1.冒泡排序法

1.1 概念

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从 Z 到 A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

1.2 原理示意图

1.3 代码

const arr = [5, 2, 7, 8, 34, 7, 39, 12, 56, 9, 1];

function bubbleSort(arr) {
    const len = arr.length;
    // 外层循环i控制比较的轮数
    for (let i = 0; i < len; i++) {
        // 里层循环控制每一轮比较的次数j，arr[i] 只用跟其余的len - i个元素比较
        for (let j = 1; j < len - i; j++) {
            // 若前一个元素"大于"后一个元素，则两者交换位置
            if (arr[j - 1] > arr[j]) {
                [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
            }
        }
    }
    return arr;
}

console.log(bubbleSort(arr)); // [1, 2,  5,  7,  7, 8, 9, 12, 34, 39, 56]

改进的冒泡排序法：

function bubbleSort(arr) {
    let temp = null,
        flag = 1;
    const len = arr.length;
    for (let i = 0; i <= len - 1 && flag === 1; i++) {
        flag = 0;
        for (let j = 0; j < len - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                flag = 1; // 发生数据交换flag置为1
            }
        }
    }
    return arr;
}

2.插入排序法

2.1 概念

一般也被称为直接插入排序（Insert Sort）。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

插入排序是指在待排序的元素中，假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第 n 个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

2.2 原理示意图

插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌 。

2.3 代码

const arr = [5, 2, 7, 8, 34, 7, 39, 12, 56, 9, 1];

function insertSort(arr) {
    const handle = [arr[0]],
        len = arr.length;
    for (let i = 1; i <= len - 1; i++) {
        const current = arr[i];
        for (var j = handle.length - 1; j >= 0; j--) {
            if (current > handle[j]) {
                handle.splice(j + 1, 0, current);
                break;
            }
            if (j === 0) {
                handle.unshift(current);
            }
        }
    }
    return handle;
}

console.log(insertSort(arr)); // [1, 2,  5,  7,  7, 8, 9, 12, 34, 39, 56]

优化的插入排序法：

//将arr[]按升序排列，插入排序法
function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        //将arr[i]插入到arr[i-1]，arr[i-2]，arr[i-3]……之中
        for (let j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1]) {
                [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
            }
        }
    }
    return arr;
}

3.快速排序法

3.1 概念

快速排序（Quick Sort）是对冒泡排序的一种改进。

快速排序由 C. A. R. Hoare 在 1960 年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

3.2 原理示意图

3.3 代码

const arr = [5, 2, 7, 8, 34, 7, 39, 12, 56, 9, 1];

function quickSort(arr) {
    // 4.结束递归（当ary小于等于一项，则不用处理）
    if (arr.length <= 1) {
        return arr;
    }
    // 1. 找到数组的中间项，在原有的数组中把它移除
    const middleIndex = Math.floor(arr.length / 2);
    const middle = arr.splice(middleIndex, 1)[0];
    // 2. 准备左右两个数组，循环剩下数组中的每一项，比当前项小的放到左边数组中，反之放到右边数组中
    const leftArr = [],
        rightArr = [];
    for (let i = 0; i < arr.length; i++) {
        const current = arr[i];
        current < middle ? leftArr.push(current) : rightArr.push(current);
    }
    // 3. 递归方式让左右两边的数组持续这样处理，一直到左右两边都排好序为止。
    //（最后让左边+中间+右边拼接成最后的结果）
    return quickSort(leftArr).concat(middle, quickSort(rightArr));
}

console.log(bubbleSort(arr)); // [1, 2,  5,  7,  7, 8, 9, 12, 34, 39, 56]

对于这段代码的分析： 缺点：

• 获取基准点使用了一个 splice 操作，在 js 中 splice 会对数组进行一次拷贝的操作，而它最坏的情况下复杂度为 O(n)，而 O(n)代表着针对数组规模的大小进行了一次循环操作。
• 首先我们每次执行都会使用到两个数组空间，产生空间复杂度。
• concat 操作会对数组进行一次拷贝，而它的复杂度也会是 O(n)
• 对大量数据的排序来说相对会比较慢

优点：

• 代码简单明了，可读性强，易于理解
• 非常适合用于面试笔试题

那么我们接下来用另外一种方式去实现快速排序

快速排序的实现方式二

从上面这张图，我们用一个指针 i 去做了一个分割

• 初始化 i = -1
• 循环数组，找到比支点小的数就将 i 向右移动一个位置，同时与下标 i 交换位置
• 循环结束后，最后将支点与 i+1 位置的元素进行交换位置
• 最后我们会得到一个由 i 指针作为分界点，分割成从下标 0-i，和 i+1 到最后一个元素。

下面我们来看一下代码的实现，整个代码分成三部分，数组交换，拆分，qsort（主函数）三个部分

先写最简单的数组交换吧，这个大家应该都懂

function swap(A, i, j) {
    const t = A[i];
    A[i] = A[j];
    A[j] = t;
}

下面是拆分的过程，其实就是对指针进行移动，找到最后指针所指向的位置

/**
 *
 * @param {*} A 数组
 * @param {*} p 起始下标
 * @param {*} r 结束下标 + 1
 */
function dvide(A, p, r) {
    // 基准点
    const pivot = A[r - 1];

    // i初始化是-1，也就是起始下标的前一个
    let i = p - 1;

    // 循环
    for (let j = p; j < r - 1; j++) {
        // 如果比基准点小就i++，然后交换元素位置
        if (A[j] <= pivot) {
            i++;
            swap(A, i, j);
        }
    }
    // 最后将基准点插入到i+1的位置
    swap(A, i + 1, r - 1);
    // 返回最终指针i的位置
    return i + 1;
}

主程序主要是通过递归去重复的调用进行拆分，一直拆分到只有一个数字。

/**
 *
 * @param {*} A  数组
 * @param {*} p  起始下标
 * @param {*} r  结束下标 + 1
 */
function qsort(A, p, r) {
    r = r || A.length;
    if (p < r - 1) {
        const q = divide(A, p, r);
        qsort(A, p, q);
        qsort(A, q + 1, r);
    }
    return A;
}

完整代码

function swap(A, i, j) {
    const t = A[i];
    A[i] = A[j];
    A[j] = t;
}

/**
 *
 * @param {*} A 数组
 * @param {*} p 起始下标
 * @param {*} r 结束下标 + 1
 */
function divide(A, p, r) {
    const x = A[r - 1];
    let i = p - 1;

    for (let j = p; j < r - 1; j++) {
        if (A[j] <= x) {
            i++;
            swap(A, i, j);
        }
    }

    swap(A, i + 1, r - 1);

    return i + 1;
}

/**
 *
 * @param {*} A 数组
 * @param {*} p 起始下标
 * @param {*} r 结束下标 + 1
 */
function qsort(A, p = 0, r) {
    r = r || A.length;

    if (p < r - 1) {
        const q = divide(A, p, r);
        qsort(A, p, q);
        qsort(A, q + 1, r);
    }

    return A;
}

总结

第二段的排序算法我们减少了两个 O(n)的操作，得到了一定的性能上的提升，而第一种方法数据规模足够大的情况下会相对来说比较慢一些，快速排序在面试中也常常出现，为了笔试更好写一些可能会有更多的前端会选择第一种方式，但也会有一些为难人的面试官提出一些算法中的问题。而在实际的项目中，我觉得第一种方式可以少用。

4.十大排序空间复杂度和时间复杂度：

信息

作者：青颜的天空 链接：https://juejin.cn/post/6844904177504616461 来源：稀土掘金 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。