常用排序算法(一)

冒泡排序

描述：

一次比较相邻的两个元素，如果它们顺序错误就交换位置；每次循环后最后的元素会是我们期待的数（最大或最小）；针对所有元素重复以上步骤，除了第一个。直到两层循环全部执行完毕，排序完成。

时间复杂度：O(n²)

空间复杂度：O(1)

代码实现：

function bubbleSort(arr) {
    const len = arr.length;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                arr[j] = [arr[j + 1], arr[j + 1] = arr[j]][0];
            }
        }
    }
    return arr;
}

选择排序

描述：

首先在未排序队列中找出最大（小）的元素，存放到已排序队列中的起始位置；然后再从剩余未排序队列中继续找出最大（小）的元素，存放到已排序队列的末尾；以此类推，直到排序完毕。

时间复杂度：O(n²)

空间复杂度：O(1)

代码实现：

function selectionSort(arr) {
    const len = arr.length;
    let minIndex;
    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;   // 保存最小（大）值得索引
            }
        }
        arr[i] = [arr[minIndex], arr[minIndex] = arr[i]][0];
    }
    return arr;
}

插入排序

描述：

将第一个元素看做已排序队列，剩余元素为未排序队列；从未排序队列取出一个元素，在已排序队列从后向前扫描，若该元素（已排序）大（小）于新元素（未排序队列取出的），则将该元素移到下一位置；直到该元素小（大）于或者等于新元素，将新元素插入到位置。重复以上步骤直到所有元素排序完成。

时间复杂度：O(n²)

空间复杂度：O(1)

代码实现：

function insertSort(arr) {
    const len = arr.length;
    let preIndex, current;
    for (let i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

快速排序

描述：

选择一个合适的元素a（一般是第一个元素）作为排序基准，将未排序队列中比a小和比a大的分别放在两侧，将两侧的子数组重复以上步骤（递归），直到最后只剩下一个元素（递归出口），排序完成。

时间复杂度：O(n㏒₂n)

空间复杂度：O(n㏒₂n)

代码实现：

function quickSort(arr) {
    // 递归出口
    if (arr.length <= 1) return arr;
    // 基准（可以随意选择）
    let number = arr[0];
    let left = [], right = [];
    for (let i = 1; i < arr.length; i++) {
        arr[i] <= number ? left.push(arr[i]) : right.push(arr[i]);
    }
    return quickSort(left).concat([number], quickSort(right));
}