数据结构（第八章排序算法）

一.直接插入排序

直接插入排序（Insertion Sort） 是一种简单直观的排序算法。它的工作原理类似于整理扑克牌：每次从未排序部分取出一个元素，将其插入到已排序部分的适当位置，直到所有元素都被排序。

---

1. 算法思想

将数组分为两部分：已排序部分和未排序部分。

初始时，已排序部分只包含第一个元素，未排序部分包含剩余元素。

每次从未排序部分取出第一个元素，将其插入到已排序部分的适当位置。

重复上述过程，直到未排序部分为空。

---

2. 算法步骤

从第二个元素开始（假设第一个元素已排序）。

将当前元素与已排序部分的元素从后向前比较。

如果当前元素小于已排序部分的元素，则将已排序部分的元素向后移动一位。

重复步骤 3，直到找到当前元素的正确位置。

将当前元素插入到正确位置。

重复上述过程，直到所有元素都被排序。

---

3. 代码实现 C++ 实现 void insertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; // 当前待插入的元素 int j = i - 1; // 将比 key 大的元素向后移动 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } // 插入 key 到正确位置 arr[j + 1] = key; } } Python 实现 def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] # 当前待插入的元素 j = i - 1 # 将比 key 大的元素向后移动 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 # 插入 key 到正确位置 arr[j + 1] = key

---

4. 示例

假设数组为 [5, 2, 4, 6, 1, 3]，排序过程如下：

初始状态：[5, 2, 4, 6, 1, 3]

插入 2：[2, 5, 4, 6, 1, 3]

插入 4：[2, 4, 5, 6, 1, 3]

插入 6：[2, 4, 5, 6, 1, 3]

插入 1：[1, 2, 4, 5, 6, 3]

插入 3：[1, 2, 3, 4, 5, 6]

最终排序结果：[1, 2, 3, 4, 5, 6]

---

5. 时间复杂度

最坏情况：数组完全逆序，时间复杂度为 O(n2)。

最好情况：数组已经有序，时间复杂度为 O(n)。

平均情况：时间复杂度为 O(n2)。

---

6. 空间复杂度

直接插入排序是 原地排序算法，空间复杂度为 O(1)。

---

7. 稳定性

直接插入排序是 稳定排序算法，相同元素的相对位置不会改变。

---

8. 优缺点 优点：

实现简单，代码易于理解。

对小规模数据或基本有序的数据效率较高。

是稳定排序算法。

缺点：

对大规模数据效率较低，时间复杂度为 O(n2)O(n2)。

不适合数据量较大的场景。

---

9. 适用场景

数据量较小。

数据基本有序。

需要稳定排序的场景。

---

10. 优化 10.1 二分插入排序

在查找插入位置时，使用二分查找将时间复杂度从 O(n)优化到 O(log⁡n)。

但移动元素的时间复杂度仍为 O(n)，因此总体时间复杂度仍为 O(n2)。

代码实现： void binaryInsertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int left = 0, right = i - 1; // 二分查找插入位置 while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] > key) { right = mid - 1; } else { left = mid + 1; } } // 移动元素 for (int j = i - 1; j >= left; j--) { arr[j + 1] = arr[j]; } // 插入元素 arr[left] = key; } } 二.折半插入排序

折半插入排序（Binary Insertion Sort） 是直接插入排序的一种优化版本。它通过 二分查找 来减少比较次数，从而提高查找插入位置的效率。尽管移动元素的时间复杂度仍然是 O(n)，但折半插入排序在数据量较大时比直接插入排序更快。

---

1. 算法思想

将数组分为两部分：已排序部分和未排序部分。

初始时，已排序部分只包含第一个元素，未排序部分包含剩余元素。

每次从未排序部分取出第一个元素，使用二分查找确定其在已排序部分的插入位置。

将元素插入到正确位置，并移动后续元素。

重复上述过程，直到未排序部分为空。

---

2. 算法步骤

从第二个元素开始（假设第一个元素已排序）。

使用二分查找在已排序部分中找到当前元素的插入位置。

将插入位置后的所有元素向后移动一位。

将当前元素插入到正确位置。

重复上述过程，直到所有元素都被排序。

---

3. 代码实现 C++ 实现 void binaryInsertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; // 当前待插入的元素 int left = 0, right = i - 1; // 二分查找插入位置 while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] > key) { right = mid - 1; } else { left = mid + 1; } } // 移动元素 for (int j = i - 1; j >= left; j--) { arr[j + 1] = arr[j]; } // 插入元素 arr[left] = key; } } Python 实现 def binary_insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] # 当前待插入的元素 left, right = 0, i - 1 # 二分查找插入位置 while left <= right: mid = left + (right - left) // 2 if arr[mid] > key: right = mid - 1 else: left = mid + 1 # 移动元素 for j in range(i - 1, left - 1, -1): arr[j + 1] = arr[j] # 插入元素 arr[left] = key

---

4. 示例

假设数组为 [5, 2, 4, 6, 1, 3]，排序过程如下：

初始状态：[5, 2, 4, 6, 1, 3]

插入 2：[2, 5, 4, 6, 1, 3]

插入 4：[2, 4, 5, 6, 1, 3]

插入 6：[2, 4, 5, 6, 1, 3]

插入 1：[1, 2, 4, 5, 6, 3]

插入 3：[1, 2, 3, 4, 5, 6]

最终排序结果：[1, 2, 3, 4, 5, 6]

---

5. 时间复杂度

查找插入位置：使用二分查找，时间复杂度为 O(log⁡n)。

移动元素：最坏情况下需要移动 O(n)个元素。

总体时间复杂度：O(n2)。

尽管查找插入位置的时间复杂度降低到 O(log⁡n)，但由于移动元素的时间复杂度仍然是O(n)，因此总体时间复杂度仍为O(n2)。

---

6. 空间复杂度

折半插入排序是 原地排序算法，空间复杂度为 O(1)。

---

7. 稳定性

折半插入排序是 稳定排序算法，相同元素的相对位置不会改变。

---

8. 优缺点 优点：

比直接插入排序减少了比较次数，适合数据量较大的场景。

实现简单，代码易于理解。

是稳定排序算法。

缺点：

移动元素的时间复杂度仍然是 O(n)，总体时间复杂度为 O(n2)。

不适合数据量非常大的场景。

---

9. 适用场景

数据量较大且需要稳定排序的场景。

数据基本有序时，效率较高。

---

