JavaScript 编写排序算法:冒泡排序、选择排序、插入排序

JavaScript 编写排序算法:

  • 冒泡排序
  • 选择排序
  • 插入排序
  • 总结

交换两个元素的位置

const swap = (arr, i, j) => {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

冒泡排序

每外循环一次,实现当前范围内最大值找出放到右边位置。子循环内每次相邻两个比较,大者移动到后面。

// 冒泡 
const bubbleSort = (arr) => { 
    for (let i = arr.length - 1; i > 0; i--) {
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1)
            }
        }
    }
    console.log(arr)
};
// 改进后的冒泡  如果内循环没有发生或一次交换,则数组已经有序了
const modifiedBubbleSort = (arr) => {
    let k = 0;
    for (let i = arr.length - 1; i > 0; i--) {
        k = 0;
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1)
                k = 1;
            }
        }
        if (k === 0) {  
            return arr;
        }
    }
    console.log(arr)
};

选择排序

每外循环一次,找到当前范围最小值放到当前范围第一个位置,依次选择最小值放在第一位,第二位……

const selectionSort =(arr) => {
    let minIndex = 0;
    for (let i = 0; i< arr.length -1; i++) {
        minIndex = i;
        for (let j = i + 1; j< arr.length; j++) {
            if (arr[minIndex] > arr[j]) {
                 minIndex = j;
            }
        }
        if (i !== minIndex) {
            swap(arr, i, minIndex)
        }
    }
    console.log(arr)
}

插入排序

假定以一个已经排好序了,第二应该插入到第一个的前面还是后面呢,第一二已经排好序了,第三个应该插入到哪个位置呢?

temp 表示即将插入的值,前者大则一个一个往后移。采用赋值方式,不用交换值。

const insertionSort =(arr) => {
    let temp = null;
    for (let i = 1; i< arr.length; i++) {
        let j = i, temp = arr[i];
        for (let j = i; j > 0 && arr[j-1] > temp; j--) {
            arr[j] = arr[j-1];
        }
        arr[j] = temp;
    }
    console.log(arr)
}

或者:前者大则两者交换。 不使用 temp 空间,多少会增加点运算时间。

const insertionSort2 =(arr) => {
    let temp = null;
     for (let i = 1; i < length; i++) {
        for (let j = i; j > 0 && arr[j-1] > arr[j]; j--) {
           swap(arr, j-1, j);
        }
    }
    console.log(arr)
}

测试

要排序的数组为:倒序的 9999 ~ 0,共有10000个数字。

let beforeArray = [];
for (let i = 0; i < 10000; i++) { 
    beforeArray.unshift( i ); 
}

在 chrome 浏览器,某次的测试结果:(粗略测试,仅做参考)

10000个数字倒序下排序
10000个数字倒序下排序

在20000个数字倒序下,排序花费时间是:

20000个数字倒序下排序
20000个数字倒序下排序

总结

  • 冒泡排序:时间 O(N^2),空间 O(1),稳定。
  • 选择排序:时间 O(N^2),空间 O(1),不稳定。
  • 插入排序:时间 O(N^2),空间 O(1),稳定。

选择排序进行互换可能跨越多个元素,所以不稳定。
比如[5,3,5,4,2,1], 第一轮最小元素1和第一个5交换了,第一个5就在第二个5之后了。

在JavaScript中,这三者排序的效率都是差不多的。选择排序稍快一点。

有问题反馈加微信:mue233 私聊送一本电子书,绝对受益良多! 微信公众号:慕意,分享创业、使用的软件和教程~
知识星球精选推荐 » JavaScript 编写排序算法:冒泡排序、选择排序、插入排序