算法简介

堆排序（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@param  array 待排序数组*/
3function heapSort(array) {
4    console.time('堆排序耗时');
5    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
6        //建堆
7        var heapSize = array.length, temp;
8        for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
9            heapify(array, i, heapSize);
10        }
11
12        //堆排序
13        for (var j = heapSize - 1; j >= 1; j--) {
14            temp = array[0];
15            array[0] = array[j];
16            array[j] = temp;
17            heapify(array, 0, --heapSize);
18        }
19        console.timeEnd('堆排序耗时');
20        return array;
21    } else {
22        return 'array is not an Array!';
23    }
24}
25/*方法说明：维护堆的性质
26@param  arr 数组
27@param  x   数组下标
28@param  len 堆大小*/
29function heapify(arr, x, len) {
30    if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number') {
31        var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;
32        if (l < len && arr[l] > arr[largest]) {
33            largest = l;
34        }
35        if (r < len && arr[r] > arr[largest]) {
36            largest = r;
37        }
38        if (largest != x) {
39            temp = arr[x];
40            arr[x] = arr[largest];
41            arr[largest] = temp;
42            heapify(arr, largest, len);
43        }
44    } else {
45        return 'arr is not an Array or x is not a number!';
46    }
47}
48var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
49console.log(heapSort(arr));//[10, 13, 20, 22, 30, 31, 35, 46, 60, 65, 65, 77, 81, 91, 96]
50

算法分析

• 最佳情况：T(n) = O(nlogn)
• 最差情况：T(n) = O(nlogn)
• 平均情况：T(n) = O(nlogn)