前端算法之排序

2018-05-28

排序算法分析比较

1 快速排序（QuickSort）

快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。

（1） 如果不多于1个数据，直接返回。
（2） 一般选择序列最左边的值作为支点数据。
（3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。
（4） 对两边利用递归排序数列。

快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。
快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。

2 归并排序（MergeSort）

1
2
3

归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，
然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，
因为它需要一个额外的数组。

3 堆排序（HeapSort）

堆排序适合于数据量非常大的场合（百万数据）。

堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。
比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。

堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。
接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。

4 Shell排序（ShellSort）

Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。
平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。

Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。
但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。

5 插入排序（InsertSort）

1
2

插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。
一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。

6 冒泡排序（BubbleSort）

1
2

冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，
较小的数据上升。它是O(n^2)的算法。

7 选择排序（SelectSort）

1
2

这两种排序方法都是交换方法的排序算法，效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。
它们只是排序算法发展的初级阶段，在实际中使用较少。

8 基数排序（RadixSort）

1
2
3

基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法，但是它只能用于整数的排序，
如果我们要把同样的办法运用到浮点数上，我们必须了解浮点数的存储格式，并通过特殊的方式将浮点数映射到整数上，
然后再映射回去，这是非常麻烦的事情，因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。

总结

排序法	平均时间	最差情形	稳定度	额外空间	备注
冒泡排序	O(nlogn)	O(n2)	稳定	O(1)	效率最低,n很小时可以使用,一般不用
选择排序	O(nlogn)	O(n2)	不稳定	O(1)	效率很低,n很小时可以使用,一般不用
插入排序	O(nlogn)	O(n2)	稳定	O(1)	大部分已排序时比较好
希尔排序	O(nlogn)	O(n的s次方)	不稳定	O(1)	1<s<2
快速排序	O(nlogn)	O(n2)	不稳定	O(nlogn)	数据量很大时好,平均效率最高的算法
归并排序	O(nlogn)	O(nlogn)	稳定	O(1)	数据量很大时好
堆排序	O(nlogn)	O(nlogn)	不稳定	O(1)	数据量很大时好

冒泡排序: 最慢的排序算法,基本上用不着!!!

var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator');

var bubbleSort = function (data) {
    var l = data.length;
    for (var i = 0; i <= l - 1; i++) {  //外层循环表示要进行length趟排序
        //内层循环表示在每一趟中两两交换进行排序
        for (var j = 1; j <= l; j++) {
            if (data[j] < data[j - 1]) {
                var tmp = data[j];
                data[j] = data[j - 1];
                data[j - 1] = tmp;
            }
        }
    }
    return data;
}

var data = generateTestData(20000);

var start = new Date().getTime();
console.log('start sorting....');

var result = bubbleSort(data);

var end = new Date().getTime();
console.log('耗时: ' + (end - start) + ' ms');

// console.log(result);

选择排序
选择排序是先找到起始数组中最小的元素，将它交换到i=0；
然后寻找剩下元素中最小的元素，将它交换到i=1的位置…… 直到找到第二大的元素，将它交换到n-2的位置。
这时，整个数组的排序完成。

var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator')
var selectionSort = function (data) {
    // var l = data.length;
    // for (var i = 0; i <= l - 2; i++) {
    //     for (var j = i + 1; j <= l - 1; j++) {
    //         if (data[j] < data[i]) {
    //             var tmp = data[i];
    //             data[i] = data[j];
    //             data[j] = tmp;
    //         }
    //     }
    // }
    var l = data.length,
        min_index;
    for (var i = 0; i <= l - 2; i++) {
        min_index = i;
        //在后面的部分中找到最小值得index
        for (var j = i + 1; j <= l - 1; j++) {
            if (data[j] < data[min_index]) {
                min_index = j;
            }
        }
        //将最小值交换到未排序部分的头部
        var tmp = data[i];
        data[i] = data[min_index];
        data[min_index] = tmp;
    }
    return data;
}
var data = generateTestData(100000);
// console.log(data);
var start = new Date().getTime();
console.log('start sorting....');
var result = selectionSort(data);
var end = new Date().getTime();
console.log('耗时: ' + (end - start) + ' ms');
// console.log(result);

插入排序:将整个数据集看作两个部分,前面已排序的部分和后面未排序的部分。
每次从未排序的部分中选择第一个数,插入到前面已排序部分的合适位置。
速度很慢!一般在数据集不超过1000的情况下使用。。

