上一次我们讲过了js的几个排序算法，有许多小伙伴私信我js还有没有其他的排序算法，那么，这次我就带来了JavaScript的十大经典排序算法，文章分为上下两部分，大伙赶紧学起来！！
冒泡排序（Bubble Sort）
冒泡排序须知：
作为最简单的排序算法之一，冒泡排序给我的感觉就像Abandon在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。。。冒泡排序还有一种优化算法，就是立一个flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。。。
什么时候最快（Best Cases）：
当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊。。。。）
什么时候最慢（Worst Cases）：
当输入的数据是反序时（写一个for循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗。。。）
冒泡排序JavaScript代码实现：
1 function bubbleSort(arr) { 2 var len = arr.length; 3 for (var i = 0; i < len; i++) { 4 for (var j = 0; j < len - 1 - i; j++) { 5 if (arr[j] > arr[j+1]) { //相邻元素两两对比 6 var temp = arr[j+1]; //元素交换 7 arr[j+1] = arr[j]; 8 arr[j] = temp; 9 } 10 } 11 } 12 return arr; 13 }
选择排序须知： 在时间复杂度上表现最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度。。。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
选择排序JavaScript代码实现：
1 function selectionSort(arr) { 2 var len = arr.length; 3 var minIndex, temp; 4 for (var i = 0; i < len - 1; i++) { 5 minIndex = i; 6 for (var j = i + 1; j < len; j++) { 7 if (arr[j] < arr[minIndex]) { //寻找最小的数 8 minIndex = j; //将最小数的索引保存 9 } 10 } 11 temp = arr[i]; 12 arr[i] = arr[minIndex]; 13 arr[minIndex] = temp; 14 } 15 return arr; 16 }
插入排序须知： 插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。当然，如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌，那估计这辈子你对插入排序的算法都不会产生任何兴趣了。。。 插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。对于这种算法，得了懒癌的我就套用教科书上的一句经典的话吧：感兴趣的同学可以在课后自行研究。。。
插入排序JavaScript代码实现：
1 function insertionSort(arr) { 2 var len = arr.length; 3 var preIndex, current; 4 for (var i = 1; i < len; i++) { 5 preIndex = i - 1; 6 current = arr[i]; 7 while(preIndex >= 0 && arr[preIndex] > current) { 8 arr[preIndex+1] = arr[preIndex]; 9 preIndex--; 10 } 11 arr[preIndex+1] = current; 12 } 13 return arr; 14 }
希尔排序须知： 希尔排序是插入排序的一种更高效率的实现。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。在这里，我就使用了这种方法。
希尔排序JavaScript代码实现：
1 function shellSort(arr) { 2 var len = arr.length, 3 temp, 4 gap = 1; 5 while(gap < len/3) { //动态定义间隔序列 6 gap =gap*3+1; 7 } 8 for (gap; gap> 0; gap = Math.floor(gap/3)) { 9 for (var i = gap; i < len; i++) { 10 temp = arr[i]; 11 for (var j = i-gap; j > 0 && arr[j]> temp; j-=gap) { 12 arr[j+gap] = arr[j]; 13 } 14 arr[j+gap] = temp; 15 } 16 } 17 return arr; 18 }
归并排序须知： 作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第2种方法）
自下而上的迭代
在《数据结构与算法JavaScript描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：
However, it is not possible to do so in JavaScript, as the recursion goes too deep
for the language to handle.
然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。
说实话，我不太理解这句话。意思是JavaScript编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。
更新：
在《JavaScript语言精粹》的第四章里提到了递归问题。对我之前的疑问进行了解答：
Some languages offer the tail recursion optimization. This means that if a function returns the result of invoking itself recursively, then the invocation is replaced with a loop, which can significantly speed things up. Unfortunately, JavaScript does not currently provide tail recursion optimization. Functions that recurse very deeply can fail by exhausting the return stack.
一些语言提供了尾递归优化。这意味着如果一个函数返回自身递归调用的结果，那么调用的过程会被替换为一个循环，它可以显著提高速度。遗憾的是，JavaScript当前并没有提供尾递归优化。深度递归的函数可能会因为堆栈溢出而运行失败。
简而言之，就是JavaScript没有对递归进行优化。运用递归函数不仅没有运行速度上的优势，还可能造成程序运行失败。因此不建议使用递归。
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
归并排序JavaScript代码实现：
1 function mergeSort(arr) { //采用自上而下的递归方法 2 var len = arr.length; 3 if(len < 2) { 4 return arr; 5 } 6 var middle = Math.floor(len / 2), 7 left = arr.slice(0, middle), 8 right = arr.slice(middle); 9 return merge(mergeSort(left), mergeSort(right)); 10 } 11 12 function merge(left, right) 13 { 14 var result = []; 15 16 while (left.length>0 && right.length>0) { 17 if (left[0] <= right[0]) { 18 result.push(left.shift()); 19 } else { 20 result.push(right.shift()); 21 } 22 } 23 24 while (left.length) 25 result.push(left.shift()); 26 27 while (right.length) 28 result.push(right.shift()); 29 30 return result; 31 }
