归并排序
思路：将要排序的数组从中间分成两部分，分别排序，再将排序好的两部分合并。
这里用到了分治思想：分而治之，讲一个大问题分解成若干个小问题来解决。很明显这里需要用到递归这种编程方式。
function mergeSort(array, region1, region2) { var tempArray = []; var i = region1[0]; var j = region2[0]; for (; i <= region1[1]; i++) { for (; j <= region2[1]; j++) { if (array[i] > array[j]) { tempArray.push(array[j]); } else { break; } } tempArray.push(array[i]); } for (; j <= region2[1]; j++) { tempArray.push(array[j]); } var n = 0; for (let k = region1[0]; k <= region2[1]; k++) { array[k] = tempArray[n++]; } return [region1[0], region2[1]]; }function divide(array, start, end) { if (start >= end) return [start, end]; var mid = Math.floor((end+start)/2); return mergeSort(array, divide(array, start, mid),divide(array, mid+1, end)); }复制代码 分析：
-
稳定的排序；
-
根据递推代码求时间复杂度的方法，分析?代码时间复杂度：归并排序的执行效率与数据有序度无关，所有时间复杂度O(nlogn)；
-
每次合并时，会临时申请一个最大不超过n的内存空间，合并完成释放。而空间复杂度是指算法运行时需要的额外空间，每次执行时函数都仅仅申请了一块内存空间，但并没有累积。因此空间复杂度O(n)，不是原地排序，这也是归并排序不如快速排序应用广泛的原因;
快速排序
思路： 同样采用分治思想。 从数组中选一个位置的数据，小于它的放左边，大于它的放右边。之后再分别对左右两边再次进行同样操作以此类推。直到间距缩小到1，说明数据都有序了。其实就是每次通过分区的方式找到一个元素在有序后的数组中的位置。
总结就是：
- 对整个数组分区；
- 对左边区域分区；
- 对右边区域分区。
// 如果pivot==end则只需从一头开始查找了function quickSort(array, start, end) { if (start >= end) return; var pivot = divide(array, start, end); quickSort(array, start, pivot-1); quickSort(array, pivot+1,end); }function divide(array, start, end) { var pivot = end; // i代表小于pivot的区域边界 var j = 0; var i = 0; while (i <= pivot) { if (array[j] <= array[pivot]) { // 因为此时插入操作不要求保证顺序，用交换就行 if (array[i] != array[j]) { var temp = array[i]; array[i] = array[j]; array[j] = temp; } i++; } j++; if (j >= pivot) break; } // 把pivot插入到小于区域的末尾 temp = array[i]; array[i] = array[pivot]; array[pivot] = temp; pivot = i; return pivot; }复制代码 对数组进行分区操作中，为了进行原地排序，空间复杂度为O(1)，又尽可能不进行移动，采用了类似插入排序的方式，同时对数组的插入操作采用交换的方式。
而这种交换操作就会造成排序算法的不稳定。
时间复杂度：平均时间复杂度O(nlogn);最坏是O(n2);
归并排序和快速排序的区别
可以发现归并是先处理子问题，然后再合并。而快速则是先对大区域分区，在对子区域分区处理。
快速排序和归并排序的思想应用
除了对无序数组进行排序外，还可以解决如：求无序数组中第K大元素，这样的问题。 快速排序每次分区都会找到pivot元素排序的位置，因此可以每次分区后比较K和pivot的位置大小，进行更加细化的查找。时间复杂度= n+n/2+n/4+n/8+...+1 = O(n);