• 经常会使用到的三种排序方法：冒泡排序、选择排序和快速排序

复杂度区别

冒泡、选择排序： 时间O(n²) 空间O(1)
快速排序： 时间O(nlogn) 空间O(logn)

冒泡排序

let bubbleSort = (array) => {
    for(let i = 0; i < array.length; i++){
        for(let j = i; j < array.length; j++){
            if(array[i] > array[j]){
                let temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
    return array;
}

选择排序

let selectSort = (array) => {
    for(let i = 0; i < array.length; i++){
        let minIndex = i
        for(let j = i + 1; j < array.length; j++){
            if(array[j] < array[minIndex]){
                minIndex = j
            }
        }
        let temp = array[i]
        array[i] = array[minIndex]
        array[minIndex] = temp
    }
    return array
}

快速排序

let quickSort = (array, l, r) => {
    if(l < r){
        let i = l, j = r, temp = array[i]
        while(i < j){
            while(i < j && array[j] > temp){
                j--
            }
            if(i < j){
                array[i] = array[j]
                i++
            }
            while(i < j && array[i] < temp){
                i++
            }
            if(i < j){
                array[j] = array[i]
                j--
            }
            array[i] = temp
            quickSort(array, l, i - 1)
            quickSort(array, i + 1, r)
        }
    }
}

测试：

let nums = [20, 10, 9, 8, 30, 65, 70, 0, 100];

let bubble = bubbleSort(nums.slice());
let quick = nums.slice();
quickSort(quick, 0, quick.length-1);
let select = selectSort(nums.slice());

console.log(`\nnums: ${nums}`);
console.log(`\nbubble: ${bubble}`);
console.log(`\nquick: ${quick}`);
console.log(`\nselect: ${select}`);