排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复地遍历待排序的列表，比较相邻的元素并交换它们的位置来实现排序。该算法的名称来源于较小的元素会像"气泡"一样逐渐"浮"到列表的顶端。

算法步骤

1. 比较相邻元素：从列表的第一个元素开始，比较相邻的两个元素。
2. 交换位置：如果前一个元素比后一个元素大，则交换它们的位置。
3. 重复遍历：对列表中的每一对相邻元素重复上述步骤，直到列表的末尾。这样，最大的元素会被"冒泡"到列表的最后。
4. 缩小范围：忽略已经排序好的最后一个元素，重复上述步骤，直到整个列表排序完成。

假设有一个待排序的列表 [5, 3, 8, 4, 6]，冒泡排序的过程如下：

1. 第一轮遍历：
   • 比较 5 和 3，交换位置，列表变为 [3, 5, 8, 4, 6]。
   • 比较 5 和 8，不交换。
   • 比较 8 和 4，交换位置，列表变为 [3, 5, 4, 8, 6]。
   • 比较 8 和 6，交换位置，列表变为 [3, 5, 4, 6, 8]。
   • 第一轮结束后，最大的元素 8 已经"冒泡"到列表的最后。
2. 第二轮遍历：
   • 比较 3 和 5，不交换。
   • 比较 5 和 4，交换位置，列表变为 [3, 4, 5, 6, 8]。
   • 比较 5 和 6，不交换。
   • 第二轮结束后，第二大的元素 6 已经"冒泡"到列表的倒数第二位置。
3. 第三轮遍历：
   • 比较 3 和 4，不交换。
   • 比较 4 和 5，不交换。
   • 第三轮结束后，列表已经有序。
4. 第四轮遍历：
   • 比较 3 和 4，不交换。
   • 列表已经完全有序。

实例

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 标记是否发生了交换
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                # 交换位置
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # 如果没有发生交换，说明列表已经有序，提前退出
        if not swapped:
            break
    return arr

# 示例
arr = [5, 3, 8, 4, 6]
sorted_arr = bubble_sort(arr)
print(sorted_arr)  # 输出: [3, 4, 5, 6, 8]

分析

时间复杂度

• 最坏情况：\(O(n²)\)，当列表是逆序时。
• 最好情况：\(O(n)\)，当列表已经有序时。
• 平均情况：\(O(n²)\)。

空间复杂度

• \(O(1)\)，因为冒泡排序是原地排序算法，不需要额外的存储空间。

优缺点

• 优点：
  • 实现简单，代码易于理解。
  • 原地排序，不需要额外的存储空间。
• 缺点：
  • 效率较低，尤其是对于大规模数据集。
  • 不适合处理几乎已经有序的列表，因为仍然需要进行多次遍历。

什么时候最快

当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。

什么时候最慢

当输入的数据是反序时

代码

def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，无论什么数据进去都是 \(O(n²)\) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

选择排序基本思想是每次从待排序的数据中选择最小（或最大）的元素，放到已排序序列的末尾，直到全部数据排序完成。

算法步骤

1. 初始化：将列表分为已排序部分和未排序部分。初始时，已排序部分为空，未排序部分为整个列表。
2. 查找最小值：在未排序部分中查找最小的元素。
3. 交换位置：将找到的最小元素与未排序部分的第一个元素交换位置。
4. 更新范围：将未排序部分的起始位置向后移动一位，扩大已排序部分的范围。
5. 重复步骤：重复上述步骤，直到未排序部分为空，列表完全有序。

假设有一个待排序的列表 \([64, 25, 12, 22, 11]\)，选择排序的过程如下：

1. 第一轮：
   • 未排序部分：[64, 25, 12, 22, 11]。
   • 找到最小值 11，将其与第一个元素 64 交换。
   • 列表变为 [11, 25, 12, 22, 64]。
   • 已排序部分：[11]，未排序部分：[25, 12, 22, 64]。
2. 第二轮：
   • 未排序部分：[25, 12, 22, 64]。
   • 找到最小值 12，将其与第一个元素 25 交换。
   • 列表变为 [11, 12, 25, 22, 64]。
   • 已排序部分：[11, 12]，未排序部分：[25, 22, 64]。
3. 第三轮：
   • 未排序部分：[25, 22, 64]。
   • 找到最小值 22，将其与第一个元素 25 交换。
   • 列表变为 [11, 12, 22, 25, 64]。
   • 已排序部分：[11, 12, 22]，未排序部分：[25, 64]。
4. 第四轮：
   • 未排序部分：[25, 64]。
   • 找到最小值 25，它已经在正确的位置，无需交换。
   • 列表保持不变：[11, 12, 22, 25, 64]。
   • 已排序部分：[11, 12, 22, 25]，未排序部分：[64]。
