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个数字倒序下排序

在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中，这三者排序的效率都是差不多的。选择排序稍快一点。