数据结构与算法JavaScript描述（10） —— 基本排序算法（Sort）

1. 冒泡排序算法

是最慢的排序算法之一，但也是一种最容易实现的排序算法。
按照升序排列：依次比较相邻的数据，较小的值冒泡到左侧，较大的值冒泡到右侧
按照降序排列：依次比较相邻的数据，较小的值冒泡到右侧，较大的值冒泡到左侧

实现：

function bubbleSort(data) {
    const len = data.length
    for (let outer = len; outer >= 2; outer--) {
        for (let inner = 0; inner <= outer - 1; inner++) {
            if (data[inner] > data[inner + 1]) {
                // 若前一个值大于后一个值，则交换两个值
                [data[inner], data[inner + 1]] = [data[inner + 1], data[inner]]
            }
        }
    }
}

// test
const a = [72, 54, 59, 30, 31, 78, 2, 77, 82, 72]
bubbleSort(a)
console.log(a)  // [2, 30, 31, 54, 59, 72, 72, 77, 78, 82]

下图展示了上例中的数据进行冒泡排序的过程（红框里的数据为我们为了观察冒泡过程而设定的两个特定值）

2. 选择排序

从数组的开头开始，将第一个元素和其他元素进行比较。检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据便完成了排序。

实现：

function selectionSort(data) {
    const len = data.length
    let min 
    for (let outer = 0; outer < len - 1; outer++) {
        min = outer
        for (let inner = outer + 1; inner < len; inner++) {
            if (data[inner] < data[min]) {
                min = inner
            }
        }
        [data[outer], data[min]] = [data[min], data[outer]]
    }
}

// test
const b = [72, 54, 59, 30, 31, 78, 2, 77, 82, 72]
selectionSort(b)
console.log(b)  // [2, 30, 31, 54, 59, 72, 72, 77, 78, 82]

下图展示了上例中的数据进行选择排序的过程（红框里的数据为每次循环中最小的元素）

插入排序

插入排序类似于人类按数字或字母顺序对数据进行排序。
插入排序有两个循环。外循环将数组元素挨个移动，而内循环则对外循环选中的元素及它后面的那个元素进行比较。如果外循环中选中的元素比内循环中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置。
步骤：
（1）从第一个元素开始，该元素可以认为已经被排序
（2）取出下一个元素，在已经排序的元素序列中从后向前扫描
（3）如果该元素（已排序）大于新元素，将该元素移到下一位置
（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
（5）将新元素插入到该位置后
（6）重复步骤2~5

实现：

方法一：

function insertSort(data) {
    const len = data.length
    let temp, inner
    // 外循环：待排序的数据
    for (let outer = 1; outer < len; outer++) {
        temp = data[outer]
        inner = outer
        while(inner > 0 && data[inner - 1] >= temp) {
            // 内循环：已完成排序的数据
            // 比较待排序和已完成排序数据（从右至左），如果已排序的数据大于temp，则已排序数据向右移一位
            data[inner] = data[inner - 1]
            inner--
        }
        // 空出来的 原已排序的位置 放置待排序的数据
        data[inner] = temp
    }
}

// test
const c = [72, 54, 59, 30, 31, 78, 2, 77, 82, 72]
insertSort(c)
console.log(c)  // [2, 30, 31, 54, 59, 72, 72, 77, 78, 82]

方法二：

function insertSort(data) {
    const len = data.length
    // 外循环：待排序的数据
    for (let outer = 1; outer < len; outer++) {
        // 内循环：已完成排序的数据
        for (let inner = 0; inner < outer; inner++) {
            // 如果外循环小于内循环（待排序小于已排序），则数组元素将会向右移动
            if (data[inner] > data[outer]) {
                // 将待排序数据插入到已排序的位置
                data.splice(inner, 0, data[outer])
                // 删除原先待排序的数据
                data.splice(outer + 1, 1)
            }
        }
    }
}

// test
const d = [72, 54, 59, 30, 31, 78, 2, 77, 82, 72]
insertSort(d)
console.log(d)  // [2, 30, 31, 54, 59, 72, 72, 77, 78, 82]

下图展示了上例中的数据进行插入排序的过程（红框里的数据为每次外循环执行完后被插入的元素）

4. 三种基本排序的效率

（1）首先，实现一个测试平台，进行测试数据的生成。

// 测试平台
class CArray {

    constructor(count) {
        this.data = []
        this.count = count
    }

    setData() {
        for (let i = 0; i < this.count; i++) {
            this.data[i] = Math.floor(Math.random() * (this.count + 1))
        }
    }
}

（2）声明排序算法

// 冒泡排序
function bubbleSort(data) {
    const len = data.length
    for (let outer = len; outer >= 2; outer--) {
        for (let inner = 0; inner <= outer - 1; inner++) {
            if (data[inner] > data[inner + 1]) {
                // 若前一个值大于后一个值，则交换两个值
                [data[inner], data[inner + 1]] = [data[inner + 1], data[inner]]
            }
        }
    }
}

// 选择排序
function selectionSort(data) {
    const len = data.length
    let min 
    for (let outer = 0; outer < len - 1; outer++) {
        min = outer
        for (let inner = outer + 1; inner < len; inner++) {
            if (data[inner] < data[min]) {
                min = inner
            }
        }
        [data[outer], data[min]] = [data[min], data[outer]]
    }
}

// 插入排序
function insertSort(data) {
    const len = data.length
    let temp, inner
    // 外循环：待排序的数据
    for (let outer = 1; outer < len; outer++) {
        temp = data[outer]
        inner = outer
        while(inner > 0 && data[inner - 1] >= temp) {
            // 内循环：已完成排序的数据
            // 比较待排序和已完成排序数据（从右至左），如果已排序的数据大于temp，则已排序数据向右移一位
            data[inner] = data[inner - 1]
            inner--
        }
        // 空出来的 原已排序的位置 放置待排序的数据
        data[inner] = temp
    }
}

（3）进行测试

var arr = new CArray(1000)
arr.setData()
var data1 = arr.data
var data2 = data1.concat()
var data3 = data1.concat()
// 冒泡排序
console.time('bubbleSort')
bubbleSort(data1)
console.log(data1)
console.timeEnd('bubbleSort') 

// 选择排序
console.time('selectionSort')
bubbleSort(data2)
console.log(data2)
console.timeEnd('selectionSort')

// 插入排序
console.time('insertSort')
bubbleSort(data3)
console.log(data3)
console.timeEnd('insertSort')

多执行几次测试代码，我们可以看到测试结果

bubbleSort: 29.56201171875ms
selectionSort: 24.248046875ms
insertSort: 15.97119140625ms

bubbleSort: 25.317138671875ms
selectionSort: 20.39404296875ms
insertSort: 13.625ms

bubbleSort: 28.112060546875ms
selectionSort: 21.611083984375ms
insertSort: 16.8720703125ms

我们可以得出如下结论：

效率： 插入排序 > 选择排序 > 冒泡排序

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,013评论 6赞 481
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,205评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 152,370评论 0赞 342
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,168评论 1赞 278
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,153评论 5赞 371
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,954评论 1赞 283
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,271评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,916评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,382评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,877评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,989评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,624评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,209评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,199评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,418评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,401评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,700评论 2赞 345