5. 第五轮：
   • 未排序部分：[64]。
   • 只有一个元素，无需操作。
   • 列表完全有序：[11, 12, 22, 25, 64]。

实例

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 假设当前未排序部分的第一个元素是最小值
        min_idx = i
        # 在未排序部分中查找最小值的索引
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # 将最小值与未排序部分的第一个元素交换
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 示例
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print(sorted_arr)  # 输出: [11, 12, 22, 25, 64]

分析

时间复杂度

• 最坏情况：\(O(n²)\)，无论输入数据是否有序，都需要进行 n(n-1)/2 次比较。
• 最好情况：\(O(n²)\)，即使列表已经有序，仍需进行相同数量的比较。
• 平均情况：\(O(n²)\)。

空间复杂度

• O(1)，选择排序是原地排序算法，不需要额外的存储空间。

优缺点

• 优点：
  • 实现简单，代码易于理解。
  • 原地排序，不需要额外的存储空间。
  • 对于小规模数据集，性能尚可接受。
• 缺点：
  • 时间复杂度较高，不适合大规模数据集。
  • 不稳定排序算法（如果存在相同元素，可能会改变它们的相对顺序）。

适用场景

• 数据量较小且对性能要求不高的场景。
• 需要简单实现的场景。

代码

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，它的工作原理类似于整理扑克牌。

插入排序通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

算法步骤

1. 初始化：将列表分为已排序部分和未排序部分。初始时，已排序部分只包含第一个元素，未排序部分包含剩余元素。
2. 选择元素：从未排序部分中取出第一个元素。
3. 插入到已排序部分：将该元素与已排序部分的元素从后向前依次比较，找到合适的位置插入。
4. 重复步骤：重复上述步骤，直到未排序部分为空，列表完全有序。

假设有一个待排序的列表 [5, 2, 4, 6, 1, 3]，插入排序的过程如下：

1. 初始状态：
   • 已排序部分：[5]。
   • 未排序部分：[2, 4, 6, 1, 3]。
2. 第一轮：
   • 取出未排序部分的第一个元素 2。
   • 将 2 与已排序部分的 5 比较，2 < 5，插入到 5 前面。
   • 列表变为 [2, 5, 4, 6, 1, 3]。
   • 已排序部分：[2, 5]，未排序部分：[4, 6, 1, 3]。
3. 第二轮：
   • 取出未排序部分的第一个元素 4。
   • 将 4 与已排序部分的 5 比较，4 < 5，继续与 2 比较，4 > 2，插入到 2 和 5 之间。
   • 列表变为 [2, 4, 5, 6, 1, 3]。
   • 已排序部分：[2, 4, 5]，未排序部分：[6, 1, 3]。
4. 第三轮：
   • 取出未排序部分的第一个元素 6。
   • 将 6 与已排序部分的 5 比较，6 > 5，直接插入到末尾。
   • 列表变为 [2, 4, 5, 6, 1, 3]。
   • 已排序部分：[2, 4, 5, 6]，未排序部分：[1, 3]。
5. 第四轮：
   • 取出未排序部分的第一个元素 1。
   • 将 1 与已排序部分的 6 比较，1 < 6，继续与 5、4、2 比较，1 是最小的，插入到最前面。
   • 列表变为 [1, 2, 4, 5, 6, 3]。
   • 已排序部分：[1, 2, 4, 5, 6]，未排序部分：[3]。
6. 第五轮：
   • 取出未排序部分的第一个元素 3。
   • 将 3 与已排序部分的 6 比较，3 < 6，继续与 5、4、2 比较，3 > 2，插入到 2 和 4 之间。
   • 列表变为 [1, 2, 3, 4, 5, 6]。
   • 已排序部分：[1, 2, 3, 4, 5, 6]，未排序部分为空。

实例

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]  # 取出未排序部分的第一个元素
        j = i - 1
        # 将 key 插入到已排序部分的正确位置
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]  # 向后移动元素
            j -= 1
        arr[j + 1] = key  # 插入 key
    return arr

# 示例
arr = [5, 2, 4, 6, 1, 3]
sorted_arr = insertion_sort(arr)
print(sorted_arr)  # 输出: [1, 2, 3, 4, 5, 6]

分析

时间复杂度

• 最坏情况：\(O(n²)\)，当列表是逆序时，每次插入都需要移动所有已排序元素。
• 最好情况：\(O(n)\)，当列表已经有序时，只需遍历一次列表。
• 平均情况：\(O(n²)\)。

空间复杂度

• \(O(1)\)，插入排序是原地排序算法，不需要额外的存储空间。

