六种排序算法的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

    来自上海徐汇的用户 2天前
    点赞,前排摸大佬沾点技术

  2. #2

    来自重庆万州的用户 11天前
    先Mark后看(●◡●)ノ

  3. #3

    来自湖北武汉的用户 12天前
    比我还好 一年的数据库 一年的后端 一点的前端 现在搞得什么都没有学号学精

  4. #4

    来自安徽合肥的用户 19天前
    优秀,加油!

  5. #5

    来自四川成都的用户 20天前
    good

  6. #6

    来自河北石家庄的用户 21天前
    虽然很多还看不懂 但是很赞

  7. #7

    来自四川成都的用户 28天前
    可以说是相当详细了