var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator');
var insertSort = function (data) {
    var l = data.length;
    for (var i = 1; i <= l; i++) {
        var j = i - 1;
        while ((j >= 0) && (data[j] < data[j - 1])) {
            //交换
            var tmp = data[j];
            data[j] = data[j - 1];
            data[j - 1] = tmp;
            j--;  //j--
        }
    }
    return data;
}
var data = generateTestData(20000);
// console.log(data);
var start = new Date().getTime();
console.log('start sorting....');
var result = insertSort(data);
var end = new Date().getTime();
console.log('耗时: ' + (end - start) + ' ms');
// console.log(result);

希尔排序
Shell Sorting依赖于间隔(step)的选取。
希尔排序的核心理念和插入排序不同,它会首先比较距离较远的元素,而非相邻元素。
使用这种方案可以使离正确位置很远的元素能够快速回到更合适的位置。
可以动态定义每次排序的间隔,但在应用中,通常会提前定义好间隔序列。
希尔排序可以和其他排序算法配合使用,本例使用插入排序。
分组间隔的合理性会对希尔排序的性能造成较大的影响!!!
希尔排序比冒泡排序平均快5倍,比插入排序大致快2倍,但是比快排、归并、堆排序慢的多!!!!
但是比较简单实现,通常适用于数据量在5000以下的场景。。

var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator');
var shellSort = function (data, gaps /*array of numbers*/) {
    var l = data.length;
    for (var k = 0; k < gaps.length; k++) {  //最外层循环取得每次的step
        var step = gaps[k];
        //内部使用插入排序算法!
        for (var i = step; i <= l; i += step) {
            var j = i - step;
            while ((j >= 0) && (data[j] < data[j - step])) {
                //交换
                var tmp = data[j];
                data[j] = data[j - step];
                data[j - step] = tmp;
                j -= step;  //j-step
            }
        }
    }
    return data;
}
var data = generateTestData(50000);
// console.log(data);
var start = new Date().getTime();
console.log('start sorting....');
var result = shellSort(data, [10, 4, 1]);
// var result = shellSort(data, [701, 301, 132, 57, 23, 10, 4, 1]);
var end = new Date().getTime();
console.log('耗时: ' + (end - start) + ' ms');
// console.log(result);

快速排序: 快速排序通常被认为是高效，快速等特点是使用V8引擎的实现Array.prototype.sort()上有超过23个项目的数组。
对于少于23个项目，V8采用插入排序法。
快排是处理大数据集最快的算法之一。它是一种分而治之的算法,通过递归的方式将数据集依次分解为包含较小元素和包含
较大元素的不同子序列。不断重复这个步骤直至所有数据有序。
这个算法首先要在数据集中选择一个基准值(pivot),数据排序围绕基准值进行。
将列表中小于基准值的数据移动到一侧,将大于基准值的数据移动到另一侧。
快速排序非常适用于大数据集,处理小数据集反而性能下降。

var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator');
function quickSort(data, l, r) {
    {
        if (l < r) {
            //Swap(s[l], s[(l + r) / 2]); //如果以数组中间的数作为基准值,将中间的这个数和第一个数交换即可
            var i = l, j = r,
                pivot = data[l];  //以数组第一个数作为基准值来分区
            while (i < j) {
                // 从右向左找第一个小于x的数
                while (i < j && data[j] >= pivot) {
                    j--;
                }
                if (i < j) {
                    data[i++] = data[j];
                }
                // 从左向右找第一个大于等于x的数
                while (i < j && data[i] < pivot) {
                    i++;
                }
                if (i < j) {
                    data[j--] = data[i];
                }
            }
            data[i] = pivot;  //将pivot放入正确位置
            // 对左右两边递归调用
            quickSort(data, l, i - 1);
            quickSort(data, i + 1, r);
        }
    }
    return data;
}
var data = generateTestData(20000000);
// console.log(data);
var start = new Date().getTime();
console.log('start sorting....');
var result = quickSort(data, 0, data.length - 1);
var end = new Date().getTime();
console.log('耗时: ' + (end - start) + ' ms');
// console.log(result);

var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator');
 * 交换两个数
function swap(items, firstIndex, secondIndex) {
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

 * 分区操作: 以数组的中位数为基准值!
function partition(items, left, right) {
    var pivot = items[Math.floor((right + left) / 2)],
        i = left,
        j = right;
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

 * 快速排序
function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right);
        if (left < index - 1) {
            quickSort(items, left, index - 1);
        }
        if (index < right) {
            quickSort(items, index, right);
        }
    }
    return items;
}
var data = generateTestData(500000);
// console.log(data);
var start = new Date().getTime();
console.log('start sorting....');
var result = quickSort(data, 0, data.length - 1);
var end = new Date().getTime();
console.log('耗时: ' + (end - start) + ' ms');
// console.log(result);