优缺点

• 优点：
  • 实现简单，代码易于理解。
  • 对小规模数据或基本有序的数据效率较高。
  • 原地排序，不需要额外的存储空间。
  • 稳定排序算法（相同元素的相对顺序不会改变）。
• 缺点：
  • 时间复杂度较高，不适合大规模数据集。

适用场景

• 数据量较小或基本有序的场景。
• 需要稳定排序算法的场景。
• 作为更复杂排序算法（如快速排序、归并排序）的辅助算法。

代码

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

希尔排序

希尔排序（Shell Sort）是插入排序的一种改进版本，也称为缩小增量排序。它通过将待排序的列表分成若干子列表，对每个子列表进行插入排序，逐步缩小子列表的间隔，最终完成整

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

算法步骤

1. 选择增量序列：选择一个增量序列（gap sequence），用于将列表分成若干子列表。常见的增量序列有希尔增量（n/2, n/4, ..., 1）等。
2. 分组插入排序：按照增量序列将列表分成若干子列表，对每个子列表进行插入排序。
3. 缩小增量：逐步缩小增量，重复上述分组和排序过程，直到增量为 1。
4. 最终排序：当增量为 1 时，对整个列表进行一次插入排序，完成排序。

假设有一个待排序的列表 [8, 3, 1, 2, 7, 5, 6, 4]，使用希尔增量（初始增量为 n/2），排序过程如下：

1. 初始状态：
   • 列表：[8, 3, 1, 2, 7, 5, 6, 4]。
   • 初始增量：4（列表长度 8 的一半）。
2. 第一轮（增量为 4）：
   • 将列表分成 4 个子列表：
     • 子列表 1：[8, 7]。
     • 子列表 2：[3, 5]。
     • 子列表 3：[1, 6]。
     • 子列表 4：[2, 4]。
   • 对每个子列表进行插入排序：
     • 子列表 1：[7, 8]。
     • 子列表 2：[3, 5]。
     • 子列表 3：[1, 6]。
     • 子列表 4：[2, 4]。
   • 排序后的列表：[7, 3, 1, 2, 8, 5, 6, 4]。
3. 第二轮（增量为 2）：
   • 将列表分成 2 个子列表：
     • 子列表 1：[7, 1, 8, 6]。
     • 子列表 2：[3, 2, 5, 4]。
   • 对每个子列表进行插入排序：
     • 子列表 1：[1, 6, 7, 8]。
     • 子列表 2：[2, 3, 4, 5]。
   • 排序后的列表：[1, 2, 6, 3, 7, 4, 8, 5]。
4. 第三轮（增量为 1）：
   • 将整个列表视为一个子列表，进行插入排序。
   • 排序后的列表：[1, 2, 3, 4, 5, 6, 7, 8]。

实例

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始增量
    while gap > 0:
        # 对每个子列表进行插入排序
        for i in range(gap, n):
            temp = arr[i]  # 当前待插入元素
            j = i
            # 在子列表中找到合适的位置插入
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2  # 缩小增量
    return arr

# 示例
arr = [8, 3, 1, 2, 7, 5, 6, 4]
sorted_arr = shell_sort(arr)
print(sorted_arr)  # 输出: [1, 2, 3, 4, 5, 6, 7, 8]

分析

时间复杂度

希尔排序的时间复杂度取决于增量序列的选择：

• 最坏情况：\(O(n²)\)，当增量序列选择不当时。
• 最好情况：\(O(n log n)\)，当增量序列选择合适时。
• 平均情况：\(O(n log n) \)到 \(O(n²) \)之间。

常见的增量序列：

• 希尔增量：n/2, n/4, ..., 1，时间复杂度为 \(O(n²)\)。
• Hibbard 增量：1, 3, 7, 15, ..., 2^k - 1，时间复杂度为 \(O(n^{3/2})\)。
• Sedgewick 增量：1, 5, 19, 41, 109, ...，时间复杂度为 \(O(n^{4/3})\)。

空间复杂度

• \(O(1)\)，希尔排序是原地排序算法，不需要额外的存储空间。

优缺点

• 优点：
  • 相对于简单插入排序，效率更高。
  • 原地排序，不需要额外的存储空间。
  • 适用于中等规模的数据集。
• 缺点：
  • 时间复杂度依赖于增量序列的选择。
  • 不稳定排序算法（可能改变相同元素的相对顺序）。

适用场景

• 中等规模的数据集。
• 对性能要求不高但需要比简单插入排序更高效的场景。
• 作为更复杂排序算法的预处理步骤。

代码

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
• 自下而上的迭代；

在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

