js 排序算法

排序算法时间复杂度

时间复杂度

冒泡排序

• 如果有 n 个数进行排序，需要循环 n-1 次
• 每一次循环，从第一位开始进行相邻两个数的比较，将较大的数放在后面
• 依次比较相邻的两个数，一次循环后，最后的数为最大的 即归位
• 下一次循环只需比较尚未归位的前 n-1 个数 故内循环 -i

const bubbleSort = arr => {
    const len = arr.length;
    for (let i=0; i<len-1; i++) { // n 个数排序，循环 n-1 次
        for (let j=0; j<len-i-1; j++) { // 从第一位开始比较直到最后一个尚未归位的数
            if (arr[j] > arr[j+1]) { // 比较大小并交换
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }
    return arr;
}

选择排序

• 如果有 n 个数进行排序，需要循环 n-1 次。选择排序是不稳定的排序方法
• 第一次从所有的数中选出最小的数，放在第一位
• 然后再从剩余的未排序的序列中选出最小的数，放在已排序的序列的末尾

const selectionSort = arr => {
    const len = arr.length;
    let min;
    for (let i=0; i<len-1; i++) { // n 个数排序，循环 n-1 次
        min = i;
        for (let j=i+1; j<len; j++) { // 循环未排序的序列
            if (arr[j] < arr[min]) {
                min = j; // 记录最小值的位置
            }
        }
        [arr[i], arr[min]] = [arr[min], arr[i]];
    }
    return arr;
}

插入排序

• 从第一个元素开始，该元素可以认为已经被排序
• 每一次循环，取出下一个元素，在已经排序的元素序列中从后向前扫描
• 如果该元素（已排序）大于新元素，将该元素移到下一位置，直到找到已排序的元素小于或等于新元素的位置，插入新元素
• 进行下一次循环

const insertionSort = arr => {
    const len = arr.length;
    for (let i=1; i<len; i++) {
        for (let j=i-1; j>-1 && arr[j]>arr[j+1]; j--) {
            let flag = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = flag;
        }
    }
    return arr;
}

const insertionSort = arr => {
    const len = arr.length;
    let flag;
    for (let i=1; i<len; i++) {
        let j = i - 1;
        flag = arr[i];
        while (j>-1 && arr[j]>flag) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = flag;
    }
    return arr;
} 

希尔排序

• 将要排序的数组按一定的步长 d1 分成若干组，每组中记录的下标相差 d1，组内进行插入排序
• 取 d2<d1，重复上述分组和排序操作
• 直到 di=1，整个要排序的数被分成一组，排序结束

通常第一次步长为要排序数组的一半，以后每次减半，直到步长为1

const shellSort = arr => {
    const len = arr.length;
    for (let step=Math.floor(len/2); step>0; step=Math.floor(step/2)) {
        for (let i=step; i<len; i++) {
            for (let j=i-step; j>-1 && arr[j]>arr[j+step]; j-=step) {
                let flag = arr[j];
                arr[j] = arr[j+step];
                arr[j+step] = flag;
            }
        }
    }
    return arr;
}

快速排序

• 挑选一个基准数，通常为数组的第一位
• 通过一趟快速排序，将要排序的数据分割为两部分，一部分比基准数小，一部分比基准数大
• 按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行

const quickSort = arr => {
    const len = arr.length;
    if (len < 2) {
        return arr;
    }
    const base = arr[0]; // 基准数
    const left = [];
    const right = [];
    for (let i=1; i<len; i++) {
        if (arr[i] < base) { // 小于基准数的数组
            left.push(arr[i]);
        } else { // 大于基准数的数组
            right.push(arr[i]);
        }
    }
    return [...quickSort(left), base, ...quickSort(right)]; // 递归
}

未完待续~