黑马程序员技术交流社区

标题: JS家的十大经典排序算法（上） [打印本页]

作者: 月亮是我掰弯的 时间: 2016-10-17 14:39
标题: JS家的十大经典排序算法（上）
本帖最后由月亮是我掰弯的于 2016-10-17 15:04 编辑

当年，想凭借抱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循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗。。。）
冒泡排序动图演示：

冒泡排序JavaScript代码实现：

[JavaScript] 纯文本查看 复制代码

function bubbleSort(arr) {

var len = arr.length;

for (var i = 0; i < len; i++) {

for (var j = 0; j < len - 1 - i; j++) {

if (arr[j] > arr[j+1]) { //相邻元素两两对比

var temp = arr[j+1]; //元素交换

arr[j+1] = arr[j];

arr[j] = temp;

}

}

}

return arr;

}

选择排序（Selection Sort）

选择排序须知：

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

选择排序动图演示：

选择排序JavaScript代码实现：

[JavaScript] 纯文本查看 复制代码

function selectionSort(arr) {

    var len = arr.length;

    var minIndex, temp;

    for (var i = 0; i < len - 1; i++) {

        minIndex = i;

        for (var j = i + 1; j < len; j++) {

            if (arr[j] < arr[minIndex]) {     //寻找最小的数

                minIndex = j;                 //将最小数的索引保存

            }

        }

        temp = arr;

        arr = arr[minIndex];

        arr[minIndex] = temp;

    }

    return arr;

}

插入排序（Insertion Sort）
插入排序须知：插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。当然，如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌，那估计这辈子你对插入排序的算法都不会产生任何兴趣了。。。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。对于这种算法，得了懒癌的我就套用教科书上的一句经典的话吧：感兴趣的同学可以在课后自行研究。。。

插入排序动图演示：

插入排序JavaScript代码实现：

[JavaScript] 纯文本查看 复制代码

function insertionSort(arr) {

    var len = arr.length;

    var preIndex, current;

    for (var i = 1; i < len; i++) {

        preIndex = i - 1;

        current = arr;

        while(preIndex >= 0 && arr[preIndex] > current) {

            arr[preIndex+1] = arr[preIndex];

            preIndex--;

        }

        arr[preIndex+1] = current;

    }

    return arr;

}

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

希尔排序JavaScript代码实现：

[JavaScript] 纯文本查看 复制代码

function shellSort(arr) {

    var len = arr.length,

        temp,

        gap = 1;

    while(gap < len/3) {          //动态定义间隔序列

        gap =gap*3+1;

    }

    for (gap; gap > 0; gap = Math.floor(gap/3)) {

        for (var i = gap; i < len; i++) {

            temp = arr;

            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {

                arr[j+gap] = arr[j];

            }

            arr[j+gap] = temp;

        }

    }

    return arr;

}

归并排序（Merge Sort）

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

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第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语言精粹》的第四章里提到了递归问题。对我之前的疑问进行了解答：

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代码实现：

[JavaScript] 纯文本查看 复制代码

function mergeSort(arr) {  //采用自上而下的递归方法

    var len = arr.length;

    if(len < 2) {

        return arr;

    }

    var middle = Math.floor(len / 2),

        left = arr.slice(0, middle),

        right = arr.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;

}

JS家的十大经典排序算法（下）：http://bbs.itheima.com/forum.php?mod=viewthread&tid=331290

文／不是小羊的肖恩（简书作者）
原文链接：http://www.jianshu.com/p/1b4068ccd505

5.gif (327.21 KB, 下载次数: 80)

6.gif (1.91 MB, 下载次数: 69)

7.gif (264.41 KB, 下载次数: 66)

8.gif (194.43 KB, 下载次数: 109)

作者: 王磊_csOE4 时间: 2016-10-18 10:45
感谢大神的分享。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2