归并排序的核心思想是将一个大问题分解成若干个小问题，分别解决这些小问题，然后将结果合并起来，最终得到整个问题的解。具体到排序问题，归并排序的步骤如下：

1. 分解（Divide）：将待排序的数组分成两个子数组，每个子数组包含大约一半的元素。
2. 解决（Conquer）：递归地对每个子数组进行排序。
3. 合并（Combine）：将两个已排序的子数组合并成一个有序的数组。

通过不断地分解和合并，最终整个数组将被排序。

算法步骤

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤 3 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。

假设有一个待排序的列表 [38, 27, 43, 3, 9, 82, 10]，归并排序的过程如下：

1. 分解：
   • 将列表分成两半：[38, 27, 43, 3] 和 [9, 82, 10]。
   • 继续分解：
     • [38, 27, 43, 3] 分成 [38, 27] 和 [43, 3]。
     • [9, 82, 10] 分成 [9] 和 [82, 10]。
   • 继续分解：
     • [38, 27] 分成 [38] 和 [27]。
     • [43, 3] 分成 [43] 和 [3]。
     • [82, 10] 分成 [82] 和 [10]。
   • 最终分解为单个元素的子列表。
2. 合并：
   • 合并 [38] 和 [27] 得到 [27, 38]。
   • 合并 [43] 和 [3] 得到 [3, 43]。
   • 合并 [27, 38] 和 [3, 43] 得到 [3, 27, 38, 43]。
   • 合并 [9] 和 [10, 82] 得到 [9, 10, 82]。
   • 合并 [3, 27, 38, 43] 和 [9, 10, 82] 得到最终有序列表 [3, 9, 10, 27, 38, 43, 82]。

实例

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 分解：将列表分成两半
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])  # 递归排序左半部分
    right_half = merge_sort(arr[mid:])  # 递归排序右半部分

    # 合并：将两个有序子列表合并
    return merge(left_half, right_half)

def merge(left, right):
    sorted_arr = []
    i = j = 0

    # 比较两个子列表的元素，按顺序合并
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1

    # 将剩余的元素添加到结果中
    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    return sorted_arr

# 示例
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)  # 输出: [3, 9, 10, 27, 38, 43, 82]

分析

时间复杂度

• 分解：每次将列表分成两半，需要 \(O(log n)\) 层递归。
• 合并：每层递归需要 \(O(n)\) 的时间来合并子列表。
• 总时间复杂度：\(O(n log n)\)。

空间复杂度

• \(O(n)\)，归并排序需要额外的空间来存储临时列表。

优缺点

• 优点：
  • 时间复杂度稳定为 \(O(n log n)\)，适合大规模数据。
  • 稳定排序算法（相同元素的相对顺序不会改变）。
  • 适合外部排序（如对磁盘文件进行排序）。
• 缺点：
  • 需要额外的存储空间，空间复杂度为 \(O(n)\)。
  • 对于小规模数据，性能可能不如插入排序等简单算法。

代码

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0));
    return result

快速排序

快速排序（Quick Sort）是一种高效的排序算法，基于分治法（Divide and Conquer）的思想。它的核心是通过选择一个基准元素（pivot），将列表分为两部分：一部分小于基准元素，另一部分大于基准元素，然后递归地对这两部分进行排序。快速排序的平均时间复杂度为 \(O(n log n)\)，在实际应用中性能优异。

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 \(n\) 个项目要 \(Ο(nlogn)\) 次比较。在最坏状况下则需要 \(Ο(n^2)\) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 \(Ο(nlogn)\) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 \(O(n²)\)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 \(O(n logn)\) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

快速排序的最坏运行情况是 \(O(n²)\)，比如说顺序数列的快排。但它的平摊期望时间是 \(O(nlogn)\)，且 \(O(nlogn)\) 记号中隐含的常数因子很小，比复杂度稳定等于 \(O(nlogn)\) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

算法步骤

1. 选择基准元素：从列表中选择一个元素作为基准（pivot）。选择方式可以是第一个元素、最后一个元素、中间元素或随机元素。
2. 分区：将列表重新排列，使得所有小于基准元素的元素都在基准的左侧，所有大于基准元素的元素都在基准的右侧。基准元素的位置在分区完成后确定。
3. 递归排序：对基准元素左侧和右侧的子列表分别递归地进行快速排序。
4. 合并：由于分区操作是原地进行的，递归结束后整个列表已经有序。

假设有一个待排序的列表 [3, 6, 8, 10, 1, 2, 1]，选择最后一个元素作为基准（pivot），排序过程如下：

1. 初始状态：
   • 列表：[3, 6, 8, 10, 1, 2, 1]。
   • 基准元素：1（最后一个元素）。
