六种排序算法的JavaScript实现以及总结

六种排序算法的JavaScript实现以及总结

最近几天在系统的复习排序算法,之前都没有系统性的学习过,也没有留下过什么笔记,所以很快就忘了,这次好好地学习一下。

首先说明为了减少限制,以下代码通通运行于Node V8引擎而非浏览器,源码在我的GitHub,感兴趣的话可以下载来然后运行试试。

为了方便对比各个排序算法的性能,这里先写了一个生成大规模数组的方法——generateArray:

exports.generateArray = function(length) {
    let arr = Array(length);
    for(let i=0; i<length; i++) {
        arr[i] = Math.random();
    }
    return arr;
};

只需要输入数组长度,即可生成一个符合长度要求的随机数组。

一、冒泡排序

冒泡排序也成为沉淀排序(sinking sort),冒泡排序得名于其排序方式,它遍历整个数组,将数组的每一项与其后一项进行对比,如果不符合要求就交换位置,一共遍历n轮,n为数组的长度。n轮之后,数组得以完全排序。整个过程符合要求的数组项就像气泡从水底冒到水面一样泡到数组末端,所以叫做冒泡排序。

冒泡排序是最简单的排序方法,容易理解、实现简单,但是冒泡排序是效率最低的排序算法,由于算法嵌套了两轮循环(将数组遍历了n遍),所以时间复杂度为O(n^2)。最好的情况下,给出一个已经排序的数组进行冒泡排序,时间复杂度也为O(n)。

JavaScript实现(从小到大排序):

function bubbleSort(arr) {
    //console.time('BubbleSort');
    // 获取数组长度,以确定循环次数。
    let len = arr.length;
    // 遍历数组len次,以确保数组被完全排序。
    for(let i=0; i<len; i++) {
        // 遍历数组的前len-i项,忽略后面的i项(已排序部分)。
        for(let j=0; j<len - 1 - i; j++) {
            // 将每一项与后一项进行对比,不符合要求的就换位。
            if(arr[j] > arr[j+1]) {
                [arr[j+1], arr[j]] = [arr[j], arr[j+1]];
            }
        }
    }
    //console.timeEnd('BubbleSort');
    return arr;
}

代码中的注释部分的代码都用于输出排序时间,供测试使用,下文亦如是。

评论 抢沙发

表情
  1. #1

    来自河北沧州的用户 7天前
    小白我没有看懂hhh

  2. #2

    来自四川成都的用户 8天前
    感谢您的文章,又学到了不少东西

  3. #3

    来自北京朝阳的用户 10天前
    学习了, 总结的很细很棒, 赞

  4. #4

    来自辽宁沈阳的用户 19天前
    大神 听说你又有才 人又帅,明明可以靠脸吃饭,可是你偏要靠才华,鼓励师都被你撩了我们怎么办

  5. #5

    来自海南海口的用户 21天前
    贼详细,收藏了

  6. #6

    来自福建福州的用户 25天前
    优秀,先收藏了。

  7. #7

    来自江苏玄武的用户 27天前
    信息量好大