ccDocs

外观

导航栏

冒泡排序 简单 ​

上图为冒泡排序四种方法性能对比

  • 对比函数代码
    • 部分有序
    • 完全无序
js
const test = (sortFn) => {
    let array = []
    // 向数组中写入10 000 数据， 其中前1000个数据倒序， 后9000个数据顺序

    for(let i = 0; i < 10000; i++) {
        if(i < 1000) {
            array[i] = 1000 - i
        }else {
            array[i] = i
        }
    }

    console.log('=============')

    let start = new Date() - 0
    sortFn(array)

    console.log('部分有序的情况', sortFn.name, new Date() - start)
    shuffle(array)

    start = new Date() - 0
    sortFn(array)

    console.log('完全无序的情况', sortFn.name, new Date() - start)
}

1. 正常方法 ​

1.1 思路 ​

  • 从第一个元素开始，比较相邻的两个元素，如果前一个比后一个大，则交换位置
  • 对每一对相邻元素做同样的操作，从开始第一对到结尾最后一对，这样最后的元素就是最大的数

1.2 代码 ​

js
// 正常做法

const bubbleSort = (arr) => {
    let n = arr.length;

    for (let i = 1; i < n;i++) {
        for(let j = 0; j < n -1; j++) {
            if(arr[j] > arr[j + 1]) {
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]] // 交换位置
            }
        }
    }
}

const arr = [1,3,1,5,432,3,66,32]
bubbleSort(arr)
console.log(arr)

1.3 结果 ​

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：稳定

2. 标志位优化 ​

2.1 思路 ​

  • 如果某次循环没有发生交换，说明已经排好序了，可以直接退出循环

2.2 代码 ​

js
const bubbleSort2 = (arr) => {
    let n = arr.length;
    for(let i = 1;i < n;i++){
        let hasSort = true;
        for(let j = 0; j < n - 1;j++){
            if(arr[j] > arr[j + 1]){
                [arr[j], arr[j + 1]] = [arr[j + 1],arr[j]] // 交换位置
                hasSort = false
            }
        }

        if(hasSort){
            break;
        }
    }
}

const arr1 = [1,3,1,5,432,3,66,32]
bubbleSort2(arr1)
console.log(arr1)

2.3 结果 ​

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：稳定

3. 最大数下沉 ​

3.1 思路 ​

  • 每次循环都记录最后一次交换的位置，下次循环只循环到这个位置
  • 优化：如果某次循环没有发生交换，说明已经排好序了，可以直接退出循环

3.2 代码 ​

js
const bubbleSort3 = (arr) => {
    let n = arr.length, k = n - 1, swapPos = 0;

    for(let i = 1; i < n; i++) {
        let hasSort = true

        for(let j= 0;j < k; j++) {
            if(arr[j] > arr[j+1]) {
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]] // 交换位置
                hasSort = false;
                swapPos = j; // 记录交换位置，下次只循环到上一次交换位置
            }
        }

        if(hasSort) break

        k = swapPos; // 重写内部循环最后边界
    }
}

const arr2 = [1,3,1,5,432,3,66,32]
bubbleSort3(arr2)
console.log(arr2)

3.3 结果 ​

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：稳定

4. 鸡尾酒排序 ​

4.1 思路 ​

  • 鸡尾酒排序，也就是定向冒泡排序， 鸡尾酒搅拌排序， 搅拌排序（也可以视作选择排序的一种变形）， 涟漪排序， 来回排序或快乐小时排序， 是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
  • 从低到高然后从高到低，如此往复直到排序完成
  • 优化：如果某次循环没有发生交换，说明已经排好序了，可以直接退出循环

4.2 代码 ​

js
const cocktailSort = (arr) => {
    let left, right, index, i;
    left = 0; // 数组起始索引
    right = arr.length - 1; // 数组索引最大值
    index = left; // 临时变量

    // 判断数组中是否有多个元素
    while (right > left) {
        let isSorted = false;
        // 每一次进入while循环， 都会找出相应范围内最大最小的元素并分别放到相应的位置
        // 大的排到后面
        for (i = left; i < right; i++) { // 从左向右扫描
            if(arr[i] > arr[i + 1]) {
                [arr[i],arr[i + 1]] = [arr[i + 1], arr[i]]
                index = i; // 记录当前索引
                isSorted = true
            }
        }

        right = index; // 记录最后一个交换的位置

        // 小的放在前面
        for(i = right; i > left; i--) { // 从最后一个交换位置从右向左扫描
            if(arr[i] < arr[i - 1]) {
                [arr[i],arr[i - 1]] = [arr[i - 1], arr[i]]
                index = i;
                isSorted = true;
            }
        }

        left = index; // 记录最后一个交换的位置

        if(!isSorted) {
            break;
        }
    }
}


const arr3 = [1,3,1,5,432,3,66,32]
cocktailSort(arr3)
console.log(arr3,'arr3')

4.3 结果 ​

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：稳定