2. 第一轮分区：
   • 将小于基准的元素放在左侧，大于基准的元素放在右侧。
   • 分区后列表：[1, 1, 2, 10, 6, 8, 3]。
   • 基准元素 1 的位置确定。
3. 递归排序：
   • 对左侧子列表 [1] 和右侧子列表 [2, 10, 6, 8, 3] 分别进行快速排序。
   • 左侧子列表已经有序。
   • 对右侧子列表 [2, 10, 6, 8, 3] 选择基准元素 3（最后一个元素）：
     • 分区后列表：[2, 3, 6, 8, 10]。
     • 基准元素 3 的位置确定。
   • 继续递归排序右侧子列表 [6, 8, 10]：
     • 选择基准元素 10（最后一个元素）：
       • 分区后列表：[6, 8, 10]。
       • 基准元素 10 的位置确定。
     • 继续递归排序左侧子列表 [6, 8]：
       • 选择基准元素 8（最后一个元素）：
         • 分区后列表：[6, 8]。
         • 基准元素 8 的位置确定。
       • 继续递归排序左侧子列表 [6]，已经有序。
4. 最终结果：
   • 列表完全有序：[1, 1, 2, 3, 6, 8, 10]。

实例

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    # 选择基准元素（这里选择最后一个元素）
    pivot = arr[-1]
    # 分区：小于基准的元素放在左侧，大于基准的元素放在右侧
    left = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x > pivot]
    # 递归排序并合并
    return quick_sort(left) + [pivot] + quick_sort(right)

# 示例
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(sorted_arr)  # 输出: [1, 1, 2, 3, 6, 8, 10]

分析

时间复杂度

• 分解：每次将列表分成两半，需要 \(O(log n)\) 层递归。
• 合并：每层递归需要 \(O(n)\) 的时间来合并子列表。
• 总时间复杂度：\(O(n log n)\)。

空间复杂度

• \(O(n)\)，归并排序需要额外的空间来存储临时列表。

优缺点

• 优点：
  • 平均时间复杂度为 \(O(n log n)\)，在大多数情况下非常高效。
  • 原地排序（in-place）算法，只需 \(O(log n)\) 额外空间（递归栈）。
  • 适合内存中的大规模数据排序，常用于通用排序函数（如 std::sort）。
• 缺点：
  • 不稳定排序，相同元素的相对顺序可能改变。
  • 最坏时间复杂度为 \(O(n²)\)（如数组已近乎有序时），但可通过随机化或"三数取中"优化。
  • 小规模数据性能较差，不如插入排序等简单算法。

适用场景

• 大规模数据集的排序。
• 需要稳定排序算法的场景。
• 外部排序（如对磁盘文件进行排序）。

代码

def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot+1
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index+=1
        i+=1
    swap(arr,pivot,index-1)
    return index-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 \(Ο(nlogn)\)。

算法步骤

1. 创建一个堆 H[0……n-1]；
2. 把堆首（最大值）和堆尾互换；
3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
4. 重复步骤 2，直到堆的尺寸为 1。

假设有一个待排序的列表 [4, 10, 3, 5, 1]，堆排序的过程如下：

1. 构建最大堆：
   • 初始列表：[4, 10, 3, 5, 1]。
   • 从最后一个非叶子节点开始，逐步调整堆：
     • 调整节点 5：[4, 10, 3, 5, 1]（无需调整）。
     • 调整节点 10：[4, 10, 3, 5, 1]（无需调整）。
     • 调整节点 4：[10, 5, 3, 4, 1]。
   • 最终最大堆：[10, 5, 3, 4, 1]。
2. 交换堆顶元素：
   • 将堆顶元素 10 与最后一个元素 1 交换，列表变为 [1, 5, 3, 4, 10]。
   • 堆的大小减 1，已排序部分为 [10]。
3. 调整堆：
   • 对新的堆顶元素 1 进行下沉操作：
     • 比较 1 和其子节点 5、3，将 1 与 5 交换。
     • 列表变为 [5, 1, 3, 4, 10]。
     • 继续比较 1 和其子节点 4，将 1 与 4 交换。
     • 列表变为 [5, 4, 3, 1, 10]。
   • 调整后的堆：[5, 4, 3, 1]。
4. 重复步骤：
   • 将堆顶元素 5 与最后一个元素 1 交换，列表变为 [1, 4, 3, 5, 10]。
   • 堆的大小减 1，已排序部分为 [5, 10]。
   • 对新的堆顶元素 1 进行下沉操作：
     • 比较 1 和其子节点 4、3，将 1 与 4 交换。
     • 列表变为 [4, 1, 3, 5, 10]。
   • 调整后的堆：[4, 1, 3]。
5. 继续重复：
   • 将堆顶元素 4 与最后一个元素 3 交换，列表变为 [3, 1, 4, 5, 10]。
   • 堆的大小减 1，已排序部分为 [4, 5, 10]。
   • 对新的堆顶元素 3 进行下沉操作：
     • 比较 3 和其子节点 1，无需交换。
   • 调整后的堆：[3, 1]。
6. 最终步骤：
   • 将堆顶元素 3 与最后一个元素 1 交换，列表变为 [1, 3, 4, 5, 10]。
   • 堆的大小减 1，已排序部分为 [3, 4, 5, 10]。
   • 堆的大小为 1，排序完成。

实例

def heapify(arr, n, i):
    # 找到当前节点、左子节点和右子节点中的最大值
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大值不是当前节点，交换并继续调整
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 逐个取出堆顶元素并调整堆
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 交换堆顶元素和最后一个元素
        heapify(arr, i, 0)  # 调整堆

    return arr

# 示例
arr = [4, 10, 3, 5, 1]
sorted_arr = heap_sort(arr)
print(sorted_arr)  # 输出: [1, 3, 4, 5, 10]

分析

时间复杂度

• 构建最大堆：\(O(n)\)。
• 每次调整堆：\(O(log n)\)，总共需要调整 \(n-1\) 次。
• 总时间复杂度：\(O(n log n)\)。

空间复杂度

• \(O(1)\)，堆排序是原地排序算法，不需要额外的存储空间。

优缺点

• 优点：
  • 时间复杂度稳定为 \(O(n log n)\)，适合大规模数据。
  • 原地排序，不需要额外的存储空间。
• 缺点：
  • 不稳定排序算法（可能改变相同元素的相对顺序）。
  • 对于小规模数据，性能可能不如插入排序等简单算法。

适用场景

• 大规模数据集的排序。
• 对性能要求较高的场景。
• 适合内存排序（不适合外部排序）。

代码

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1
        heapify(arr, 0)
    return arr

计数排序

计数排序（Counting Sort）是一种非比较型的排序算法，适用于对整数或有限范围内的数据进行排序。它的核心思想是通过统计每个元素的出现次数，然后根据统计结果将元素放回正确的位置。计数排序的时间复杂度为 \(O(n + k)\)，其中 \(n\) 是待排序元素的数量，\(k\) 是数据的范围大小。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法步骤

当输入的元素是 \(n\) 个 \(0\) 到 \(k\) 之间的整数时，它的运行时间是 \(Θ(n + k)\)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组\(C\)的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。

 算法的步骤如下：

1. 统计频率：遍历待排序的列表，统计每个元素出现的次数，存储在一个计数数组中。
2. 累加频率：将计数数组中的值累加，得到每个元素在排序后列表中的最后一个位置。
3. 构建有序列表：遍历待排序的列表，根据计数数组中的位置信息，将元素放到正确的位置。
4. 输出结果：将排序后的列表输出。

假设有一个待排序的列表 [4, 2, 2, 8, 3, 3, 1]，数据的范围是 1 到 8，计数排序的过程如下：

1. 统计频率：
   • 初始化计数数组 count，大小为 9（范围 0-8）。
   • 遍历列表，统计每个元素的出现次数：
     • count[1] = 1
     • count[2] = 2
     • count[3] = 2
     • count[4] = 1
     • count[8] = 1
   • 计数数组：[0, 1, 2, 2, 1, 0, 0, 0, 1]。
2. 累加频率：
   • 将计数数组中的值累加，得到每个元素的最终位置：
     • count[1] = 1
     • count[2] = 1 + 2 = 3
     • count[3] = 3 + 2 = 5
     • count[4] = 5 + 1 = 6
     • count[8] = 6 + 1 = 7
   • 累加后的计数数组：[0, 1, 3, 5, 6, 6, 6, 6, 7]。
3. 放置元素：
   • 初始化结果数组 output，大小为 7。
   • 遍历原始列表，根据计数数组中的位置信息，将元素放入结果数组：
     • 元素 4：count[4] = 6，放入 output[5]，count[4] -= 1。
     • 元素 2：count[2] = 3，放入 output[2]，count[2] -= 1。
     • 元素 2：count[2] = 2，放入 output[1]，count[2] -= 1。
     • 元素 8：count[8] = 7，放入 output[6]，count[8] -= 1。
     • 元素 3：count[3] = 5，放入 output[4]，count[3] -= 1。
     • 元素 3：count[3] = 4，放入 output[3]，count[3] -= 1。
     • 元素 1：count[1] = 1，放入 output[0]，count[1] -= 1。
   • 结果数组：[1, 2, 2, 3, 3, 4, 8]。
