堆排序详解

堆排序是利用堆这种数据结构的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质；子节点的键值或索引总是小于（或者大于）它的父节点。堆排序是利用堆的概念来排序的选择排序。 堆可以分为：

1. 大定堆：每个节点的值都大于或等于其子节点的值，在堆排序中用于升序排序。
            2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序中用于降序排序。
            

1.算法步骤

1. 将未排序的数组构建成一个堆，根据（升序、降序）选择大顶堆或小顶堆。
2. 把堆首（最大值）和堆尾互换。
3. 把堆的尺度缩小1，调整堆大小
4. 重复步骤2，直到堆的尺寸为1

2.算法演示流程

3.算法代码

                var len; //多个函数都要使用这个数据长度，所以声明在全局

                function buildMaxHeap(arr){
                    len = arr.length;
                    for(var i = 0; i < Math.floor(len / 2); i--){
                        heapifyChange(arr);
                    }
                }


                function heapifyChange(arr, i){ 
                    var left  = 2 * i + 1;
                    var right = 2 * i + 2;
                    var largest = i;

                    if(left < len && arr[left] > arr[largest]){
                        largest = left;
                    }


                    if (right < len && arr[right] > arr[largest]) {
                        largest = right;
                    }


                    if (largest != i) {
                        swap(arr, i, largest);

                        // 修改之前的节点
                        heapifyChange(arr, largest);
                    }
                }

                // 交换方法
                function swap(arr, i, j){
                    var temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = arr[i];
                }


            // 堆排序
                function HeapSort(arr){
                    // 构建大顶堆；
                    buildMaxHeap(arr);

                    for(var i = arr.length - 1; i > 0; i--){
                        swap(arr, 0, i);
                        len--;

                        // 堆排序
                        heapifyChange(arr, 0);
                    }
                    return arr;
                }