1. 排序算法

1.1. 排序算法的简介

排序算法是一类用于将一组数据按照特定顺序（通常是从小到大或从大到小）排列的方法和过程。在计算机科学中，排序是一个基本问题，因为许多其他算法（如搜索和合并算法）都依赖于数据的有序性。排序算法有很多种，不同的算法在时间复杂度、空间复杂度以及稳定性（即是否保持相同值的相对顺序）等方面表现各异。

排序算法（sorting algorithm）用于将一组数据按照特定顺序进行排列。由于有序数据通常能够被更高效地查找、分析和处理，排序算法在计算机科学和实际应用中都非常重要。

如下图所示，排序算法可以处理的数据类型包括整数、浮点数、字符或字符串等。排序的判断规则可根据需求设定，如数字大小、字符的 ASCII 码顺序或自定义规则。

数据类型和判断规则示例

1.2 评价维度

运行效率：排序算法的时间复杂度应尽可能低，且操作数量应尽量减少（即时间复杂度中的常数项要小）。在大数据量的情况下，运行效率显得尤为重要。

就地性：原地排序通过直接在原数组上操作实现排序，无需借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，因此运行速度也更快。

稳定性：稳定排序在完成排序后，相等元素在数组中的相对顺序保持不变。

在多级排序场景中，稳定排序是必要条件。假设我们有一个存储学生信息的表格，其中第 1 列和第 2 列分别是姓名和年龄。在这种情况下，非稳定排序可能会导致输入数据的有序性丧失：

# 输入数据是按照姓名排序好的
# (name, age)
  ('A', 19)
  ('B', 18)
  ('C', 21)
  ('D', 19)
  ('E', 23)

# 如果使用非稳定排序算法按年龄排序列表，
# 结果中 ('D', 19) 和 ('A', 19) 的相对位置改变，
# 输入数据按姓名排序的性质丢失
  ('B', 18)
  ('D', 19)
  ('A', 19)
  ('C', 21)
  ('E', 23)

自适应性：自适应排序能够利用输入数据已有的顺序信息来减少计算量，达到更优的时间效率。自适应排序算法的最佳时间复杂度通常优于平均时间复杂度。

是否基于比较：基于比较的排序依赖比较运算符（$<$、$=$、$>$）来判断元素的相对顺序，从而对整个数组进行排序，理论上的最优时间复杂度为 $O(n \log n)$。而非比较排序不使用比较运算符，时间复杂度可达到 $O(n)$，但其通用性相对较差。

1.3. 理想排序算法

理想的排序算法应具备以下特性：运行快、原地、稳定、自适应、通用性好。然而，迄今为止尚未发现兼具所有这些特性的排序算法。因此，在选择排序算法时，需要根据具体的数据特点和问题需求来决定。

2. 选择排序(sorting algorithm)

2.1. 核心算法

选择排序（Selection Sort）的工作原理十分简单：通过循环遍历数组，每一轮从未排序区间中选出最小的元素，并将其放置在已排序区间的末尾。具体流程如下所示：

初始状态：所有元素均处于未排序状态，即未排序区间为索引 $[0, n-1]$，其中 $n$ 为数组的长度。
第一轮选择：在未排序区间 $[0, n-1]$ 中选取最小元素，并将其与索引 $0$ 处的元素交换。此时，数组的第一个元素已排序。
第二轮选择：在未排序区间 $[1, n-1]$ 中再次选取最小元素，并将其与索引 $1$ 处的元素交换。此时，数组的前两个元素已排序。
依次重复：每一轮都在当前未排序区间内选取最小元素，并将其与未排序区间的第一个元素交换。经过 $n - 1$ 轮选择与交换，数组的前 $n - 1$ 个元素将全部排序完毕。
最后一步：此时，数组中仅剩一个元素未排序，由于前 $n - 1$ 个元素已按顺序排列，剩下的这个元素必然是最大的，无需再进行任何操作。

2.2. 代码实现

下面是选择排序的Python代码实现：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 假设当前i位置的元素为最小值
        min_index = i
        # 从i+1到n的区间内找到最小值
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # 将最小值与i位置的元素交换
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# 测试
arr = [29, 10, 14, 37, 13]
sorted_arr = selection_sort(arr)
print("排序后的数组:", sorted_arr)