4. 输出结果：
   • 排序后的列表：[1, 2, 2, 3, 3, 4, 8]。

实例

def counting_sort(arr):
    # 找到列表中的最大值
    max_val = max(arr)
    # 初始化计数数组
    count = [0] * (max_val + 1)
    # 统计每个元素的出现次数
    for num in arr:
        count[num] += 1
    # 累加计数数组，得到每个元素的最终位置
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    # 初始化结果数组
    output = [0] * len(arr)
    # 反向遍历原始列表，将元素放入结果数组
    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1
    return output

# 示例
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)  # 输出: [1, 2, 2, 3, 3, 4, 8]

分析

时间复杂度

• 统计频率：\(O(n)\)，遍历列表一次。
• 累加频率：\(O(k)\)，遍历计数数组一次。
• 放置元素：\(O(n)\)，遍历列表一次。
• 总时间复杂度：\(O(n + k)\)，其中 \(n \)是列表长度，\(k\) 是数据的范围大小。

空间复杂度

• \(O(n + k)\)，需要额外的计数数组和结果数组。

优缺点

• 优点：
  • 时间复杂度为 \(O(n + k)\)，当 \(k\) 较小时，性能优异。
  • 稳定排序算法（相同元素的相对顺序不会改变）。
• 缺点：
  • 仅适用于整数或有限范围内的数据。
  • 当数据范围 k 很大时，空间复杂度较高。

适用场景

• 数据范围较小的整数排序。
• 需要稳定排序算法的场景。
• 适合外部排序（如对磁盘文件进行排序）。

代码

def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]]=0
        bucket[arr[i]]+=1
    for j in range(bucketLen):
        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr

桶排序

桶排序（Bucket Sort）是一种分布式排序算法，它将待排序的元素分配到若干个桶（Bucket）中，然后对每个桶中的元素进行排序，最后将所有桶中的元素按顺序合并。桶排序的核心思想是将数据分到有限数量的桶中，每个桶再分别排序（可以使用其他排序算法或递归地使用桶排序）。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 \(N\) 个数据均匀的分配到 \(K\) 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

算法步骤

算法步骤：

1. 初始化桶：根据数据的范围和分布，创建若干个桶。
2. 分配元素：遍历待排序的列表，将每个元素分配到对应的桶中。
3. 排序每个桶：对每个桶中的元素进行排序（可以使用插入排序、快速排序等）。
4. 合并桶：将所有桶中的元素按顺序合并，得到最终排序结果。

1. 什么时候最快

当输入的数据可以均匀的分配到每一个桶中。

2. 什么时候最慢

当输入的数据被分配到了同一个桶中。

元素分布在桶中：

然后，元素在每个桶中排序：

假设有一个待排序的列表 [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]，桶排序的过程如下：

1. 初始化桶：
   • 假设数据范围是 [0, 1)，创建 10 个桶，每个桶的范围为 0.1。
   • 桶 0：[0.0, 0.1)
   • 桶 1：[0.1, 0.2)
   • ...
   • 桶 9：[0.9, 1.0)
2. 分配元素：
   • 遍历列表，将元素分配到对应的桶中：
     • 0.42 → 桶 4
     • 0.32 → 桶 3
     • 0.33 → 桶 3
     • 0.52 → 桶 5
     • 0.37 → 桶 3
     • 0.47 → 桶 4
     • 0.51 → 桶 5
   • 分配后的桶：
     • 桶 3：[0.32, 0.33, 0.37]
     • 桶 4：[0.42, 0.47]
     • 桶 5：[0.52, 0.51]
3. 排序每个桶：
   • 对每个桶中的元素进行排序：
     • 桶 3：[0.32, 0.33, 0.37]（已经有序）。
     • 桶 4：[0.42, 0.47]（已经有序）。
     • 桶 5：[0.51, 0.52]（排序后）。
4. 合并桶：
   • 按顺序合并所有桶中的元素：
     • 桶 3：[0.32, 0.33, 0.37]
     • 桶 4：[0.42, 0.47]
     • 桶 5：[0.51, 0.52]
   • 合并后的列表：[0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52]。

实例

