排序算法

发表于 2023-04-01 更新于 2023-07-10 分类于算法阅读次数：

本文字数： 4.5k 阅读时长 ≈ 4 分钟

排序算法	时间复杂度	空间复杂度	稳定性
冒泡排序	O(n^2)	O(1)	稳定
插入排序	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(1)	不稳定
归并排序	O(n(log n)	O(n)	稳定
快速排序	O(n(log n))	O(n(log n))	不稳定
堆排序	O(n(log n))	O(1)	不稳定
希尔排序	O(n(log n))	O(1)	不稳定

1. 冒泡排序

冒泡排序在每次冒泡操作时会比较相邻的两个元素，看是否满足大小关系要求，不满足就将它俩互换。一直迭代到不再需要交换，也就是排序完成。

const bubbleSort = function(arr) {
    const len = arr.length
    let flag = false
    if (len < 2) return arr
    for (let i = 0; i < len; i++) {
        flag = false // 提前退出冒泡循环的标志
        for (let j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
                flag = true // 表示有数据交换
            }
        }
        if (!flag) break // 没有数据交换，提前退出
    }
    return arr
}

2. 插入排序

插入排序顾名思义，对于未排序的数据，在已排序的序列中从后往前扫描，找到相应的位置进行插入，保持已排序序列中元素一直有序。从 i 等于 1 开始遍历，拿到当前元素 curr，与前面的元素进行比较。如果前面的元素大于当前元素，就把前面的元素和当前元素进行交换，不断循环直到未排序序列中元素为空，排序完成。

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

3. 选择排序

选择排序和插入排序有些类似，也分已排序序列和未排序序列。

但是选择排序是将最小的元素存放在数组起始位置，再从剩下的未排序的序列中寻找最小的元素，然后将其放到已排序的序列后面。以此类推，直到排序完成。

const selectSort = function(arr) {
    const len = arr.length
    let temp, 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
            }
        }
        temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    }
    return arr
}

4. 归并排序

分治法典型应用，分治算法思想很大程度上是基于递归的，也比较适合用递归来实现。

1	处理过程是由下到上的，先处理子问题，然后再合并。

分而治之。一般分为以下三个过程：

分解：将原问题分解成一系列子问题。
解决：递归求解各个子问题，若子问题足够小，则直接求解。
合并：将子问题的结果合并成原问题。

归并排序就是将待排序数组不断二分为规模更小的子问题处理，再将处理好的子问题合并起来，这样整个数组就都有序了。

const mergeSort = function(arr) {
    const merge = (left, right) => {
        const result = []
        let i = 0, j = 0
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                result.push(left[i++])
            } else {
                result.push(right[j++])
            }
        }
        while (i < left.length) {
            result.push(left[i++])
        }
        while (j < right.length) {
            result.push(right[j++])
        }
        return result
    }

    if (arr.length === 1) { return arr } // 注意这句
    const mid = Math.floor(arr.length / 2)
    const left = arr.slice(0, mid)
    const right = arr.slice(mid, arr.length)
    return merge(mergeSort(left), mergeSort(right))
}

5. 快速排序

快速排序也是分治法的应用，处理过程是由上到下的，先分区，然后再处理子问题。快速排序通过遍历数组，将待排序元素分隔成独立的两部分，一部分记录的元素均比另一部分的元素小，则可以分别对这两部分记录的元素继续进行排序，直到排序完成。

这就需要从数组中挑选出一个元素作为 基准(pivot)，然后重新排序数列，将元素比基准值小的放到基准前面，比基准值大的放到基准后面。然后将小于基准值的子数组 (left) 和大于基准值的子数组 (right) 递归地调用 quick 方法，直到排序完成。

function quickSort(arr) {
    const len = arr.length;
    if(len < 2) return arr;
    let [pivot] = arr.splice(Math.floor(len >> 1), 1);
    let left = [], right = [];
    arr.forEach(item => {
        if(item < pivot) {
            left.push(item);
        } else {
            right.push(item);
        }
    })
    return quickSort(left).concat(pivot, quickSort(right));
}

6. 堆排序

堆排序相比其他几种排序代码会有些复杂，先来看一些前置知识帮助理解。堆排序顾名思义就是要利用堆这种数据结构进行排序。堆是一种特殊的树，满足以下两点就是堆：

堆是一个完全二叉树
堆中每一个节点的值都必须大于等于 (或小于等于) 其子树中的每个节点的值

每个节点的值都大于等于子树中每个节点值的堆，叫做大顶堆，每个节点的值都小于等于子树中每个节点值的堆，叫做小顶堆。也就是说，大顶堆中，根节点是堆中最大的元素。小顶堆中，根节点是堆中最小的元素。堆如果用一个数组表示的话，给定一个节点的下标 i (i 从 1 开始)，那么它的父节点一定为 A[i / 2]，左子节点为 A[2i]，右子节点为 A[2i + 1]。

堆排序包含两个过程，建堆和排序。首先构建一个大顶堆，也就是将最大值存储在根节点 (i = 1)。每次取大顶堆的根节点与堆的最后一个节点进行交换，此时最大值放入了有效序列的最后一位，并且有效序列减 1，有效堆依然保持完全二叉树的结构，然后进行堆化成为新的大顶堆。重复此操作，直到有效堆的长度为 0，排序完成。

function heapSort(arr) {
    let len = arr.length;
    // 构建大顶堆
    // 从后往前并不是从序列的最后一个元素开始，而是从最后一个非叶子节点开始，因为叶子节点没有子节点，不需要自上而下式堆化。
    // 最后一个子节点的父节点为 n/2，所以从 n/2 位置节点开始堆化
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        heapify(arr, len, i);
    }
    for (let i = len - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
    return arr;
}

// 堆化
function heapify(arr, len, i) {
    let left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest !== i) {
        swap(arr, i, largest);
        heapify(arr, len, largest);
    }
}

// 交换工具函数
function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

7. 希尔排序

希尔排序又称缩小增量排序，是插入排序的一种更高效的改进版，属于非稳定排序算法。

希尔排序的基本思想是：先将整个待排序的序列分割成为若干子序列，而后将它们分别进行直接插入排序。
具体步骤：

选择一个增量序列 t1，t2，…，ti，tj，tk，其中 ti > tj，tk = 1。注意，增量是不断缩小的。
按增量序列的个数 n，对序列进行 n 趟排序。
每趟排序，根据对应的增量，将待排序的序列分割成若干长度为 m 的子序列，并分别对各子序列进行直接插入排序。当增量为 1 时，对整个序列进行直接插入排序。

function shellSort(arr) {
    const len = arr.length;
    let gap = 1, temp;
    while (gap < len / 5) {
        gap = gap * 5 + 1;
    }   
    for (gap; gap > 0; gap = Math.floor(gap / 5)) {
        for (let i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j+gap] = arr[j]; 
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}