JS家的排序算法 前端

当年，想凭借抱Java大腿火一把而不惜把自己名字给改了的JavaScript（原名LiveScript），如今早已光芒万丈。node JS的出现更是让JavaScript可以前后端通吃。虽然Java依然制霸企业级软件开发领域（C/C + +的大神们不要打我。。。），但在Web的江湖，JavaScript可谓风头无两，坐上了头把交椅。

然而，在传统的计算机算法和数据结构领域，大多数专业教材和书籍的默认语言都是Java或者C/C+ +。这给最近想恶补算法和数据结构知识的我造成了一定困扰，因为我想寻找一本以JavaScript为默认语言的算法书籍。当我了解到O’REILLY家的动物丛书系列里有一本叫做《数据结构与算法JavaScript描述》时，便兴奋的花了两天时间把这本书从头到尾读了一遍。它是一本很好的针对前端开发者们的入门算法书籍，可是，它有一个很大的缺陷，就是里面有很多明显的小错误，明显到就连我这种半路出家的程序猿都能一眼看出来。还有一个问题是，很多重要的算法和数据结构知识并没有在这本书里被提到。这些问题对于作为一个晚期强迫症患者的我来说简直不能忍。于是乎，一言不合我就决定自己找资料总结算法。那么，我就从算法领域里最基础的知识点——排序算法总结起好了。

我相信以下的代码里一定会有某些bug或错误或语法不规范等问题是我自己无法发现的，所以敬请各位大神能够指出错误，因为只有在不断改错的道路上我才能取得长久的进步。

十大经典算法排序总结对比

一张图概括：

主流排序算法概览

名词解释：

n: 数据规模k:“桶”的个数In-place: 占用常数内存，不占用额外内存Out-place: 占用额外内存稳定性：排序后2个相等键值的顺序和排序之前它们的顺序相同

冒泡排序（Bubble Sort）

冒泡排序须知：

作为最简单的排序算法之一！冒泡排序给我的感觉就像Abandon在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。。。冒泡排序还有一种优化算法，就是立一个flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。。。

什么时候最快（Best Cases）：

当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊。。。。）

什么时候最慢（Worst Cases）：

当输入的数据是反序时（写一个for循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗。。。）

冒泡排序动图演示：

Bubble Sort 动图演示 算法可视化来源：http://visualgo.net/

冒泡排序JavaScript代码实现：

function bubbleSort(arr) {    var len = arr.length;    for (var i = 0; i  arr[j+1]) {        //相邻元素两两对比                var temp = arr[j+1];        //元素交换                arr[j+1] = arr[j];                arr[j] = temp;            }        }    }    return arr;}

选择排序（Selection Sort）

选择排序须知：

表现最稳定的排序算法之一！因为无论什么数据进去都是O(n²)的时间复杂度。。。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

选择排序动图演示：

Selection Sort 动图演示 算法可视化来源：http://visualgo.net/

选择排序JavaScript代码实现：

function selectionSort(arr) {    var len = arr.length;    var minIndex, temp;    for (var i = 0; i

插入排序（Insertion Sort）

插入排序须知：

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。当然，如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌，那估计这辈子你对插入排序的算法都不会产生任何兴趣了。。。插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。对于这种算法，得了懒癌的我就套用教科书上的一句经典的话吧：感兴趣的同学可以在课后自行研究。。。

插入排序动图演示：

Insertion Sort 动图演示 算法可视化来源：http://visualgo.net/

插入排序JavaScript代码实现：

function insertionSort(arr) {    var len = arr.length;    var preIndex, current;    for (var i = 1; i = 0 && arr[preIndex] > current) {            arr[preIndex+1] = arr[preIndex];            preIndex--;        }        arr[preIndex+1] = current;    }    return arr;}

希尔排序（Shell Sort）

希尔排序须知：

希尔排序是插入排序的一种更高效率的实现。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。在这里，我就使用了这种方法。

希尔排序JavaScript代码实现：

function shellSort(arr) {    var len = arr.length,        temp,        gap = 1;    while(gap  0; gap = Math.floor(gap/3)) {        for (var i = gap; i = 0 && arr[j] > temp; j-=gap) {                arr[j+gap] = arr[j];            }            arr[j+gap] = temp;        }    }    return arr;}

归并排序（Merge Sort）

归并排序须知：

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

在《数据结构与算法JavaScript描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：