3、实现堆排序
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆的性质:即子结点的值总是小于(或者大于)它的父节点。
算法步骤
- 将初始待排序列
构建成大顶堆,此堆为初始的无序区; - 将堆顶元素
与最后一个元素 交换,此时得到新的无序区 和新的有序区 , 且满足 ; - 由于交换后新的堆顶
可能违反堆的性质,因此需要对当前无序区 调整为新堆,然后再次将 与无序区最后一个元素交换,得到新的无序区 和新的有序区 。不断重复此过程直到有序区的元素个数为 ,则整个排序过程完成。
图解算法

代码实现
// Global variable that records the length of an array;
static int heapLen;
/**
* Swap the two elements of an array
* @param arr
* @param i
* @param j
*/
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/**
* Build Max Heap
* @param arr
*/
private static void buildMaxHeap(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {
heapify(arr, i);
}
}
/**
* Adjust it to the maximum heap
* @param arr
* @param i
*/
private static void heapify(int[] arr, int i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (right < heapLen && arr[right] > arr[largest]) {
largest = right;
}
if (left < heapLen && arr[left] > arr[largest]) {
largest = left;
}
if (largest != i) {
swap(arr, largest, i);
heapify(arr, largest);
}
}
/**
* Heap Sort
* @param arr
* @return
*/
public static int[] heapSort(int[] arr) {
// index at the end of the heap
heapLen = arr.length;
// build MaxHeap
buildMaxHeap(arr);
for (int i = arr.length - 1; i > 0; i--) {
// Move the top of the heap to the tail of the heap in turn
swap(arr, 0, i);
heapLen -= 1;
heapify(arr, 0);
}
return arr;
}
算法分析
- 稳定性:不稳定
- 时间复杂度:最佳:
, 最差: , 平均: - 空间复杂度: