冒泡排序 & 选择排序 & 插入排序 & 希尔排序 JavaScript 实现
之前用 JavaScript 写过 快速排序 和 归并排序，本文聊聊四个基础排序算法。（本文默认排序结果都是从小到大）
冒泡排序
冒泡排序每次循环结束会将最大的元素 "冒泡" 到最后一位。
以 [1, 5, 2, 4, 3] 为例，O(n^2) 的复杂度，总共外层循环 5 次，第一次循环结束后的结果是 [1, 2, 4, 3, 5]。 首先是 1 和 5 比较，1 <=5，不交换位置，然后 5 和 2 比较，5 > 2，交换位置，数组变为 [1, 2, 5, 4, 3]，然后 5 和 4 比较，交换位置，数组变为 [1, 2, 4, 5, 3]，最后 5 和 3 比较，交换位置，数组为 [1, 2, 4, 3, 5]，这个时候最大的元素 5 已经到了最后，整个交换过程中大的元素就好像 "冒泡" 一样冒出来。然后 [1, 2, 4, 3] 再进行同样操作，以此类推。
冒泡排序看起来无论最好情况还是最坏情况，复杂度一样，都是 O(n^2)。
function swap(array, a, b) { var tmp = array[a]; array[a] = array[b]; array[b] = tmp;}function bubbleSort(array) { var _array = array.concat(); for (var i = 0, len = _array.length; i < len; i++) for (var j = 0; j < len - 1 - i; j++) if (_array[j] > _array[j + 1]) swap(_array, j, j + 1); return _array;}var a = [1, 5, 2, 4, 3];var ans = bubbleSort(a);console.log(ans); // [1, 2, 3, 4, 5]选择排序
选择排序每次循环会找到最值元素的下标，然后将该元素交换到最前面。所以选择元素每次循环交换一次，不会像冒泡一样多次交换。
还是以 [1, 5, 2, 4, 3] 为例，第一次循环比较，默认最值下标为 0，最值为 1，接着分别和 5，2，4，3 比较，ok 比完，最值的下标还是 0，那么就不交换（也可以看做 array[0] 和 array[0] 交换）。接着进行第二轮，是为 [5, 2, 4, 3] 进行循环，以此类推。
和冒泡相比，选择排序也是无论好坏情况，复杂度都是 O(n^2)，而效率应该比冒泡稍微好点，毕竟交换次数少了。
function swap(array, a, b) { var tmp = array[a]; array[a] = array[b]; array[b] = tmp;}function selectionSort(array) { var _array = array.concat(); for (var i = 0, len = _array.length; i < len; i++) { // 最值元素下标 var index = i; for (var j = i + 1; j < len; j++) if (_array[j] < _array[index]) index = j; swap(_array, i, index); } return _array;}var a = [1, 5, 2, 4, 3];var ans = selectionSort(a);console.log(ans); // [1, 2, 3, 4, 5]插入排序
插入排序会比前面两种排序算法高效。它将数组分成 "已排序" 和 "未排序" 两部分，一开始的时候，"已排序" 的部分只有一个元素，然后将它后面一个元素从 "未排序" 部分插入 "已排序" 部分，从而 "已排序" 部分增加一个元素，"未排序" 部分减少一个元素。以此类推，完成全部排序。（摘自阮老师的博文 http://javascript.ruanyifeng.com/library/sorting.html）
还是以 [1, 5, 2, 4, 3] 为例，外层还是需要循环 5 次，假设循环到第三次，到 2 这个元素，前面已经有序，是为 [1, 5]，我们要将 2 插入，首先比较 5 和 2，交换，此时数组前三项为 [1, 2, 5]，再比较 1 和 2，ok，不用交换了，有序了，比较结束。再看 4，第一次比较后，交换，数组为 [1, 2, 4, 5]，然后 4 和 2 比较，ok，有序了，不用继续比了，那么 2 就不用和 1 比较了，这样就大大节省了相邻元素两两比较的次数。
和前两者相比，插入排序能减少比较次数，当然最坏情况下还是 O(n^2)，但是和选择排序相比，可能会多交换次数。
function insertionSort(array) { var _array = array.concat(); for (var i = 0, len = _array.length; i < len; i++) { // 储存当前位置的值 var item = _array[i]; // 和前面已经有序的部分，比较，交换 for (j = i - 1; j > -1 && _array[j] > item; j--) _array[j + 1] = _array[j]; _array[j+1] = item; } return _array;}var a = [1, 5, 2, 4, 3];var ans = insertionSort(a);console.log(ans); // [1, 2, 3, 4, 5]当然，真实生产环境中不可能用这三种排序方法，毕竟效率太低！不过一定要比较效率的话，我觉得是 插入排序 > 选择排序 > 冒泡排序！
希尔排序
希尔排序是选择排序的升级版，可以说是分组插入排序，据说复杂度达到 O(n^1.2)。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
- 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位
它是怎么排序的呢？我们设定一个变量叫做 gap，gap 小于数组长度，对于数组，我们将距离 gap 的元素划分为一组，每组进行插入排序，gap 不断变小，最后减为 1，即完成希尔排序。
gap 如何取值？有个简单一点的方法，第一次取值数组长度一半，然后再一半，再一半，最后为 1。当然如果要求更高效率，可以深入研究下 gap 的取值。至于希尔排序为什么效率会比普通的插入排序高，这点不在本文探讨范围之内（其实是我不知道），有兴趣的可以查阅相关资料。
// 希尔排序：先将整个待排序记录序列分割成若干个子序列// 在序列内分别进行直接插入排序，待整个序列基本有序时，// 再对全体记录进行一次直接插入排序function shellSort(array){ var len = array.length , gap = ~~(len >> 1); // 克隆数组 var result = array.concat(); while (gap > 0) { for(var i = gap; i < len; i++) { var tmp = result[i]; var j = i - gap; while (j >= 0 && tmp < result[j]) { result[j + gap] = result[j]; j -= gap; 1 } result[j + gap] = tmp; } gap = ~~(gap >> 1); } return result;}var a = [1, 5, 2, 4, 3];var ans = shellSort(a);console.log(ans); // [1, 2, 3, 4, 5]Read More：
- http://www.cnblogs.com/wteam-xq/p/4752610.html
- http://www.cnblogs.com/ITtangtang/p/3959960.html
- http://bubkoo.com/2014/01/15/sort-algorithm/shell-sort/
