归并排序
1）整体就是一个简单递归，左边排好序、右边排好序、让其整体有序
2）让其整体有序的过程里用了排外序方法
算法解析：
将整体进行左右分组，在分组过程中，对中间下标的计算采用
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;
}
堆
- 堆结构就是用数组实现的完全二叉树结构
- 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
- 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
堆排序
- 先让整个数组都变成大根堆结构，建立堆的过程:
- 从上到下的方法，时间复杂度为O(N*logN)
- 从下到上的方法，时间复杂度为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;
}
解析：首先用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。