外层循环：for i in range(n)，循环变量 i 表示已排序区间的末尾索引，从 0 到 n-1 遍历整个数组。
假设最小值索引：min_index = i，初始假设 i 位置的元素为最小值。
寻找最小值：for j in range(i + 1, n)，内层循环从 i + 1 到数组末尾寻找比当前 min_index 位置更小的元素。如果找到更小的，则更新 min_index。
交换位置：arr[i], arr[min_index] = arr[min_index], arr[i]，将找到的最小值与当前位置 i 的元素交换。
返回排序结果：return arr，最终返回排序后的数组。

2.3. 算法特性

选择排序（Selection Sort）具有以下几个算法特性：

2.3.1. 时间复杂度

最坏情况时间复杂度：( O(n^2) )
平均情况时间复杂度：( O(n^2) )
最好情况时间复杂度：( O(n^2) )
选择排序在任何情况下都需要进行相同数量的比较操作，即使数组已经部分或完全排序，也无法减少比较次数，因此它的时间复杂度始终是 ( O(n^2) )。

2.3.2. 空间复杂度

空间复杂度：( O(1) )
选择排序是原地排序算法，它不需要额外的存储空间，除了用于交换的临时变量，所有操作都在输入数组上直接进行，因此空间复杂度为 ( O(1) )。

2.3.3. 稳定性

不稳定
选择排序不是一个稳定的排序算法。因为在选择最小元素进行交换时，如果有相同的元素，可能会导致相同元素的相对顺序发生变化。例如，如果在排序过程中两个相同的元素被分开，交换时可能会导致它们的相对位置发生变化。

2.3.4. 原地排序

选择排序是一个原地排序算法。它不依赖额外的存储空间，排序是在输入数组上完成的。

2.3.5. 比较和交换次数

比较次数：选择排序在排序过程中总共会进行 ( n(n-1)/2 ) 次比较。每轮需要遍历未排序部分的所有元素，以找到最小元素，因此比较次数较多。
交换次数：虽然选择排序的比较次数较多，但它的交换次数较少。在最理想的情况下，每轮选择只需要交换一次，也就是最多 ( n-1 ) 次交换。

2.3.6. 适用场景

选择排序适用于数据量较小或对内存使用有限制的场景。在实际应用中，由于其 ( O(n^2) ) 的时间复杂度，它通常不适用于大规模数据的排序任务。

2.3.7. 简单易实现

选择排序的实现逻辑非常简单，易于理解和实现，适合教学和演示用途。

2.3.8. 依赖顺序

选择排序的效率与初始数据的顺序无关，即使数组已经接近有序，算法仍会执行 ( O(n^2) ) 的比较。

3. 冒泡排序

3.1. 核心算法

冒泡过程可以利用元素交换操作来模拟：从数组最左端开始向右遍历，依次比较相邻元素大小，如果“左元素 > 右元素”就交换二者。遍历完成后，最大的元素会被移动到数组的最右端。

冒泡排序（Bubble Sort）是一种通过反复遍历数组并交换相邻元素，逐步将最大或最小元素“冒泡”至数组末端的排序算法。这个过程像气泡从底部升到顶部一样，因此得名“冒泡排序”。其工作原理如下：

初始状态：所有元素均处于未排序状态，未排序区间的索引范围为 $[0, n-1]$，其中 $n$ 为数组的长度。
第一轮冒泡：从数组的第一个元素开始，依次比较相邻的两个元素。如果前一个元素比后一个元素大（对于升序排序），则交换它们的位置。经过一轮遍历后，最大的元素将“冒泡”至数组末尾，即进入已排序区间。
第二轮冒泡：在未排序区间 $[0, n-2]$ 内重复上述过程，此时，次大的元素将移动到已排序区间的第二个位置。
依次重复：每一轮遍历后，未排序区间的长度缩短1，直到整个数组有序。
结束条件：如果在某一轮遍历中没有发生任何交换操作，表示数组已经完全有序，算法可以提前终止。

3.2. 代码实现