def bucket_sort(arr, bucket_size=10):
    if len(arr) == 0:
        return arr

    # 找到最小值和最大值
    min_val = min(arr)
    max_val = max(arr)

    # 初始化桶
    bucket_count = (max_val - min_val) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]

    # 分配元素到桶中
    for num in arr:
        index = int((num - min_val) // bucket_size)
        buckets[index].append(num)

    # 对每个桶中的元素进行排序
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(sorted(bucket))  # 使用内置排序函数

    return sorted_arr

# 示例
arr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
sorted_arr = bucket_sort(arr)
print(sorted_arr)  # 输出: [0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52]

分析

时间复杂度

• 分配元素：\(O(n)\)，遍历列表一次。
• 排序每个桶：假设每个桶中的元素数量为 \(m\)，则排序一个桶的时间复杂度为 \(O(m log m)\)。如果桶的数量为 \(k\)，则总时间复杂度为 \(O(k * m log m)\)。
• 合并桶：\(O(n)\)，遍历所有桶一次。
• 总时间复杂度：\(O(n + k * m log m)\)，其中 \(n\) 是列表长度，\(k\) 是桶的数量，\(m\) 是每个桶的平均元素数量。

空间复杂度

• \(O(n + k)\)，需要额外的存储空间来存放桶和排序后的结果。

优缺点

• 优点：
  • 当数据分布均匀时，性能优异。
  • 适合外部排序（如对磁盘文件进行排序）。
• 缺点：
  • 当数据分布不均匀时，某些桶中的元素数量过多，导致性能下降。
  • 需要额外的存储空间。

适用场景

• 数据分布均匀的场景。
• 数据范围已知且有限的场景。
• 适合外部排序（如对磁盘文件进行排序）。

基数排序

基数排序（Radix Sort）是一种非比较型的排序算法，它通过逐位比较元素的每一位（从最低位到最高位）来实现排序。基数排序的核心思想是将整数按位数切割成不同的数字，然后按每个位数分别进行排序。基数排序的时间复杂度为 \(O(n * k)\)，其中 \(n\) 是列表长度，\(k \)是最大数字的位数。

算法步骤：

1. 确定最大位数：找到列表中最大数字的位数，确定需要排序的轮数。
2. 按位排序：从最低位开始，依次对每一位进行排序（通常使用计数排序或桶排序作为子排序算法）。
3. 合并结果：每一轮排序后，更新列表的顺序，直到所有位数排序完成。

基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值；

假设有一个待排序的列表 [170, 45, 75, 90, 802, 24, 2, 66]，基数排序的过程如下：

1. 确定最大位数：
   • 最大数字是 802，有 3 位数，因此需要 3 轮排序。
2. 第一轮（按个位数排序）：
   • 使用计数排序对个位数进行排序：
     • 个位数统计：[0, 2, 4, 5, 6, 0, 2, 6]。
     • 排序后列表：[170, 90, 802, 2, 24, 45, 75, 66]。
3. 第二轮（按十位数排序）：
   • 使用计数排序对十位数进行排序：
     • 十位数统计：[7, 9, 0, 0, 2, 4, 7, 6]。
     • 排序后列表：[802, 2, 24, 45, 66, 170, 75, 90]。
4. 第三轮（按百位数排序）：
   • 使用计数排序对百位数进行排序：
     • 百位数统计：[8, 0, 0, 0, 1, 0, 0, 0]。
     • 排序后列表：[2, 24, 45, 66, 75, 90, 170, 802]。
5. 最终结果：
   • 列表完全有序：[2, 24, 45, 66, 75, 90, 170, 802]。

实例

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n  # 初始化输出数组
    count = [0] * 10  # 初始化计数数组

    # 统计每个数字的出现次数
    for num in arr:
        index = (num // exp) % 10
        count[index] += 1

    # 累加计数数组，得到每个数字的最终位置
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 将元素放入输出数组
    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    # 将输出数组复制到原始数组
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    # 找到最大数字的位数
    max_num = max(arr)
    exp = 1  # 从个位数开始
    while max_num // exp > 0:
        counting_sort(arr, exp)  # 对当前位数进行计数排序
        exp *= 10  # 移动到下一位
    return arr

# 示例
arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radix_sort(arr)
print(sorted_arr)  # 输出: [2, 24, 45, 66, 75, 90, 170, 802]

分析

时间复杂度

• 每一轮排序：\(O(n)\)，使用计数排序对每一位进行排序。
• 总轮数：\(k\) 轮，其中 \(k\) 是最大数字的位数。
• 总时间复杂度：\(O(n * k)\)。

空间复杂度

• \(O(n + k)\)，需要额外的存储空间来存放计数数组和输出数组。

优缺点

• 优点：
  • 时间复杂度为 \(O(n * k)\)，当 \(k\) 较小时，性能优异。
  • 稳定排序算法（相同元素的相对顺序不会改变）。
• 缺点：
  • 仅适用于整数或固定长度的字符串。
  • 当最大数字的位数 \(k\) 很大时，性能下降。

适用场景

• 数据范围较小的整数排序。
• 需要稳定排序算法的场景。
• 适合外部排序（如对磁盘文件进行排序）。

Reference

十大经典排序算法