既然是堆排序,肯定是涉及到数据结果中的堆,堆排序是利用堆来实现排序;其排序既用到完全二叉树的特性,又用到了堆父节点大于子节点的特性。
先将所有数据当成一颗完全二叉树,然后使得所有的父节点都大于子节点(满足堆的特性),然后将完全二叉树最后一个叶子节点与根节点交换(此时最后一个节点属于有序的,我们暂称其存在于有序区,而其他节点存在无序区),此时数据不再满足堆的特性,因此再继续调整,让所有父节点大于子节点,再替换最后一个叶子节点与根节点(此时有序区存在两个节点),依此循环,直至所有节点都加入有序区,则排序完成。
发现自己上面表达得有点太啰嗦了,却又不知道怎么去更改,暂且自认为已经表达了意思吧。
我们再来看看其示意图(画图太麻烦,只好百度之,注:下图来自网络)
堆排序
堆排序算法java实现代码如下:
- public class BucketSort implements IArraySort {
- //声明全局变量,用于记录数组array的长度;
- static int len;
- /**
- * 堆排序算法
- *
- * @param array
- * @return
- */
- public static int[] HeapSort(int[] array) {
- len = array.length;
- if (len < 1) return array;
- //1.构建一个最大堆
- buildMaxHeap(array);
- //2.循环将堆首位(最大值)与末位交换,然后在重新调整最大堆
- while (len > 0) {
- swap(array, 0, len - 1);
- len--;
- adjustHeap(array, 0);
- }
- return array;
- }
- /**
- * 建立最大堆
- *
- * @param array
- */
- public static void buildMaxHeap(int[] array) {
- //从最后一个非叶子节点开始向上构造最大堆
- for (int i = (len/2 - 1); i >= 0; i--) {
- adjustHeap(array, i);
- }
- }
- /**
- * 调整使之成为最大堆
- *
- * @param array
- * @param i
- */
- public static void adjustHeap(int[] array, int i) {
- int maxIndex = i;
- //如果有左子树,且左子树大于父节点,则将最大指针指向左子树
- if (i * 2 < len && array[i * 2] > array[maxIndex])
- maxIndex = i * 2;
- //如果有右子树,且右子树大于父节点,则将最大指针指向右子树
- if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
- maxIndex = i * 2 + 1;
- //如果父节点不是最大值,则将父节点与最大值交换,并且递归调整与父节点交换的位置。
- if (maxIndex != i) {
- swap(array, maxIndex, i);
- adjustHeap(array, maxIndex);
- }
- }
- /**
- * 交换数组内两个元素
- * @param array
- * @param i
- * @param j
- */
- public static void swap(int[] array, int i, int j) {
- int temp = array[i];
- array[i] = array[j];
- array[j] = temp;
- }
- }
-
由上面可以看出,堆排序时间复杂度为T(n) = O(nlogn)