下面是冒泡排序的Python代码实现：

def bubble_sort(nums: list[int]):
    """冒泡排序"""
    n = len(nums)
    # 外循环：未排序区间为 [0, i]
    for i in range(n - 1, 0, -1):
        # 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for j in range(i):
            if nums[j] > nums[j + 1]:
                # 交换 nums[j] 与 nums[j + 1]
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

#优化后的代码
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        # 从0到n-i-1的范围内进行冒泡
        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

外层循环：for i in range(n)，每次循环确定一个新的已排序区间的起始位置，从数组末尾向前推进。
内层循环：for j in range(0, n - i - 1)，在未排序区间内进行冒泡操作，比较并交换相邻的两个元素。
交换标志：swapped = False，用于跟踪当前轮次是否进行了交换操作。如果没有交换，则提前结束排序。
提前终止：if not swapped: break，如果在一轮冒泡中未发生交换，算法提前终止，表示数组已排序。
返回排序结果：return arr，最终返回排序后的数组。

3.3. 算法特性

冒泡排序（Bubble Sort）具有以下几个算法特性：

时间复杂度：
- 最坏情况时间复杂度：(O(n^2))，当数组是逆序时，需要进行最多的比较和交换。
- 最佳情况时间复杂度：(O(n))，当数组已经有序时，只需进行一次遍历即可完成排序。
- 平均情况时间复杂度：(O(n^2))，通常情况下，需要进行多次比较和交换。
空间复杂度：
- (O(1))，冒泡排序是原地排序算法，只需要常量级的辅助空间。
稳定性：
- 冒泡排序是稳定的排序算法，若两个元素相等，它们在排序后的相对顺序不会发生改变。
内排序：
- 冒泡排序是一种内排序算法，所有的排序操作都是在原数组上完成的，不需要额外的数组来存储数据。
渐进性：
- 冒泡排序是渐进的，即它每次遍历数组时都会把最大的元素“冒泡”到数组末尾。
简单易实现：
- 冒泡排序算法相对简单，容易理解和实现，特别适合对算法理解的初学者。

4. 插入排序(insertion sort)

4.1 核心算法

插入排序（Insertion Sort）是一种简单直观的排序算法，特别适用于数据量小或部分已排序的场景。插入排序的核心思想是逐步构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。它的工作原理与手动整理一副牌的过程非常相似。插入排序的工作原理如下：

初始状态：假设数组的第一个元素已经排好序，已排序区间为索引 ([0, 0])，未排序区间为索引 ([1, n-1])，其中 (n) 为数组的长度。
第一轮插入：从未排序区间 ([1, n-1]) 中取出第一个元素（索引为1的元素），将其插入到已排序区间 ([0, 0]) 中的正确位置。此时，数组的前两个元素已排序。
第二轮插入：从未排序区间 ([2, n-1]) 中取出第一个元素（索引为2的元素），将其插入到已排序区间 ([0, 1]) 中的正确位置。此时，数组的前三个元素已排序。
依次重复：每一轮都从未排序区间取出第一个元素，将其插入到已排序区间的合适位置，直到所有元素都被插入，排序完成。
结束排序：当未排序区间为空时，算法结束，整个数组已排序。

4.2. 代码实现

下面是插入排序的Python代码实现：

def insertion_sort(arr):
    # 遍历数组从第二个元素开始
    for i in range(1, len(arr)):
        key = arr[i]  # 当前元素
        j = i - 1     # 前一个元素的索引
        
        # 将当前元素插入到已排序区间的合适位置
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key  # 插入当前元素
    
    return arr

外层循环：for i in range(1, len(arr))，遍历数组的每个元素，从索引1开始到最后一个元素。
当前元素的存储：key = arr[i]，保存当前要插入的元素。
内层循环：while j >= 0 and key < arr[j]，从已排序区间的末尾开始向前扫描，如果当前元素比已排序区间中的元素小，就将已排序元素向后移动一位，直到找到插入位置。
插入当前元素：arr[j + 1] = key，将当前元素插入到正确位置。
返回排序结果：return arr，最终返回排序后的数组。

4.3. 算法特性

插入排序（Insertion Sort）是一种简单直观的排序算法，具有以下几个特性：

稳定性：插入排序是稳定的排序算法。即在排序过程中，两个相等的元素不会改变相对顺序。
在线排序：插入排序可以在接收输入时进行排序，因此它是一种在线算法。每处理一个元素，就可以得到一个部分排序的序列。
时间复杂度：
- 最佳时间复杂度：O(n) —— 当输入数据已经是有序的时。
- 平均时间复杂度：O(n^2) —— 当输入数据是随机排列时。
- 最坏时间复杂度：O(n^2) —— 当输入数据是逆序排列时。
空间复杂度：O(1) —— 插入排序是就地排序（in-place sort），不需要额外的存储空间，除了少量用于交换的临时变量。
适用性：插入排序适合于数据量较小或基本有序的数据集。在数据量很大且无序的情况下，其效率较低。
算法稳定性：因为插入排序只需要在已排序的序列中插入元素，不会改变元素之间的相对顺序。

5. 快速排序 (Quick Sort)

5.1 核心算法

快速排序（Quick Sort）是一种分治法（Divide and Conquer）思想的排序算法。它通过选取一个“基准”元素，将数组分为两部分，然后递归地对每一部分进行快速排序，从而实现整个数组的排序。它的平均时间复杂度为 (O(n \log n))，在所有内部排序算法中表现优异。

快速排序的核心思想如下：

选择基准（Pivot）：从数组中选择一个元素作为“基准”元素（通常是第一个元素、最后一个元素、随机选取或选取中间位置的元素）。
分区（Partition）：将数组重新排列，使得所有小于基准的元素移到基准的左边，所有大于基准的元素移到基准的右边。基准元素最终位于其排序后的正确位置。
递归排序：递归地对基准左侧和右侧的子数组进行快速排序。
结束递归：当子数组的大小为0或1时，结束递归。

5.2 代码实现

