//希尔排序 function shallSort(array) { var increment = array.length; var i var temp; //暂存 do { //设置增量 increment = Math.floor(increment / 3) + 1; for (i = increment ; i < array.length; i++) { if ( array[i] < array[i - increment]) { temp = array[i]; for (var j = i - increment; j >= 0 && temp < array[j]; j -= increment) { array[j + increment] = array[j]; } array[j + increment] = temp; } } } while (increment > 1) return array; }
效果如下：
console.log( '原始数据:' + dataStore ); console.log( '希尔排序:' + shallSort( dataStore) ); // 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72 // 希尔排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
5.归并排序（Merge Sort）
将两个的有序数列合并成一个有序数列，我们称之为"归并"，归并排序的思想就是将一系列排序好的子序列合并成一个大的完整有序的序列。
实现步骤如下：
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列
一张动图来说明归并排序的过程：
具体的JS代码实现如下：
//归并排序 function mergeSort ( array ) { var len = array.length; if( len < 2 ){ return array; } var middle = Math.floor(len / 2), left = array.slice(0, middle), right = array.slice(middle); return merge(mergeSort(left), mergeSort(right)); } function merge(left, right) { var result = []; while (left.length && right.length) { if (left[0] <= right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } } while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); return result; }
测试结果如下 ：
console.log( '原始数据:' + dataStore ); console.log( '希尔排序:' + mergeSort( dataStore) ); // 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72 // 希尔排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
6.快速排序（Quicksort）
快速排序是处理大数据最快的排序算法之一，它也是一种分而治之的算法，通过递归方式将数据依次分解为包含较小元素和较大元素的不同子序列，会不断重复这个步骤，直到所有的序列全部为有序的，最后将这些子序列一次拼接起来，就可得到排序好的数据。
该算法首先要从数列中选出一个元素作为基数（pivot）。接着所有的数据都将围绕这个基数进行，将小于改基数的元素放在它的左边，大于或等于它的数全部放在它的右边，对左右两个小数列重复上述步骤，直至各区间只有1个数。
整个排序过程如下：
具体实现如下：
//快速排序 function quickSort( arr ){ if ( arr.length == 0) { return []; } var left = []; var right = []; var pivot = arr[0]; for (var i = 1; i < arr.length; i++) { if (arr[i] < pivot) { left.push( arr[i] ); } else { right.push( arr[i] ); } } return quickSort( left ).concat( pivot, quickSort( right )); }
测试结果如下：
console.log( '原始数据:' + dataStore ); console.log( '快速排序:' + quickSort( dataStore) ); // 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72 // 快速排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
至此，我们已基本介绍过一些常见的排序算法的思想和具体实现（基数排序在之前的文章已经介绍过），排序算法博大精深，我们不仅要学习理论，也要不断去实践，大家加油！
感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：测试上述代码运行效果。
PS：这里再为大家推荐一款关于排序的演示工具供大家参考：