快速排序详解

1
2

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，而且快速排序思想----分治法也确实实用!
必须要熟练掌握快排,弄清原理后,能够默写出快排算法!!!

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。
对快速排序作了进一步的说明：挖坑填数+分治法：

index	0	1	2	3	4	5	6	7	8	9
	72	6	57	88	60	42	83	73	48	85

以一个数组作为示例，取区间第一个数为基准数。
初始时，i = 0;  j = 9;   X = a[i] = 72

由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++;  
这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。
这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

index	0	1	2	3	4	5	6	7	8	9
	48	6	57	88	60	42	83	73	88	85

数组变为上述这样。 i = 3; j = 7; X=72

再重复上面的步骤，先从后向前找，再从前向后找。

从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;

从i开始向后找，当i=5时，由于i==j退出。

此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

index	0	1	2	3	4	5	6	7	8	9
	48	6	57	42	60	72	83	73	88	85

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

对挖坑填数进行总结

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

照着这个总结很容易实现挖坑填数的代码：

int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置  
{  
    int i = l, j = r;  
    int x = s[l]; //s[l]即s[i]就是第一个坑  
    while (i < j)  
    {  // 从右向左找小于x的数来填s[i]  
        while(i < j && s[j] >= x)   
            j--;    
        if(i < j)   
        {  
            s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑  
            i++;  
        }  
        // 从左向右找大于或等于x的数来填s[j]  
        while(i < j && s[i] < x)  
            i++;    
        if(i < j)   
        {  
            s[j] = s[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑  
            j--;  
        }  
    }  
    //退出时，i等于j。将x填到这个坑中。  
    s[i] = x;  
    return i;  
}

再写分治法的代码：

void quick_sort1(int s[], int l, int r)  
{  
    if (l < r)  
    {  
        int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]  
        quick_sort1(s, l, i - 1); // 递归调用   
        quick_sort1(s, i + 1, r);  
    }  
}

这样的代码显然不够简洁，对其组合整理下：

void quick_sort(int s[], int l, int r)  
{  
    if (l < r)  
    {  
        //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换(以数组中间的数作为基准值!!)  
        int i = l, j = r, x = s[l];  
        while (i < j)  
        {  
            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数  
                j--;    
            if(i < j)   
                s[i++] = s[j];  
              
            while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数  
                i++;    
            if(i < j)   
                s[j--] = s[i];  
        }  
        s[i] = x;  
        quick_sort(s, l, i - 1); // 递归调用   
        quick_sort(s, i + 1, r);  
    }  
}

快速排序还有很多改进版本，如随机选择基准数，区间内数据较少时直接用另的方法排序以减小递归深度。

注1，有的书上是以中间的数作为基准数的，要实现这个方便非常方便，直接将中间的数和第一个数进行交换就可以了。

归并排序
如果我们要将一副扑克按照数字大小排序。此前已经有两个人分别将其中的一半排好顺序。
那么我们可以将这两堆扑克向上放好，假设小的牌在上面。此时，我们将看到牌堆中最上的两张牌。
我们取两张牌中小的那张取出放在手中。两个牌堆中又是两张牌暴露在最上面，继续取小的那张放在手中……
直到所有的牌都放入手中，那么整副牌就排好顺序了。这就是归并排序。

var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator');
 * js数组方法实现merge非常简洁,但是效率不高,见通用版本的merge方法!!!