以下是快速排序的Python代码实现：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # 基本情况：数组为空或只有一个元素，已排序
    
    pivot = arr[len(arr) // 2]  # 选择中间元素作为基准
    left = [x for x in arr if x < pivot]  # 小于基准的元素
    middle = [x for x in arr if x == pivot]  # 等于基准的元素
    right = [x for x in arr if x > pivot]  # 大于基准的元素
    
    return quick_sort(left) + middle + quick_sort(right)  # 递归排序并合并结果

基本情况：if len(arr) <= 1，数组为空或只有一个元素时，直接返回该数组，因其已排序。
选择基准：pivot = arr[len(arr) // 2]，通常选择中间元素作为基准。
分区过程：
- left = [x for x in arr if x < pivot]：所有小于基准的元素放到左边。
- middle = [x for x in arr if x == pivot]：所有等于基准的元素放到中间。
- right = [x for x in arr if x > pivot]：所有大于基准的元素放到右边。
递归调用：return quick_sort(left) + middle + quick_sort(right)，对左子数组和右子数组递归调用快速排序，并合并结果。

5.3 算法特性

快速排序具有以下几个特性：

不稳定性：快速排序是一种不稳定的排序算法，因为在交换过程中，可能改变相等元素的相对顺序。
时间复杂度：
- 最佳时间复杂度：(O(n \log n)) —— 当每次分区时，都正好均匀地分成两半时。
- 平均时间复杂度：(O(n \log n)) —— 大多数情况下。
- 最坏时间复杂度：(O(n^2)) —— 当每次分区选择的基准是最小或最大元素（极度不均匀分区）时。
空间复杂度：(O(\log n)) —— 快速排序是就地排序算法，但递归调用会占用栈空间，最坏情况下的空间复杂度为 (O(n))。
适用性：快速排序适合于大数据量的排序，是平均性能最优的内部排序算法。
递归性质：快速排序通过递归地处理较小的子问题来解决更大的问题，其递归深度决定了其空间复杂度。

快速排序因其高效性和相对简单的实现，被广泛应用于各种排序需求中。尤其在大数据量、数据无序的情况下，表现尤为优异。

5.4 快速排序为什么快

从名字上看，快速排序（Quick Sort）在效率上应该有一定的优势。虽然快速排序的平均时间复杂度与“归并排序”和“堆排序”相同，都是 (O(n \log n))，但在大多数情况下，快速排序的效率更高。这主要归因于以下几个原因：

最坏情况的概率低：虽然快速排序的最坏时间复杂度为 (O(n^2))，这比归并排序的稳定 (O(n \log n)) 要差，但这种情况出现的概率非常低。在绝大多数情况下，快速排序可以在 (O(n \log n)) 的时间复杂度下运行，因而能提供更高效的性能。
缓存使用效率高：快速排序在执行分区操作时，通常对相邻的元素进行访问。这种连续的内存访问方式使得整个子数组可以被有效加载到缓存中，从而提高访问效率。相比之下，像“堆排序”这样的算法需要频繁地进行跳跃式内存访问，导致缓存利用率不高，因此在实际运行中的表现不如快速排序。
时间复杂度中的常数系数小：在快速排序、归并排序和堆排序三种算法中，快速排序在比较、赋值和交换等操作的总数量上最少。这使得它的实际运行时间更短。这种情况类似于“插入排序”比“冒泡排序”更快的原因：尽管两者的时间复杂度都是 (O(n^2))，但插入排序所需的操作步骤更少，常数因子更小，因此在实际应用中表现得更快。

这些因素使得快速排序在实践中成为一种极其高效的排序算法，特别适合处理大规模、无序的数据集。

6. 归并排序 (Merge Sort)

6.1 核心算法

归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）思想的排序算法。它将数组分为两个子数组，对每个子数组递归进行排序，然后将排好序的子数组合并在一起。归并排序的时间复杂度为 (O(n \log n))，且其性能在各种情况下都相对稳定。

归并排序的核心思想如下：

分解（Divide）：将原始数组分成两个子数组，递归地对每个子数组进行排序。
合并（Conquer）：将两个已排序的子数组合并成一个排序的数组。
结束递归：当子数组的大小为1时，结束递归，因为一个大小为1的数组已经是有序的。

6.2 代码实现

以下是归并排序的Python代码实现：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr  # 基本情况：数组为空或只有一个元素，已排序
    
    # 分解步骤
    mid = len(arr) // 2  # 找到中间点
    left = merge_sort(arr[:mid])  # 递归排序左半部分
    right = merge_sort(arr[mid:])  # 递归排序右半部分
    
    # 合并步骤
    return merge(left, right)

def merge(left, right):
    result = []  # 用于存储合并后的结果
    i = j = 0  # 初始化两个指针
    
    # 合并两个已排序的子数组
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 处理剩余元素
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

基本情况：if len(arr) <= 1，数组为空或只有一个元素时，直接返回该数组，因为其已排序。
分解步骤：
- mid = len(arr) // 2：计算数组的中间位置。
- left = merge_sort(arr[:mid])：递归地对左半部分进行排序。
- right = merge_sort(arr[mid:])：递归地对右半部分进行排序。
合并步骤：merge(left, right) 合并两个已排序的子数组。
合并函数：
- 创建一个空数组 result 用于存储合并结果。
- 使用两个指针 i 和 j 分别指向 left 和 right 数组的开始位置。
- 比较 left[i] 和 right[j] 的大小，将较小的元素加入 result 并移动相应指针。
- 当其中一个数组的所有元素已被处理完时，将另一个数组的剩余元素直接添加到 result 中。

6.3 算法特性

归并排序具有以下几个特性：

稳定性：归并排序是稳定的排序算法，因为在合并过程中，相同大小的元素不会改变相对顺序。
时间复杂度：
- 最佳时间复杂度：(O(n \log n))。
- 平均时间复杂度：(O(n \log n))。
- 最坏时间复杂度：(O(n \log n))。
空间复杂度：(O(n)) —— 归并排序不是就地排序算法，它需要额外的存储空间来存放合并结果。
适用性：归并排序适合于大数据量且需要稳定排序的情况，例如外部排序（处理磁盘或其他外部存储器上的数据）。
递归性质：归并排序通过递归地处理较小的子问题来解决更大的问题，其递归深度为 (\log n)。
在线排序：归并排序是一种离线算法，因为它需要所有输入数据才能开始工作。

归并排序虽然空间复杂度较高，但在处理大规模数据集时性能稳定，且能够处理无法在内存中完全加载的大数据集合。

7. 堆排序 (Heap Sort)

7.1 核心算法

堆排序（Heap Sort）是一种基于堆这种数据结构的比较排序算法。堆是一棵完全二叉树，分为最大堆和最小堆。在最大堆中，每个节点的值都大于或等于其子节点的值，而在最小堆中，每个节点的值都小于或等于其子节点的值。堆排序利用最大堆来实现升序排序。

堆排序的核心思想如下：

构建最大堆：将原始数组转化为最大堆。
交换和调整堆：将堆顶元素（最大值）与末尾元素交换，然后将剩余的堆进行调整以恢复最大堆性质。
重复步骤：重复交换和调整堆的过程，直到堆的大小缩减为1，排序完成。

堆排序的时间复杂度为 (O(n \log n))，且它是一种就地排序算法，不需要额外的存储空间。

7.2 代码实现

以下是堆排序的Python代码实现：

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[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)  # 调整剩余部分为最大堆

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)

构建最大堆：通过从第一个非叶子节点开始（索引为 (n//2 - 1)）向上遍历，将数组转化为最大堆。每个节点与其子节点比较，调整位置以满足最大堆的性质。
排序步骤：
- 将堆顶（最大值）与当前堆的最后一个元素交换。
- 将剩下的部分重新调整为最大堆。
- 逐步减少堆的大小并重复上述过程，最终形成一个升序排列的数组。
堆调整函数 (heapify)：
- 确定当前节点与其左右子节点中的最大值的位置。
- 如果最大值不是当前节点，则交换它们，并递归调整下去，保持堆的性质。

7.3 算法特性

堆排序具有以下几个特性：

稳定性：堆排序不是稳定的排序算法，因为在交换过程中可能改变相同元素的相对顺序。
时间复杂度：
- 最佳时间复杂度：(O(n \log n))。
- 平均时间复杂度：(O(n \log n))。
- 最坏时间复杂度：(O(n \log n))。
空间复杂度：(O(1)) —— 堆排序是一种就地排序算法，只需要常数级别的额外空间。
适用性：堆排序适用于需要较少额外空间的排序场景，但由于不稳定性，在对稳定性有要求的场合不适合使用。
性能比较：堆排序在数据量较大时表现良好，特别是在不要求排序稳定性的场景下，能够有效地利用空间。
在线排序：堆排序是一种离线算法，需要所有输入数据才能开始工作。

堆排序虽然不稳定，但由于其时间复杂度在所有情况下均为 (O(n \log n))，且空间复杂度低，因此在某些内存敏感的应用中表现较为优秀。

8. 桶排序 (Bucket Sort)

8.1 核心算法

桶排序（Bucket Sort）是一种基于分布的排序算法，其核心思想是将数据分到有限数量的桶中，然后对每个桶中的数据进行排序，最后将各个桶中的数据合并得到最终的排序结果。桶排序特别适合用于处理均匀分布的数据集。

桶排序的核心步骤如下：

创建桶：根据数据的范围和数量创建若干个桶。
分配数据：将数据分配到对应的桶中，每个桶负责一部分数据。
排序桶内数据：对每个桶内的数据进行排序。可以使用其他排序算法，如插入排序或快速排序。
合并桶：将所有桶中的数据按顺序合并，得到排序后的结果。

8.2 代码实现

以下是桶排序的Python代码实现示例：

def bucket_sort(arr):
    if len(arr) == 0:
        return arr
    
    # 1. 创建桶
    min_value = min(arr)
    max_value = max(arr)
    bucket_count = len(arr)  # 选择桶的数量等于数组长度
    bucket_range = (max_value - min_value) / bucket_count + 1
    
    buckets = [[] for _ in range(bucket_count)]
    
    # 2. 分配数据到桶
    for num in arr:
        index = (num - min_value) // bucket_range
        buckets[int(index)].append(num)
    
    # 3. 对每个桶内的数据进行排序
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(sorted(bucket))
    
    return sorted_arr

创建桶：根据数据的范围（最小值和最大值）和桶的数量来决定每个桶的范围。这里使用了桶数量等于数组长度的策略，但可以根据实际需求调整桶的数量。
分配数据：计算每个数据应该放入哪个桶中，并将数据放入相应的桶。
排序桶内数据：对每个桶内的数据进行排序。示例中使用了Python内置的 sorted 函数，但可以根据实际需要选择其他排序算法。
合并桶：将所有桶中的数据合并成一个排序后的结果。

8.3 算法特性

桶排序具有以下几个特性：

稳定性：桶排序是一种稳定的排序算法，因为在桶内排序时保持了原始元素的相对顺序。
时间复杂度：
- 最佳时间复杂度：(O(n + k))，其中 (n) 是数据的数量，(k) 是桶的数量。
- 平均时间复杂度：(O(n + k))。
- 最坏时间复杂度：(O(n^2))，当桶内排序使用插入排序且数据分布不均时。
空间复杂度：(O(n + k)) —— 需要额外的空间来存储桶和桶内的数据。
适用性：桶排序适用于数据均匀分布且数据范围有限的情况，如浮点数排序、分数排序等。对数据分布不均的情况表现较差。
性能比较：当数据范围较小且分布较均匀时，桶排序可以提供非常高效的排序性能。对于数据分布不均的情况，桶排序的性能可能会下降。
在线排序：桶排序是一种离线算法，需要所有数据才能开始排序。

总的来说，桶排序在适用场景下具有优越的性能，但在数据分布不均或数据范围非常大的情况下，其效率可能会受到影响。在实际应用中，通常会结合其他排序算法来优化桶排序的性能。

9. 计数排序 (Counting Sort)

9.1 核心算法

计数排序（Counting Sort）是一种非比较型的排序算法，主要用于排序非负整数或有限范围内的整数。它通过计算数组中每个元素出现的次数，然后利用这些计数来直接构建排序后的数组。计数排序适合于数据范围有限且值的分布均匀的情况。

计数排序的核心步骤如下：

确定范围：找到待排序数组中的最大值和最小值。
计数：创建一个计数数组，用于记录每个值出现的次数。
累积计数：计算计数数组中每个位置的累积值，用于确定每个元素的最终位置。
排序：根据累积计数数组的值将元素放入正确的位置，构建排序后的数组。

9.2 代码实现

以下是计数排序的Python代码实现示例：

def counting_sort(arr):
    if len(arr) == 0:
        return arr
    
    # 1. 确定范围
    max_value = max(arr)
    min_value = min(arr)
    
    # 2. 初始化计数数组
    range_of_elements = max_value - min_value + 1
    count = [0] * range_of_elements
    
    # 3. 计数
    for num in arr:
        count[num - min_value] += 1
    
    # 4. 累积计数
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # 5. 排序
    sorted_arr = [0] * len(arr)
    for num in reversed(arr):
        index = count[num - min_value] - 1
        sorted_arr[index] = num
        count[num - min_value] -= 1
    
    return sorted_arr

确定范围：通过 max(arr) 和 min(arr) 找到数组中最大值和最小值，以确定计数数组的大小。
初始化计数数组：创建一个计数数组 count，长度为数据范围（最大值 - 最小值 + 1），初始值全为0。
计数：遍历输入数组，将每个元素对应位置的计数数组值加1。
累积计数：遍历计数数组，将每个位置的值变为其前面所有值的和，用于确定每个元素的最终位置。
排序：从输入数组的最后一个元素开始，将其放到正确的位置，并更新计数数组。最终得到排序后的数组。

9.3 算法特性

计数排序具有以下几个特性：

稳定性：计数排序是一种稳定的排序算法，因为它按输入数组的顺序放置元素，并保持相同值的元素相对顺序不变。
时间复杂度：
- 最佳时间复杂度：(O(n + k))，其中 (n) 是待排序的元素个数，(k) 是数据的范围（最大值与最小值之差）。
- 平均时间复杂度：(O(n + k))。
- 最坏时间复杂度：(O(n + k))。
空间复杂度：(O(n + k)) —— 计数排序需要额外的空间来存储计数数组和排序结果数组。
适用性：计数排序适用于数据范围有限且整数值较小的情况，如成绩排序、字母表排序等。对于数据范围非常大的情况，计数排序的空间复杂度可能会导致问题。
性能比较：当数据范围较小且分布均匀时，计数排序的性能非常高效。对于数据范围很大的情况，计数排序可能会变得不适用，因为计数数组的大小会迅速增加。
在线排序：计数排序是一种离线算法，需要所有输入数据才能开始排序。

总的来说，计数排序是一种高效的排序算法，但其适用场景有限。对于范围较小的非负整数数据，计数排序能够提供非常好的性能。

10. 基数排序 (Radix Sort)

10.1 核心算法

基数排序（Radix Sort）是一种非比较型的排序算法，适用于排序整数数据。它通过将数据按位数进行排序来实现排序过程。基数排序的关键在于对数据的各个位数进行逐步排序，通常从最低有效位（LSD）开始排序，逐步到最高有效位（MSD）。基数排序可以利用稳定的子排序算法（如计数排序）来对各位进行排序。

基数排序的核心步骤如下：

确定最大值：找到待排序数组中的最大值，以确定排序的位数。
逐位排序：从最低有效位（LSD）开始，对数据进行逐位排序，直到排序到最高有效位（MSD）。
使用稳定的排序算法：对每一位进行排序时，使用稳定的排序算法（如计数排序）以保持排序的稳定性。

10.2 代码实现

以下是基数排序的Python代码实现示例：

def radix_sort(arr):
    if len(arr) == 0:
        return arr
    
    # 1. 找到最大值
    max_value = max(arr)
    exp = 1  # 初始位数为个位
    
    # 2. 按位排序
    while max_value // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    
    return arr

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # 计数数组（针对0-9的位数）

    # 计数排序中每位数出现的次数
    for num in arr:
        index = (num // exp) % 10
        count[index] += 1
    
    # 累积计数
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # 从后向前排序
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
    
    # 复制排序结果到原数组
    for i in range(n):
        arr[i] = output[i]

确定最大值：通过 max(arr) 找到数组中最大值，以确定需要排序的位数。
逐位排序：
- 从个位开始，每次将 exp （表示当前位数的权重）乘以10，逐步排序到最高有效位。
- 对每一位，调用 counting_sort_by_digit 函数进行排序。
使用稳定的排序算法：在 counting_sort_by_digit 函数中使用计数排序对每个位进行排序。
计数排序按位：
- 创建计数数组 count，用于记录每个数字（0-9）的出现次数。
- 对计数数组进行累积，以便确定每个数字在输出数组中的位置。
- 从后向前遍历输入数组，按累积计数数组确定每个元素的位置，并填充到输出数组中。
复制排序结果：将排序后的结果复制回原数组。

10.3 算法特性

基数排序具有以下几个特性：

稳定性：基数排序是一种稳定的排序算法，因为它使用稳定的排序算法（如计数排序）来对各位进行排序。
时间复杂度：
- 最佳时间复杂度：(O(n \cdot k))，其中 (n) 是待排序的元素个数，(k) 是位数（即最大数字的位数）。
- 平均时间复杂度：(O(n \cdot k))。
- 最坏时间复杂度：(O(n \cdot k))。
空间复杂度：(O(n + k)) —— 需要额外的空间来存储计数数组和输出数组。
适用性：基数排序适用于排序非负整数或其他离散的数据类型，尤其是当数据的位数较小且数据量较大的时候。对于大范围数据或浮点数，基数排序的空间复杂度可能较高。
性能比较：当数据位数较少且数据量较大时，基数排序可以非常高效。然而，对于数据范围非常大的情况，基数排序的性能可能受到限制，因为位数增加会导致时间复杂度和空间复杂度上升。
在线排序：基数排序是一种离线算法，需要所有数据才能开始排序。

总的来说，基数排序在适用场景下能够提供非常高效的排序性能，但其适用性受到数据类型和范围的限制。在处理大数据量且数据位数较少的情况下，基数排序是一种非常有效的排序算法。