定义
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
算法描述
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
- 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
- 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。
动图演示
代码实现
1 2 3 4 5 6 7
| public static void main(String[] args) { int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}; heapSort(array);
System.out.println(Arrays.toString(array)); }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
|
public static void heapSort(int[] array) { if (array == null || array.length <= 1) { return; }
int length = array.length;
for (int i = length / 2 - 1; i >= 0; i--) { adjustHeap(array, i, length); } for (int j = length - 1; j > 0; j--) { swap(array, 0, j); adjustHeap(array, 0, j); }
}
private static void adjustHeap(int[] array, int i, int length) { int temp = array[i]; for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { if (k + 1 < length && array[k] < array[k + 1]) { k++; } if (array[k] > temp) { array[i] = array[k]; i = k; } else { break; } } array[i] = temp; }
private static void swap(int[] array, int a, int b) { int temp = array[a]; array[a] = array[b]; array[b] = temp; }
|
算法分析
最佳情况:$T(n) = O(nlogn)$
最差情况:$T(n) = O(nlogn)$
平均情况:$T(n) = O(nlogn)$