function merge(left, right) {
    var result = [];
    while (left.length > 0 && right.length > 0) {
        if (left[0] < right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    return result.concat(left).concat(right);
}
function mergeSort(items) {
     * 此句为递归结束条件,绝对不能遗漏!!!!
    if (items.length == 1) {
        return items;
    }
    var middle = Math.floor(items.length / 2),
        left = items.slice(0, middle),
        right = items.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
var data = generateTestData(300000);
// console.log(data);
var start = new Date().getTime();
console.log('start sorting....');
var result = mergeSort(data);
var end = new Date().getTime();
console.log('耗时: ' + (end - start) + ' ms');
// console.log(result);

归并排序通用版本

var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator');
function merge(a1, a2) {
    var result = [];
    var i = 0,
        j = 0,
        l1 = a1.length,
        l2 = a2.length;
    while (i < l1 && j < l2) {
        if (a1[i] < a2[j]) {
            result.push(a1[i++]);
        } else {
            result.push(a2[j++]);
        }
    }
    if (i < l1) {
        for (; i < l1; i++) {
            result.push(a1[i]);
        }
    }
    if (j < l2) {
        for (; j < l2; j++) {
            result.push(a2[j]);
        }
    }
    return result;
}
function mergeSort(data) {
    /***
     * 此句为递归结束条件,绝对不能遗漏!!!!
     */
    if (data.length === 1) {
        return data;
    }
    var middle = Math.floor(data.length / 2);
    var left = data.slice(0, middle),
        right = data.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
var data = generateTestData(3000000);
// console.log(data);
var start = new Date().getTime();
console.log('start sorting....');
var result = mergeSort(data);
var end = new Date().getTime();
console.log('耗时: ' + (end - start) + ' ms');
// console.log(result);

1	归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，
取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

//将有序数组a[]和b[]合并到c[]中  
void MemeryArray(int a[], int n, int b[], int m, int c[])  
{  
    int i, j, k;  
    i = j = k = 0;  
    while (i < n && j < m)  
    {  
        if (a[i] < b[j])  
            c[k++] = a[i++];  
        else  
            c[k++] = b[j++];   
    }  
  
    while (i < n)  
        c[k++] = a[i++];  
  
    while (j < m)  
        c[k++] = b[j++];  
}

可以看出合并有序数列的效率是比较高的，可以达到O(n)。

解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，
那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，
然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

//将有二个有序数列a[first...mid]和a[mid...last]合并。  
void mergearray(int a[], int first, int mid, int last, int temp[])  
{  
    int i = first, j = mid + 1;  
    int m = mid,   n = last;  
    int k = 0;  
      
    while (i <= m && j <= n)  
    {  
        if (a[i] <= a[j])  
            temp[k++] = a[i++];  
        else  
            temp[k++] = a[j++];  
    }  
      
    while (i <= m)  
        temp[k++] = a[i++];  
      
    while (j <= n)  
        temp[k++] = a[j++];  
      
    for (i = 0; i < k; i++)  
        a[first + i] = temp[i];  
}  

void mergesort(int a[], int first, int last, int temp[])  
{  
    if (first < last)  
    {  
        int mid = (first + last) / 2;  
        mergesort(a, first, mid, temp);    //左边有序  
        mergesort(a, mid + 1, last, temp); //右边有序  
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并  
    }  
}  
  
bool MergeSort(int a[], int n)  
{  
    int *p = new int[n];  
    if (p == NULL)  
        return false;  
    mergesort(a, 0, n - 1, p);  
    delete[] p;  
    return true;  
}

1
2
3

归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，
时间复杂度可以记为O(N)，故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作，
所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。

堆排序
1.堆
堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]
即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。
堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，
满足Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。
由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。
2.堆排序的思想
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
其基本思想为(大顶堆)：
1)将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无须区；
2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),
且满足R[1,2...n-1]<=R[n];
3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，
然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。
不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
操作过程如下：
1)初始化堆：将R[1..n]构造为堆；
2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。
因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。
堆排序
堆排序适合于数据量非常大的场合（百万数据）。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。
比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。
接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值。
如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。

实现堆排序需要解决两个问题：
　　　　1.如何由一个无序序列建成一个堆？
　　　　2.如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator');
/*方法说明：调整堆,维护堆的性质
 @param  arr 数组
 @param  x   数组下标
 @param  len 堆大小*/
function adjustHeap(arr, x, len) {
    var l = 2 * x, r = 2 * x + 1, largest = x, temp;
    if (l < len && arr[l] > arr[largest]) {
        largest = l;
    }
    if (r < len && arr[r] > arr[largest]) {
        largest = r;
    }
    if (largest != x) {
        temp = arr[x];
        arr[x] = arr[largest];
        arr[largest] = temp;
        adjustHeap(arr, largest, len);
    }
}

/*方法说明：堆排序

function heapSort(array) {
    //建堆
    var heapSize = array.length, temp;
    for (var i = Math.floor(heapSize / 2); i >= 0; i--) {
        adjustHeap(array, i, heapSize);
    }
    //堆排序
    for (var j = heapSize - 1; j >= 1; j--) {
        temp = array[0];
        array[0] = array[j];
        array[j] = temp;
        adjustHeap(array, 0, --heapSize);
    }
    return array;
}
var data = generateTestData(20000);
// console.log(data);
var start = new Date().getTime();
console.log('start sorting....');
var result = heapSort(data);
var end = new Date().getTime();
console.log('耗时: ' + (end - start) + ' ms');
// console.log(result);