10. 与直接插入排序的比较 特性直接插入排序折半插入排序比较次数O(n2)O(nlog⁡n)移动次数O(n2)O(n2）时间复杂度O(n2)O(n2)适用场景数据量较小或基本有序数据量较大或基本有序 三.希尔排序

希尔排序（Shell Sort） 是插入排序的一种高效改进版本，也称为 缩小增量排序。它通过将数组分成若干子序列，对每个子序列进行插入排序，逐步减少子序列的长度，最终完成整个数组的排序。希尔排序的核心思想是 使数组中任意间隔为 h 的元素有序，从而减少后续插入排序的工作量。

---

1. 算法思想

增量序列：选择一个增量序列 h1,h2,…,hk，其中 h1>h2>⋯>hk=1。

分组插入排序：对于每个增量 hihi​，将数组分成若干子序列，每个子序列包含间隔为 hihi​ 的元素，对每个子序列进行插入排序。

逐步缩小增量：重复上述过程，直到增量为 1，此时对整个数组进行插入排序。

---

2. 算法步骤

选择一个增量序列（如 h=n/2,n/4,…,1）。

对于每个增量 hh：

将数组分成若干子序列，每个子序列包含间隔为 h 的元素。

对每个子序列进行插入排序。

重复上述过程，直到增量为 1，此时对整个数组进行插入排序。

---

3. 代码实现 C++ 实现 void shellSort(int arr[], int n) { // 选择增量序列 for (int h = n / 2; h > 0; h /= 2) { // 对每个子序列进行插入排序 for (int i = h; i < n; i++) { int key = arr[i]; int j = i; // 插入排序 while (j >= h && arr[j - h] > key) { arr[j] = arr[j - h]; j -= h; } arr[j] = key; } } } Python 实现 def shell_sort(arr): n = len(arr) # 选择增量序列 h = n // 2 while h > 0: # 对每个子序列进行插入排序 for i in range(h, n): key = arr[i] j = i # 插入排序 while j >= h and arr[j - h] > key: arr[j] = arr[j - h] j -= h arr[j] = key h //= 2

---

4. 示例

假设数组为 [5, 2, 4, 6, 1, 3]，增量序列为 [3, 1]，排序过程如下：

增量 h=3：

子序列 1：[5, 6] → 排序后：[5, 6]

子序列 2：[2, 1] → 排序后：[1, 2]

子序列 3：[4, 3] → 排序后：[3, 4]

数组变为：[5, 1, 3, 6, 2, 4]

增量 h=1：

对整个数组进行插入排序：

插入 1：[1, 5, 3, 6, 2, 4]

插入 3：[1, 3, 5, 6, 2, 4]

插入 6：[1, 3, 5, 6, 2, 4]

插入 2：[1, 2, 3, 5, 6, 4]

插入 4：[1, 2, 3, 4, 5, 6]

最终排序结果：[1, 2, 3, 4, 5, 6]

---

5. 时间复杂度

最坏情况：取决于增量序列的选择，通常为 O(n2)。

最好情况：当数组已经有序时，时间复杂度为 O(nlog⁡n)。

平均情况：取决于增量序列的选择，通常为 O()。

---

6. 空间复杂度

希尔排序是 原地排序算法，空间复杂度为 O(1)。

---

7. 稳定性

希尔排序是 不稳定排序算法，相同元素的相对位置可能会改变。

---

8. 优缺点 优点：

比直接插入排序效率更高，尤其是对中等规模的数据。

实现简单，代码易于理解。

是原地排序算法，空间复杂度低。

缺点：

时间复杂度依赖于增量序列的选择。

是不稳定排序算法。

---

9. 增量序列的选择

增量序列的选择对希尔排序的性能有很大影响。常见的增量序列包括：

Shell 增量序列：h=n/2,n/4,…,1。

Hibbard 增量序列：h=1,3,7,15,…,2k−1。

Sedgewick 增量序列：结合了 Shell 和 Hibbard 的优点，性能更好。

---

10. 适用场景

数据量中等。

对稳定性没有要求。

需要原地排序的场景。

---

11. 与插入排序的比较 特性直接插入排序希尔排序时间复杂度O(n2) O()空间复杂度O(1)O(1)稳定性稳定不稳定适用场景数据量较小或基本有序数据量中等 四.冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复地遍历列表，比较相邻的元素并交换它们的位置，直到整个列表有序为止。它的名字来源于较小的元素会像“气泡”一样逐渐“浮”到列表的顶端。

---

算法步骤

遍历列表：从列表的第一个元素开始，依次比较相邻的两个元素。

比较与交换：如果前一个元素比后一个元素大（升序排序），则交换它们的位置。

重复过程：重复上述步骤，直到没有需要交换的元素，列表完全有序。

---

时间复杂度

最坏情况：O(n²)（列表完全逆序）

平均情况：O(n²)

最好情况：O(n)（列表已经有序）

---

空间复杂度

O(1)（原地排序，不需要额外空间）

---

代码实现（Python） 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 = [64, 34, 25, 12, 22, 11, 90] sorted_arr = bubble_sort(arr) print("排序后的数组:", sorted_arr)

---

示例运行结果 排序后的数组: [11, 12, 22, 25, 34, 64, 90]

c++

for(int i = 0 ; i < n ; i ++) { for(int j = 0 ; j < n - i - 1; j ++) { if(a[j] > a[j+1]) { int t = a[j+1]; a[j+1] = a[j]; a[j] = t; } } }

---

优化

提前终止：如果在某次遍历中没有发生任何交换，说明列表已经有序，可以提前终止算法。

记录最后一次交换位置：可以记录最后一次交换的位置，减少不必要的比较。

---

适用场景

适用于小规模数据或部分有序的数据。

对于大规模数据，冒泡排序的效率较低，通常选择更高效的排序算法（如快速排序、归并排序等）

五.快速排序

快速排序（Quick Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略。它的核心思想是通过选择一个基准元素（pivot），将数组分为两部分：一部分比基准元素小，另一部分比基准元素大，然后递归地对这两部分进行排序。

---

算法步骤

选择基准元素：从数组中选择一个元素作为基准（通常选择第一个元素、最后一个元素或中间元素）。

分区操作：

将数组分为两部分：一部分比基准元素小，另一部分比基准元素大。

基准元素最终位于正确的位置。

递归排序：对基准元素左右两部分分别递归调用快速排序。

---

时间复杂度

平均情况：O(n log n)

最坏情况：O(n²)（当数组已经有序或完全逆序时，取决于基准元素的选择）

最好情况：O(n log n)

---

空间复杂度

O(log n)（递归调用栈的深度）

---

代码实现（Python） def quick_sort(arr): # 如果数组长度小于等于1，直接返回 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 = [64, 34, 25, 12, 22, 11, 90] sorted_arr = quick_sort(arr) print("排序后的数组:", sorted_arr)

---

示例运行结果

复制

排序后的数组: [11, 12, 22, 25, 34, 64, 90]

---

优化

随机选择基准元素：避免最坏情况（如数组已经有序），可以随机选择基准元素。

三数取中法：选择第一个、最后一个和中间元素的中位数作为基准元素。

小数组使用插入排序：当数组规模较小时，插入排序的效率更高。

---

适用场景

快速排序是实际应用中最常用的排序算法之一，适用于大规模数据。

对于小规模数据，插入排序或冒泡排序可能更高效。

六.简单选择排序

简单选择排序（Selection Sort）是一种直观的排序算法。它的核心思想是每次从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾，直到所有元素有序。

---

算法步骤

初始化：将数组分为已排序部分和未排序部分。初始时，已排序部分为空，未排序部分为整个数组。

选择最小元素：在未排序部分中找到最小元素。

交换位置：将最小元素与未排序部分的第一个元素交换位置。

更新已排序部分：将交换后的元素纳入已排序部分。

重复过程：重复上述步骤，直到未排序部分为空。

---

时间复杂度

最坏情况：O(n²)

平均情况：O(n²)

最好情况：O(n²)

无论输入数据的分布如何，选择排序都需要进行 n(n-1)/2 次比较。

---

空间复杂度

O(1)（原地排序，不需要额外空间）

---

代码实现（Python） def selection_sort(arr): n = len(arr) for i in range(n): # 假设当前未排序部分的第一个元素是最小的 min_index = i # 在未排序部分中找到最小元素的索引 for j in range(i+1, n): if arr[j] < arr[min_index]: min_index = j # 将最小元素与未排序部分的第一个元素交换 arr[i], arr[min_index] = arr[min_index], arr[i] return arr # 示例 arr = [64, 34, 25, 12, 22, 11, 90] sorted_arr = selection_sort(arr) print("排序后的数组:", sorted_arr)

---

示例运行结果

复制

排序后的数组: [11, 12, 22, 25, 34, 64, 90]

---

特点

简单直观：算法逻辑简单，易于实现。

不稳定性：选择排序是一种不稳定的排序算法（可能改变相同元素的相对顺序）。

适合小规模数据：对于小规模数据，选择排序的效率尚可接受；但对于大规模数据，效率较低。

---

适用场景

适用于数据量较小的情况。

当内存空间有限时，选择排序是一种不错的选择（原地排序）。

七.堆堆排

堆排序（Heap Sort） 是一种基于 二叉堆 数据结构的排序算法。它通过构建最大堆（或最小堆）来实现排序，具有 O(nlog⁡n)O(nlogn) 的时间复杂度，是一种高效的排序算法。

---

1. 算法思想

构建最大堆：将待排序数组构建成一个最大堆（父节点的值大于子节点的值）。

交换堆顶元素：将堆顶元素（最大值）与堆的最后一个元素交换，然后将堆的大小减 1。

调整堆：对剩余的堆进行调整，使其重新满足最大堆的性质。

重复步骤 2 和 3：直到堆的大小为 1，排序完成。

---

2. 算法步骤

构建最大堆：

从最后一个非叶子节点开始，依次向上调整每个子树，使其满足最大堆的性质。

交换堆顶元素：

将堆顶元素（最大值）与堆的最后一个元素交换。

调整堆：

对剩余的堆进行调整，使其重新满足最大堆的性质。

重复步骤 2 和 3：

直到堆的大小为 1，排序完成。

---

3. 代码实现 C++ 实现 void heapify(int arr[], int n, int i) { int largest = i; // 初始化最大值为根节点 int left = 2 * i + 1; // 左子节点 int right = 2 * i + 2; // 右子节点 // 如果左子节点大于根节点 if (left < n && arr[left] > arr[largest]) { largest = left; } // 如果右子节点大于当前最大值 if (right < n && arr[right] > arr[largest]) { largest = right; } // 如果最大值不是根节点 if (largest != i) { swap(arr[i], arr[largest]); // 交换 heapify(arr, n, largest); // 递归调整子树 } } void heapSort(int arr[], int n) { // 构建最大堆 for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 交换堆顶元素并调整堆 for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); // 交换堆顶元素和最后一个元素 heapify(arr, i, 0); // 调整堆 } } Python 实现 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) # 调整堆

---

4. 示例

假设数组为 [5, 2, 4, 6, 1, 3]，排序过程如下：

构建最大堆：

初始数组：[5, 2, 4, 6, 1, 3]

构建后的最大堆：[6, 5, 4, 2, 1, 3]

交换堆顶元素：

交换堆顶元素 6 和最后一个元素 3，数组变为：[3, 5, 4, 2, 1, 6]

调整堆：[5, 3, 4, 2, 1, 6]

重复交换和调整：

交换堆顶元素 5 和最后一个元素 1，数组变为：[1, 3, 4, 2, 5, 6]

调整堆：[4, 3, 1, 2, 5, 6]

继续交换和调整，直到堆的大小为 1。

最终排序结果：[1, 2, 3, 4, 5, 6]

---

5. 时间复杂度

构建最大堆：O(n)。

每次调整堆：O(log⁡n)。

总体时间复杂度：O(nlog⁡n)。

---

6. 空间复杂度

堆排序是 原地排序算法，空间复杂度为 O(1)。

---

7. 稳定性

堆排序是 不稳定排序算法，相同元素的相对位置可能会改变。

---

8. 优缺点 优点：

时间复杂度为 O(nlog⁡n)，效率较高。

是原地排序算法，空间复杂度低。

缺点：

是不稳定排序算法。

对缓存不友好，因为堆排序的访问模式是跳跃式的。

---

9. 适用场景

数据量较大。

对稳定性没有要求。

需要原地排序的场景。

---

10. 与其他排序算法的比较 特性堆排序快速排序归并排序时间复杂度O(nlog⁡n)O(nlog⁡n)O(nlog⁡n)空间复杂度O(1)O(log⁡n)O(n)稳定性不稳定不稳定稳定适用场景数据量较大数据量较大数据量较大且需要稳定排序 八.归并排序

归并排序是一种分治算法，它将一个数组分成若干个子数组，分别对子数组进行排序，然后将排序好的子数组合并成一个有序的数组。以下是归并排序的详细解释和实现：

---

归并排序的基本思想

分治法：将数组分成两部分，分别对这两部分进行排序，最后将排序好的两部分合并。

递归：通过递归的方式将数组不断分割，直到每个子数组只有一个元素（单个元素是有序的）。

合并：将两个有序的子数组合并成一个有序数组。

---

归并排序的步骤

分割：将数组从中间分成两部分，递归地对左右两部分进行归并排序。

合并：将两个有序的子数组合并成一个有序数组。合并过程是归并排序的核心。

---

合并过程

假设有两个有序数组 left 和 right，我们需要将它们合并成一个有序数组 result：

初始化两个指针 i 和 j，分别指向 left 和 right 的第一个元素。

比较 left[i] 和 right[j]：

如果 left[i] < right[j]，将 left[i] 放入 result，并将 i 向右移动一位。

否则，将 right[j] 放入 result，并将 j 向右移动一位。

当一个数组的所有元素都被放入 result 后，将另一个数组的剩余部分直接追加到 result。

---

归并排序的时间复杂度

时间复杂度：O(n log n)，其中 n 是数组的长度。分割过程是 O(log n)，合并过程是 O(n)。

空间复杂度：O(n)，因为需要额外的空间来存储合并后的数组。

---

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 # 示例 arr = [38, 27, 43, 3, 9, 82, 10] sorted_arr = merge_sort(arr) print("排序后的数组:", sorted_arr)

---

归并排序的特点

稳定性：归并排序是一种稳定的排序算法，即相同元素的相对顺序在排序后不会改变。

适用性：适合处理大规模数据，尤其是链表排序。

缺点：需要额外的存储空间，空间复杂度较高。

九.基数排序

基数排序（Radix Sort）是一种非比较型的排序算法，它通过逐位处理数据，将数字或字符串按照每一位的值进行分桶和合并，从而实现排序。以下是关于基数排序的详细介绍：

---

基数排序的基本思想

基数排序的核心在于分桶和合并。它不依赖于元素之间的直接比较，而是通过元素的位权信息（如数字的个位、十位、百位等）进行排序。

基数排序有两种主要的实现方式：

最低有效位优先（LSD，Least Significant Digit）：从最低位（个位）开始排序，逐步向最高位（如百位、千位）进行。

最高有效位优先（MSD，Most Significant Digit）：从最高位开始排序，递归地对每个桶中的元素进行排序。

---

算法步骤（以LSD为例）

确定最大值的位数：找到数组中的最大值，确定需要处理的最大位数。

按位分桶排序：

从最低位（个位）开始，根据当前位的值将数组中的元素放入对应的桶中（0-9）。

按桶的顺序收集元素，形成新的序列。

逐步处理更高位，重复上述步骤，直到处理完最高位。

---

时间复杂度

基数排序的时间复杂度为 O(kn)，其中 n 是数组的长度，k 是最大值的位数。在整数排序中，如果位数相对固定，基数排序的时间复杂度接近线性时间 O(n)。

---

空间复杂度

基数排序需要额外的空间来存储桶，空间复杂度为 O(n + k)，其中 k 是基数（通常为10，对应十进制）。

---

稳定性

基数排序是一种稳定的排序算法。在每一轮排序中，相同位值的元素会保持原有的相对顺序。

---

Python实现 def radix_sort(arr): if not arr: return arr max_num = max(arr) # 找到最大值 exp = 1 # 初始位权（个位） while max_num // exp > 0: # 直到处理完最高位 buckets = [[] for _ in range(10)] # 创建10个桶 for num in arr: buckets[(num // exp) % 10].append(num) # 按当前位放入桶 arr = [num for bucket in buckets for num in bucket] # 按桶顺序收集 exp *= 10 # 提升位权 return arr

---

应用场景

基数排序适用于以下场景：

整数排序：尤其是当整数的位数相对固定时。

字符串排序：可以将字符串的每个字符视为一个“位”。

大数据处理：由于其线性时间复杂度，在处理大规模数据时表现出色。

---

基数排序通过分桶和合并的方式，避免了传统比较排序的时间瓶颈，是一种高效且稳定的排序算法。

十.计数排序

计数排序（Counting Sort）是一种非比较型的排序算法，适用于一定范围内的整数排序。它的核心思想是利用一个额外的数组（计数数组）来统计每个整数出现的次数，从而实现快速排序。计数排序是一种非常高效的排序算法，尤其在数据范围较小时表现突出。

---

计数排序的基本思想

计数排序的核心在于**“计数”和“定位”**：

计数：统计每个整数出现的次数。

定位：根据计数结果，直接将每个整数放到它在排序后数组中的正确位置。

计数排序的关键在于它不依赖于元素之间的比较，而是通过“计数”来实现排序，因此它的效率非常高。

---

计数排序的步骤

假设有一个数组 arr，其中的整数范围为 [min_value, max_value]，计数排序的步骤如下：

确定范围：找到数组中的最小值 min_value 和最大值 max_value，确定整数的范围。

创建计数数组：创建一个大小为 range_size = max_value - min_value + 1 的计数数组 count，初始化为 0。

统计频率：遍历原数组 arr，对于每个元素 arr[i]，将其对应的计数数组位置 count[arr[i] - min_value] 加 1。

计算前缀和（可选）：如果需要稳定排序，需要对计数数组计算前缀和，以确定每个元素在排序后数组中的位置。

输出排序结果：根据计数数组，将元素按顺序放入结果数组中。

---

计数排序的稳定性

计数排序是一种稳定的排序算法。为了保持稳定性，需要从后向前填充结果数组。

---

时间复杂度

时间复杂度：O(n + k)，其中 n 是数组的长度，k 是整数范围（max_value - min_value）。当 k 不大时，计数排序非常高效。

空间复杂度：O(k)，需要额外的计数数组。

---

Python实现 def counting_sort(arr): if not arr: return [] # 确定范围 min_value = min(arr) max_value = max(arr) range_size = max_value - min_value + 1 # 创建计数数组 count = [0] * range_size # 统计频率 for num in arr: count[num - min_value] += 1 # 计算前缀和（可选，用于稳定排序） for i in range(1, range_size): count[i] += count[i - 1] # 输出排序结果 output = [0] * len(arr) for num in reversed(arr): # 从后向前填充，保证稳定性 output[count[num - min_value] - 1] = num count[num - min_value] -= 1 return output # 示例 arr = [4, 2, 2, 8, 3, 3, 1] sorted_arr = counting_sort(arr) print("排序后的数组:", sorted_arr)

---

应用场景

计数排序适用于以下场景：

整数排序：当整数范围较小（如 0 到 100）时，计数排序非常高效。

数据范围已知：如果数据范围已知且范围较小，计数排序是理想选择。

需要稳定排序：计数排序是一种稳定的排序算法，适合对稳定性有要求的场景。

---

注意事项

数据范围：如果整数范围非常大（如 1 到 10^9），计数排序的空间复杂度会很高，此时不适合使用。

非整数数据：计数排序主要用于整数排序。如果数据是非整数类型（如浮点数或字符串），需要转换为整数范围或使用其他排序算法。

---

计数排序通过“计数”而非“比较”来实现排序，是一种非常高效且稳定的排序算法，特别适合处理范围较小的整数数据。