Tips: 我们知道, 单次直接插入排序是稳定的, 它不会改变相同元素之间的相对顺序, 但在多次不同的插入排序过程中, 相同的元素可能在各自的插入排序中移动, 可能导致相同元素相对顺序发生变化. 因此, 希尔排序并不稳定.
归并排序归并排序建立在归并操作之上, 它采取分而治之的思想, 将数组拆分为两个子数组, 分别排序, 最后才将两个子数组合并; 拆分的两个子数组, 再继续递归拆分为更小的子数组, 进而分别排序, 直到数组长度为1, 直接返回该数组为止.
Tips: 归并排序严格按照从左往右(或从右往左)的顺序去合并子数组, 它并不会改变相同元素之间的相对顺序, 因此它也是一种稳定的排序算法.
如下是动图效果:
归并排序可通过两种方式实现:
自上而下的递归
自下而上的迭代
如下是算法实现(方式1:递归):
function mergeSort(array) { //采用自上而下的递归方法 var length = array.length; if(length < 2) { return array; } var m = (length >> 1), left = array.slice(0, m), right = array.slice(m); //拆分为两个子数组 return merge(mergeSort(left), mergeSort(right));//子数组继续递归拆分,然后再合并 } function merge(left, right){ //合并两个子数组 var result = []; while (left.length && right.length) { var item = left[0] <= right[0] ? left.shift() : right.shift();//注意:判断的条件是小于或等于,如果只是小于,那么排序将不稳定. result.push(item); } return result.concat(left.length ? left : right); }
由上, 长度为n的数组, 最终会调用mergeSort函数2n-1次. 通过自上而下的递归实现的归并排序, 将存在堆栈溢出的风险. 亲测各浏览器的堆栈溢出所需的递归调用次数大致为:
Chrome v55: 15670
Firefox v50: 44488
Safari v9.1.2: 50755
以下是测试代码:
function computeMaxCallStackSize() { try { return 1 + computeMaxCallStackSize(); } catch (e) { // Call stack overflow return 1; } } var time = computeMaxCallStackSize(); console.log(time);
为此, ES6规范中提出了尾调优化的思想: 如果一个函数的最后一步也是一个函数调用, 那么该函数所需要的栈空间将被释放, 它将直接进入到下次调用中, 最终调用栈里只保留最后一次的调用记录.
虽然ES6规范如此诱人, 然而目前并没有浏览器支持尾调优化, 相信在不久的将来, 尾调优化就会得到主流浏览器的支持.
以下是其算法复杂度:
平均时间复杂度
最好情况
最坏情况
空间复杂度
O(nlog₂n)
O(nlog₂n)
O(nlog₂n)
O(n)
从效率上看, 归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n, 那么拆分数组共需logn步, 又每步都是一个普通的合并子数组的过程, 时间复杂度为O(n), 故其综合时间复杂度为O(nlogn). 另一方面, 归并排序多次递归过程中拆分的子数组需要保存在内存空间, 其空间复杂度为O(n).
快速排序快速排序借用了分治的思想, 并且基于冒泡排序做了改进. 它由C. A. R. Hoare在1962年提出. 它将数组拆分为两个子数组, 其中一个子数组的所有元素都比另一个子数组的元素小, 然后对这两个子数组再重复进行上述操作, 直到数组不可拆分, 排序完成.
如下是动图效果:
如下是算法实现:
function quickSort(array, left, right) { var partitionIndex, left = typeof left == 'number' ? left : 0, right = typeof right == 'number' ? right : array.length-1; if (left < right) { partitionIndex = partition(array, left, right);//切分的基准值 quickSort(array, left, partitionIndex-1); quickSort(array, partitionIndex+1, right); } return array; } function partition(array, left ,right) { //分区操作 for (var i = left+1, j = left; i <= right; i++) {//j是较小值存储位置的游标 array[i] < array[left] && swap(i, ++j, array);//以第一个元素为基准 } swap(left, j, array); //将第一个元素移至中间 return j; }
以下是其算法复杂度:
平均时间复杂度
最好情况
最坏情况
空间复杂度
O(nlog₂n)
O(nlog₂n)
O(n²)
O(nlog₂n)
快速排序排序效率非常高. 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常, 平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高. 之前在 捋一捋JS的数组 一文中就提到: Chrome的v8引擎为了高效排序, 在排序数据超过了10条时, 便会采用快速排序. 对于10条及以下的数据采用的便是插入排序.