排序算法2

归并排序

1）整体就是一个简单递归，左边排好序、右边排好序、让其整体有序
2）让其整体有序的过程里用了排外序方法

mergeSortTree

算法解析：
将整体进行左右分组，在分组过程中，对中间下标的计算采用mid = L + ((R - L) >> 1),而不是直接采用mid=(R+L)/2,目的是防止溢出，当R和L都比较大时，两者的和会超出数组长度；然后同样的方法将分好的组再进行左右分组，依次类推，最后将数分为两个一组或者单个数一组的形式，然后将每组中的数进行排序，小值位于前面，之后就是合并，在合并时，将前后两组的数，按照从左到右的顺序进行一一对比，按照从小到大的顺序排列好，以此类推，最后就能得到一个递增的数组。

function mergeSort(array) {
    if (array == null || array.length < 2) {
        return;
    }
    process(array, 0, array.length - 1);
}
function process(array, L, R) {
    if (L == R) {
        return;
    }
    var mid = L + ((R - L) >> 1);
    process(array, L, mid);
    process(array, mid + 1, R);
    merge(array, L, mid, R);
}
function merge(array, L, mid, R) {
    var help = [];
    var p1 = L;
    var p2 = mid + 1;
    while (p1 <= mid && p2 <= R) {
        help[i++] = array[p1] <= array[p2] ? array[p1++] : array[p2++];
    }
    while (p1 <= mid) {
        help[i++] = array[p1++];
    }
    while (p2 <= R) {
        help[i++] = array[p2++];
    }
    for (var i = 0; i < help.length; i++) {
        array[L + i] = help[i];
    }
}

归并排序的扩展

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
例子:[1,3,4,2,5] 1左边比1小的数，没有; 3左边比3小的数，1; 4左边比4小的数，1，3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、2; 所以小和为1+1+3+1+1+3+4+2=16。

小和问题就是采用了归并排序的方法，其中关键的一句代码就是res += array[p1] < array[p2] ? (R - p2 + 1) * array[p1] : 0;在两个小组中的数进行比较时，位于左边的组中的数，在右边组中遇到一个大于它的数时，res加(R - p2 + 1) * array[p1]，因为小组中数据已经进行了从小到大的排序，所以在遇到一个比它大的数时，这个数后面的数也都大于前面这组的这个数，所以对于array[p1]来说，它在小和中出现的次数就是(R-p2+1)，然后乘以array[p1]，累加在res中，最后就能得到整个数组的小和。

function smallSort(array) {
    if (array == null || array.length < 2) {
        return 0;
    }
    return process(array, 0, array - 1);
}
function process(array, L, R) {
    if (L = R) {
        return 0;
    }
    var mid = L + ((R - L) >> 1);
    return process(array, L, mid) + process(array, mid + 1, R) + merge(array, L, mid, R)
}
function merge(array, L, m, R) {
    var help = [];
    var p1 = L;
    var p2 = m + 1;
    var res = 0;
    while (p1 <= m && p2 <= R) {
        res += array[p1] < array[p2] ? (R - p2 + 1) * array[p1] : 0;
        help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
    }
    while (p1 <= m) {
        help[i++] = array[p1++];
    }
    while (p2 <= R) {
        help[i++] = array[p2++];
    }
    for (var i = 0; i < help.length; i++) {
        array[L + i] = help[i];
    }
    return res;
}

堆

堆结构就是用数组实现的完全二叉树结构
完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
完全二叉树中如果每棵子树的最小值都在顶部就是小根堆

堆排序

先让整个数组都变成大根堆结构，建立堆的过程:
1. 从上到下的方法，时间复杂度为O(N*logN)
2. 从下到上的方法，时间复杂度为O(N)

2，把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N*logN)
3，堆的大小减小成0之后，排序完成
算法如下：

function heapSort(array) {
    if (array = null || array.length < 2) {
        return;
    }
    for (var i = 0; i < array.length; i++) {
        heapInsert(array, i);
    }
    var heapSize = array.length;
    swap(array, 0, --heapSize);
    while (heapSize > 0) {
        heapify(array, 0, heapSize);
        swap(array, 0, --heapSize);
    }
}
// 某个数现在处在index位置，往上继续移动
function heapInsert(array, index) {
    while (array[index] > array[(index - 1) / 2]) {
        swap(array, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}
// 某个数在index位置，能否往下移动
function heapify(array, index, heapSize) {
    var left = index * 2 + 1; //左孩子下标
    while (left < heapSize) { //下方还有孩子的时候
        // 两个孩子中，谁的值大，把下标给largest
        var largest = left + 1 < heapSize && array[left + 1] > array[left] ? left + 1 : left;
        // 父和较大的孩子之间，谁的值大，把下标给largest
        largest = array[largest] > array[index] ? largest : index;
        if (largest == index) {
            break;
        }
        swap(array, largest, index);
        index = largest;
        left = index * 2 + 1;
    }
}
function swap(array, i, j) {
    var tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

maxHeap

解析：首先用heapInsert方法将数组转换成大根堆形式，然后将堆的第一个值也就是数组的最大值与堆最后一个互换，然后重新对数组转换为大根堆形式，不过此时对于堆最后一个值不参与转换，这样就相当于将数组最大值固定在数组末端，在下一次大根堆转换后，同样将第一个值与此时的最末值交换，再继续转换，此时就能得到数组第二大的值，并且储存在数组倒数第二个位置，一直进行这个过程，最后当heapSize为0时停止。

堆排序扩展题目

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
先在npm搜索优先级队列的JS代码，直接下载应用

<script src="./node_modules/js-priority-queue/priority-queue.min.js"></script>

接下来展示代码，其中return a-b 表示输出由小到大队列

var queue = new PriorityQueue({ comparator: function (a, b) { return a - b; } });
function SortArrayDistanceLseeK(array, k) {
    if (array == null && array.length < 2) {
        return;
    }
    var index = 0;
    for (; index <= Math.min(array.length, k); index++) {
        queue.queue(array[index]);
    }
    var i = 0
    for (; index < array.length; i++, index++) {
        array[i] = queue.dequeue();
        queue.queue(array[index]);
    }
    for (; i < array.length; i++) {
        array[i] = queue.dequeue();
    }
}

首先判断数组长度是否小于所提供的k值，如果小于，则能直接输出队列，若大于k值，则继续进行，将队列进行排序后，输出队列中的最小值，然后将数组中后面的一个数添加到队列中进行排序，由于队列长度是k，所以能保证元素移动距离不超过k，进行到最后队列中剩下数组最后k个元素且已经排好序，然后将元素按顺序输出，这样就能将原数组排好序，且每个元素移动距离不超过k。