好的，没问题！作为你的数据结构与算法老师，很高兴带你一起学习排序算法。排序是计算机科学中最基本也最重要的算法之一，理解它能帮助我们更好地处理和组织数据。
我们将按照从简单到复杂、从直观到巧妙的顺序，一个一个地深入剖析常见的排序算法。每个算法，我们都会按照以下步骤来讲解：
- 理解题目与目的： 排序算法的通用目的是什么？这个特定算法的核心思想是什么？
- 思路与实现： 如何一步步想到这个算法？它的具体执行流程是怎样的？提供 Go 语言实现。
- 复杂度分析与特点： 这个算法的时间复杂度、空间复杂度是多少？它是稳定的吗？（稳定排序是指相等元素的相对顺序在排序后保持不变）它是原地排序吗？（原地排序是指只需要常数额外空间的排序）
- 解题模式与适用场景： 这个算法的核心模式是什么？它适用于哪些情况？有哪些优缺点？
- 泛化与对比： 与其他排序算法有什么异同？有没有变体？
让我们开始吧！
排序算法的通用目的：
给定一个元素序列，将其重新排列，使得序列中的元素满足某种顺序关系（通常是升序或降序）。
考察内容：
排序算法主要考察的是如何通过比较和移动元素，高效地达到有序状态。不同的算法体现了不同的策略和权衡（如时间效率 vs. 空间效率，稳定性 vs. 原地性）。
1. 冒泡排序 (Bubble Sort) - 最直观的 O(n^2) 算法 #
1. 理解题目与目的：
冒泡排序是最简单的排序算法之一。它的目的是通过重复遍历待排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作会重复进行，直到没有再需要交换，也就是说该数列已经排序完成。
核心思想：就像水中的气泡一样，较大的（或较小的，取决于排序方向）元素会逐渐“冒”到序列的末尾（或开头）。
2. 思路与实现：
思路：
- 从序列的第一个元素开始，比较它与下一个元素。
- 如果第一个元素比第二个元素大（以升序为例），则交换它们的位置。
- 移动到下一对相邻元素，重复步骤 2。
- 一轮遍历结束后，最大的元素就会被“冒泡”到序列的最后一个位置。
- 对剩余的未排序部分重复以上步骤，直到整个序列有序。
- 优化：如果在某一轮遍历中没有发生任何交换，说明序列已经有序，可以提前终止。
Go 语言实现：
package main
import "fmt"
// BubbleSort 冒泡排序实现
func BubbleSort(arr []int) []int {
n := len(arr)
// 外层循环控制遍历的轮数，每轮确定一个最大元素的位置
for i := 0; i < n-1; i++ {
// 标记本轮是否发生了交换，用于优化
swapped := false
// 内层循环负责比较和交换相邻元素，范围逐渐减小
for j := 0; j < n-1-i; j++ {
// 如果前一个元素比后一个大，交换它们
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = true // 发生了交换
}
}
// 如果本轮没有发生交换，说明数组已经有序，提前退出
if !swapped {
break
}
}
return arr
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
sortedArr := BubbleSort(arr)
fmt.Println("冒泡排序后:", sortedArr)
}
3. 复杂度分析与特点：
- 时间复杂度：
- 最好情况 (已排序): $O(n)$ (因为有优化，只需要一轮遍历)
- 最坏情况 (逆序): $O(n^2)$ (需要进行 $n-1$ 轮遍历，每轮比较次数逐渐减少，总比较次数约是 $n^2/2$)
- 平均情况: $O(n^2)$
- 空间复杂度： $O(1)$ (只需要常数额外的空间进行交换)
- 稳定性： 稳定 (只有相邻元素进行比较和交换，相等元素的相对位置不会改变)
- 原地排序： 是 (排序过程只在原数组上进行)
4. 解题模式与适用场景：
模式：通过不断比较和交换相邻元素，将极值“冒泡”到一端。 适用场景：
- 数据规模非常小。
- 教学或演示，因为它非常直观易懂。
- 在某些特定优化后（如已排序检测）可能对接近有序的序列有所帮助，但通常不如插入排序效率高。
5. 泛化与对比：
冒泡排序是比较排序中最简单的一种。它的效率较低，通常不用于实际应用。与选择排序和插入排序同属 $O(n^2)$ 级别的简单排序，但它们的工作方式不同。选择排序是找到最小/最大元素放到正确位置，插入排序是构建有序子序列。
2. 选择排序 (Selection Sort) - 每次选择一个极值 #
1. 理解题目与目的：
选择排序的目的是每次从未排序的部分中找到最小（或最大）的元素，然后将其放到已排序部分的末尾。
核心思想：分阶段，每阶段从剩余元素中“选择”一个最合适的放到正确位置。
2. 思路与实现：
思路：
- 将序列分为已排序和未排序两个部分。初始时，已排序部分为空，未排序部分包含所有元素。
- 从未排序部分中找到最小的元素。
- 将找到的最小元素与未排序部分的第一个元素（也就是当前轮次的起始元素）交换位置。这样，最小元素就进入了已排序部分的末尾。
- 重复步骤 2 和 3，直到未排序部分为空。
Go 语言实现：
package main
import "fmt"
// SelectionSort 选择排序实现
func SelectionSort(arr []int) []int {
n := len(arr)
// 外层循环控制已排序部分的边界
for i := 0; i < n-1; i++ {
// 假设当前未排序部分的第一个元素是最小值
minIndex := i
// 内层循环在未排序部分查找真正的最小值
for j := i + 1; j < n; j++ {
if arr[j] < arr[minIndex] {
minIndex = j // 找到新的最小值索引
}
}
// 如果最小值不是当前位置的元素，则交换它们
if minIndex != i {
arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
}
return arr
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
sortedArr := SelectionSort(arr)
fmt.Println("选择排序后:", sortedArr)
}
3. 复杂度分析与特点：
- 时间复杂度：
- 最好情况: $O(n^2)$
- 最坏情况: $O(n^2)$
- 平均情况: $O(n^2)$ (无论原始序列如何，都需要进行 $n-1$ 轮选择，每轮都需要遍历剩余未排序元素，所以比较次数固定)
- 空间复杂度： $O(1)$ (只需要常数额外的空间进行交换)
- 稳定性： 不稳定 (例如，序列 5 8 5 2，第一次会把 2 和第一个 5 交换，改变了两个 5 的相对顺序)
- 原地排序： 是
4. 解题模式与适用场景：
模式：通过多轮迭代，每轮从未排序部分找到一个极值并将其放到正确位置。 适用场景：
- 数据规模较小。
- 当交换元素的成本很高，而比较元素的成本较低时，选择排序可能是一个考虑选项（因为它交换次数固定且最少，为 $n-1$ 次）。
5. 泛化与对比：
选择排序的交换次数比冒泡排序和插入排序都要少（固定为 $n-1$ 次），但比较次数是固定的 $O(n^2)$。它不如冒泡排序直观，也不如插入排序在接近有序时表现好。
3. 插入排序 (Insertion Sort) - 逐步构建有序序列 #
1. 理解题目与目的：
插入排序的目的是构建一个有序的序列，通过从未排序的元素中逐个取出元素，然后将其“插入”到已排序序列的正确位置中。
核心思想：手里拿着一副扑克牌，已经排好序的部分是左手拿着的牌，右手每次摸一张新牌，然后将其插入左手牌中正确的位置。
2. 思路与实现：
思路：
- 将序列的第一个元素视为已排序的序列。
- 从第二个元素开始，取出该元素（称为当前元素）。
- 在已排序的序列中从后向前查找当前元素的合适插入位置。
- 在查找过程中，如果已排序序列中的元素比当前元素大，则将其向后移动一个位置，为当前元素腾出空间。
- 找到合适位置后，将当前元素插入。
- 重复步骤 2-5，直到所有元素都已插入到已排序序列中。
Go 语言实现：
package main
import "fmt"
// InsertionSort 插入排序实现
func InsertionSort(arr []int) []int {
n := len(arr)
// 外层循环控制待插入的元素
for i := 1; i < n; i++ {
// 当前待插入的元素
currentElement := arr[i]
// 已排序部分的最后一个元素的索引
j := i - 1
// 在已排序部分从后向前查找插入位置
// 如果已排序部分的元素比待插入元素大，则向后移动
for j >= 0 && arr[j] > currentElement {
arr[j+1] = arr[j]
j--
}
// 找到合适位置，插入当前元素
arr[j+1] = currentElement
}
return arr
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
sortedArr := InsertionSort(arr)
fmt.Println("插入排序后:", sortedArr)
arrPartiallySorted := []int{1, 2, 5, 7, 3, 4, 6}
fmt.Println("部分有序数组:", arrPartiallySorted)
sortedArrPartially := InsertionSort(arrPartiallySorted)
fmt.Println("插入排序后:", sortedArrPartially) // 对接近有序的数组效率高
}
3. 复杂度分析与特点：
- 时间复杂度：
- 最好情况 (已排序): $O(n)$ (每轮只需要比较一次就找到位置)
- 最坏情况 (逆序): $O(n^2)$ (每轮都需要将当前元素插入到最前面，移动次数最多)
- 平均情况: $O(n^2)$
- 空间复杂度： $O(1)$ (只需要常数额外的空间存储当前待插入元素)
- 稳定性： 稳定 (插入过程中只有在找到第一个小于或等于待插入元素的位置时停止，相等元素的相对顺序不会改变)
- 原地排序： 是
4. 解题模式与适用场景：
模式：逐步构建一个有序的子序列，通过将未排序元素插入到已排序子序列的正确位置。 适用场景：
- 数据规模较小。
- 数据接近有序。
- 作为其他高级排序算法（如快速排序）的子过程，用于处理小规模子问题。
5. 泛化与对比：
插入排序在最好情况下比冒泡排序和选择排序快，因为它对已排序或接近有序的数组表现优秀。它是实际应用中对于小规模数据或作为混合排序算法的一部分时常用的 $O(n^2)$ 算法。
到这里，我们讲解了三种简单的、时间复杂度为 $O(n^2)$ 的排序算法：冒泡排序、选择排序和插入排序。它们概念简单，易于实现，但效率较低。
接下来，我们将进入更高效的排序算法，它们通常采用“分而治之”等策略，时间复杂度可以达到 $O(n \log n)$。
4. 归并排序 (Merge Sort) - 稳定的分治排序 #
1. 理解题目与目的：
归并排序是一种基于分治思想的排序算法。它的目的是将一个大问题（排序整个序列）分解成小问题（排序子序列），然后将小问题的解合并（归并）起来得到最终的解。
核心思想：“分而治之” + “合并”。
2. 思路与实现：
思路：
- 分解 (Divide): 不断将当前序列从中间一分为二，直到每个子序列只有一个元素（单个元素自然是有序的）。
- 解决 (Conquer): 对每个子序列进行递归排序。当子序列只有一个元素时，递归停止。
- 合并 (Combine): 将两个已经排序的子序列合并成一个更大的有序序列。这是归并排序的关键步骤。合并操作需要额外的空间。
合并 (Merge) 两个有序子序列 left 和 right 的思路：
- 创建一个新的临时数组
result。 - 使用两个指针，分别指向
left和right的开头。 - 比较两个指针指向的元素，将较小的那个放入
result，并移动相应指针。 - 重复此过程，直到其中一个子序列的所有元素都被放入
result。 - 将另一个子序列中剩余的元素全部复制到
result的末尾。 - 将
result中的元素复制回原始序列对应的位置。
Go 语言实现：
package main
import "fmt"
// MergeSort 归并排序主函数
func MergeSort(arr []int) []int {
n := len(arr)
if n <= 1 {
return arr // 递归终止条件：一个元素的数组已经有序
}
// 分解：找到中间点
mid := n / 2
// 递归排序左右两部分
left := MergeSort(arr[:mid])
right := MergeSort(arr[mid:])
// 合并：将排序好的左右两部分合并
return merge(left, right)
}
// merge 合并两个有序数组
func merge(left, right []int) []int {
result := make([]int, 0, len(left)+len(right)) // 预分配容量
i, j := 0, 0 // left 和 right 的指针
// 比较并合并
for i < len(left) && j < len(right) {
if left[i] <= right[j] { // 注意使用 <= 保证稳定性
result = append(result, left[i])
i++
} else {
result = append(result, right[j])
j++
}
}
// 将剩余元素添加到结果中
result = append(result, left[i:]...)
result = append(result, right[j:]...)
return result
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
sortedArr := MergeSort(arr)
fmt.Println("归并排序后:", sortedArr)
}
3. 复杂度分析与特点：
- 时间复杂度：
- 最好/最坏/平均情况: $O(n \log n)$ (分解过程产生 $\log n$ 层递归，每层递归（包括合并）的总操作次数是 $O(n)$)
- 空间复杂度： $O(n)$ (合并操作需要一个额外的临时数组)
- 稳定性： 稳定 (合并时，当左右两边元素相等时，优先取左边的元素，保证了相对顺序)
- 原地排序： 否 (需要额外空间)
4. 解题模式与适用场景：
模式：经典的分治算法，$T(n) = 2T(n/2) + O(n)$。 适用场景：
- 对时间复杂度要求较高，且可以接受额外的空间开销。
- 需要稳定排序的场景。
- 适用于对链表进行排序（链表的合并非常高效）。
5. 泛化与对比：
归并排序是少数几种能够保证 $O(n \log n)$ 最坏时间复杂度的比较排序算法之一。它的主要缺点是需要额外的空间。与快速排序相比，归并排序的性能更稳定，但通常实际运行时快速排序更快（尽管快排最坏情况是 $O(n^2)$）。
5. 快速排序 (Quick Sort) - 最常用的不稳定分治排序 #
1. 理解题目与目的：
快速排序也是一种基于分治思想的排序算法，通常是实际应用中表现最好的比较排序算法。它的目的是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分记录进行递归排序，以达到整个序列有序。
核心思想：“分而治之” + “分区 (Partition)”。
2. 思路与实现：
思路：
- 选择枢轴 (Pick Pivot): 从序列中选择一个元素作为“枢轴”（pivot）。选择枢轴的方法有很多（第一个元素、最后一个元素、中间元素、随机元素等）。
- 分区 (Partition): 重新排列序列，使得所有比枢轴值小的元素都放在枢轴的前面，所有比枢轴值大的元素都放在枢轴的后面（相等元素可以放在任意一边）。这个过程称为分区。分区结束后，枢轴就处于其最终的有序位置。
- 递归 (Recursion): 递归地对枢轴前和枢轴后的两个子序列进行快速排序。
Go 语言实现（使用经典的 Lomuto 分区方案，以最后一个元素为枢轴）：
package main
import "fmt"
// QuickSort 快速排序主函数
func QuickSort(arr []int, low, high int) {
if low < high {
// partitionIndex 是分区后枢轴的最终位置
partitionIndex := partition(arr, low, high)
// 递归排序枢轴前和枢轴后的子数组
QuickSort(arr, low, partitionIndex-1)
QuickSort(arr, partitionIndex+1, high)
}
}
// partition 分区函数
// 以最后一个元素 arr[high] 作为枢轴
// 将小于枢轴的元素放到枢轴前面，大于枢轴的元素放到枢轴后面
// 返回枢轴最终的索引
func partition(arr []int, low, high int) int {
pivot := arr[high] // 选择最后一个元素作为枢轴
i := low - 1 // i 指向小于枢轴的区域的末尾
for j := low; j < high; j++ {
// 如果当前元素小于或等于枢轴
if arr[j] <= pivot {
i++ // 移动 i
// 交换 arr[i] 和 arr[j]
arr[i], arr[j] = arr[j], arr[i]
}
}
// 将枢轴放到正确的位置 (i+1)
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1 // 返回枢轴的索引
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
QuickSort(arr, 0, len(arr)-1)
fmt.Println("快速排序后:", arr)
}
3. 复杂度分析与特点：
- 时间复杂度：
- 最好情况 (每次都能均匀分区): $O(n \log n)$ ($T(n) = 2T(n/2) + O(n)$)
- 最坏情况 (枢轴选择不当，导致分区极度不平衡，如已排序或逆序数组选择第一个/最后一个元素作为枢轴): $O(n^2)$ ($T(n) = T(n-1) + O(n)$)
- 平均情况: $O(n \log n)$
- 空间复杂度： $O(\log n)$ (取决于递归栈的深度，最好/平均情况下为 $O(\log n)$，最坏情况下为 $O(n)$)
- 稳定性： 不稳定 (分区过程中可能改变相等元素的相对顺序，例如，序列 5 8 5 2，如果枢轴选 2，第一次交换可能将后面的 5 换到前面)
- 原地排序： 是 (大部分实现是原地排序，只需要常数或对数级别的栈空间)
4. 解题模式与适用场景：
模式：经典的分治算法，$T(n) = T(k) + T(n-k-1) + O(n)$，其中 $k$ 是分区后第一个子数组的大小。 适用场景：
- 对时间复杂度要求较高，且可以接受不稳定性。
- 实际应用中最常用的通用排序算法之一，因为它在平均情况下的性能优秀且是原地排序。
5. 泛化与对比：
快速排序通常比归并排序更快，但最坏情况时间复杂度是 $O(n^2)$。通过随机选择枢轴或使用三数取中等方法可以降低遇到最坏情况的概率。快速排序的变体包括三路快排（用于处理大量重复元素）。Go 语言标准库中的排序算法 sort.Ints 等就是基于快速排序（具体是内省排序，结合了快速排序、堆排序和插入排序）。
6. 堆排序 (Heap Sort) - 利用堆结构的原地排序 #
1. 理解题目与目的：
堆排序是利用堆（一种特殊的树形数据结构）来实现的一种排序算法。它的目的是通过构建和操作堆来完成排序。
核心思想：堆的性质（最大堆：父节点总是大于等于其子节点；最小堆：父节点总是小于等于其子节点）使得我们可以快速找到序列中的最大或最小元素。
2. 思路与实现：
思路：
- 构建堆: 将待排序序列构建成一个最大堆（如果要升序排序）。构建过程从最后一个非叶子节点开始，对其进行“堆化”（Heapify，也叫下沉，确保以该节点为根的子树满足堆的性质）。
- 排序: 将堆顶元素（最大值）与堆的最后一个元素交换。然后将堆的大小减一（相当于将最大元素从堆中“移除”，放到已排序区域）。对新的堆顶元素进行堆化，恢复堆的性质。重复此过程，直到堆的大小变为 1。
Go 语言实现（构建最大堆进行升序排序）：
package main
import "fmt"
// HeapSort 堆排序主函数
func HeapSort(arr []int) []int {
n := len(arr)
// 1. 构建最大堆
// 从最后一个非叶子节点开始，向上进行堆化
// 最后一个非叶子节点的索引是 n/2 - 1
for i := n/2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
// 2. 排序
// 从最后一个元素开始，逐个将堆顶元素放到正确位置
for i := n - 1; i > 0; i-- {
// 将堆顶元素 (当前最大值) 与当前堆的最后一个元素交换
arr[0], arr[i] = arr[i], arr[0]
// 对剩余的 n-1 个元素组成的堆进行堆化，参数 i 表示当前堆的大小
heapify(arr, i, 0)
}
return arr
}
// heapify 堆化函数
// 维护以 i 为根的子树是最大堆
// n 是当前堆的大小
func heapify(arr []int, n int, i int) {
largest := i // 假设根节点是最大的
left := 2*i + 1 // 左子节点索引
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 {
// 交换根节点和最大子节点
arr[i], arr[largest] = arr[largest], arr[i]
// 对被交换的子节点继续进行堆化
heapify(arr, n, largest)
}
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
sortedArr := HeapSort(arr)
fmt.Println("堆排序后:", sortedArr)
}
3. 复杂度分析与特点：
- 时间复杂度：
- 最好/最坏/平均情况: $O(n \log n)$ (构建堆需要 $O(n)$ 时间，每次堆化需要 $O(\log n)$ 时间，共进行 $n-1$ 次堆化)
- 空间复杂度： $O(1)$ (只需要常数额外的空间进行交换和递归调用栈，可以视为原地排序)
- 稳定性： 不稳定 (堆的性质不保证相等元素的相对顺序)
- 原地排序： 是
4. 解题模式与适用场景：
模式：利用堆的数据结构，通过构建堆和反复调整堆来排序。 适用场景：
- 对时间复杂度要求较高，且需要原地排序（空间效率要求高）。
- 求解 Top K 问题（可以使用最小堆或最大堆）。
5. 泛化与对比：
堆排序是少数几种能够保证 $O(n \log n)$ 最坏时间复杂度的原地排序算法。与快速排序相比，堆排序的最坏情况性能更好，但实际应用中通常比快速排序慢一些。与归并排序相比，堆排序是原地排序但不是稳定排序，而归并排序是稳定排序但需要额外空间。
线性时间排序算法 (O(n)) - 特殊情况 #
以上介绍的都是基于比较的排序算法，它们的最好时间复杂度理论上不能低于 $O(n \log n)$。然而，对于某些特殊类型的输入数据，我们可以使用非比较排序算法，达到线性时间 $O(n)$ 的复杂度。
这里简单介绍两种常见的线性时间排序算法：
7. 计数排序 (Counting Sort) - 适用于小范围非负整数 #
1. 理解题目与目的：
计数排序是一种非比较排序算法，适用于待排序元素是处于一个有限范围内的非负整数的情况。它的目的是通过统计每个元素出现的次数，然后根据次数将元素按顺序放回原序列。
核心思想：“统计” + “累加” + “回填”。
2. 思路与实现：
思路：
- 找到序列中的最大值和最小值，确定元素的范围。
- 创建一个计数数组
count，其大小为 (最大值 - 最小值 + 1)，用于存储范围内每个数字出现的次数。初始化为 0。 - 遍历原始序列，统计每个数字的出现次数，并更新
count数组。 - （可选，用于稳定排序）修改
count数组，使得count[i]存储小于或等于i的元素的个数。 - 创建一个输出数组
output，大小与原始序列相同。 - 从后向前遍历原始序列。对于每个元素
x，找到它在count数组中对应的位置，将其放入output的这个位置，然后将count[x]减一。从后向前遍历保证了稳定性。 - 将
output数组复制回原始序列。
Go 语言实现：
package main
import (
"fmt"
"math"
)
// CountingSort 计数排序实现 (适用于非负整数)
func CountingSort(arr []int) []int {
n := len(arr)
if n == 0 {
return arr
}
// 找到最大值和最小值
maxVal := arr[0]
minVal := arr[0]
for i := 1; i < n; i++ {
if arr[i] > maxVal {
maxVal = arr[i]
}
if arr[i] < minVal {
minVal = arr[i]
}
}
// 创建计数数组，大小为 (maxVal - minVal + 1)
countSize := maxVal - minVal + 1
count := make([]int, countSize)
// 统计每个元素的出现次数
for i := 0; i < n; i++ {
count[arr[i]-minVal]++
}
// (可选，用于稳定排序) 修改计数数组，使其存储小于等于当前元素的个数
for i := 1; i < countSize; i++ {
count[i] += count[i-1]
}
// 创建输出数组
output := make([]int, n)
// 从后向前遍历原始数组，将元素放到输出数组的正确位置
// 从后向前保证稳定性
for i := n - 1; i >= 0; i-- {
// arr[i] - minVal 是元素 arr[i] 在计数数组中的索引
// count[arr[i]-minVal] - 1 是元素 arr[i] 在输出数组中的最终位置索引
output[count[arr[i]-minVal]-1] = arr[i]
count[arr[i]-minVal]--
}
// 将输出数组复制回原始数组
copy(arr, output)
return arr
}
func main() {
arr := []int{4, 2, 2, 8, 3, 3, 1}
fmt.Println("原始数组:", arr)
sortedArr := CountingSort(arr)
fmt.Println("计数排序后:", sortedArr)
arrWithRange := []int{10, 7, 13, 15, 12}
fmt.Println("原始数组:", arrWithRange)
sortedArrRange := CountingSort(arrWithRange)
fmt.Println("计数排序后:", sortedArrRange)
}
3. 复杂度分析与特点：
- 时间复杂度： $O(n + k)$，其中 $n$ 是元素个数，$k$ 是元素的取值范围 (maxVal - minVal + 1)。当 $k$ 接近于 $n$ 或小于 $n$ 时，时间复杂度接近于 $O(n)$。
- 空间复杂度： $O(k)$ (需要一个大小为 $k$ 的计数数组)
- 稳定性： 稳定 (通过从后向前遍历和累加计数数组实现)
- 原地排序： 否 (需要额外的计数数组和输出数组)
4. 解题模式与适用场景：
模式：利用元素的取值范围，通过统计频次来确定元素位置。 适用场景：
- 待排序元素是非负整数。
- 元素的取值范围不是很大，否则计数数组会非常大，导致空间开销过高。
5. 泛化与对比：
计数排序是基数排序的基础。它突破了比较排序的 $O(n \log n)$ 下界，但牺牲了通用性，只能处理特定类型和范围的数据。
8. 基数排序 (Radix Sort) - 适用于按位排序 #
1. 理解题目与目的：
基数排序是一种非比较排序算法，它通过按数字的每一位（例如，个位、十位、百位…）进行排序来完成。它可以处理整数，也可以扩展到字符串等其他类型的数据。
核心思想：“按位” + “稳定排序”。通常会配合计数排序或桶排序来按位进行稳定排序。
2. 思路与实现：
思路（以 LSD - Least Significant Digit - 最低有效位优先为例）：
- 找到序列中的最大值，以确定需要排序的位数。
- 从最低有效位（个位）开始，对序列进行一次稳定排序。可以使用计数排序来完成这个按位的稳定排序。
- 对下一位（十位）重复步骤 2。
- 重复此过程，直到对最高有效位也进行了稳定排序。
Go 语言实现（使用计数排序作为内部的稳定排序）：
package main
import (
"fmt"
"math"
)
// RadixSort 基数排序主函数 (LSD，适用于非负整数)
func RadixSort(arr []int) []int {
n := len(arr)
if n == 0 {
return arr
}
// 找到最大值以确定位数
maxVal := arr[0]
for i := 1; i < n; i++ {
if arr[i] > maxVal {
maxVal = arr[i]
}
}
// 对每一位进行计数排序
// exp 从 1 开始，表示个位 (10^0)
// exp 变为 10，表示十位 (10^1)
// exp 变为 100，表示百位 (10^2)，依此类推
for exp := 1; maxVal/exp > 0; exp *= 10 {
countSortByDigit(arr, n, exp)
}
return arr
}
// countSortByDigit 对指定位数的数字进行计数排序 (稳定排序)
func countSortByDigit(arr []int, n int, exp int) {
output := make([]int, n) // 输出数组
count := make([]int, 10) // 计数数组 (0-9)
// 统计当前位上每个数字的出现次数
for i := 0; i < n; i++ {
digit := (arr[i] / exp) % 10 // 获取当前位上的数字
count[digit]++
}
// 修改计数数组，使其存储小于等于当前数字的个数
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
// 从后向前遍历原始数组，将元素放到输出数组的正确位置
// 根据当前位上的数字和计数数组的值确定位置
for i := n - 1; i >= 0; i-- {
digit := (arr[i] / exp) % 10
output[count[digit]-1] = arr[i]
count[digit]--
}
// 将输出数组复制回原始数组
copy(arr, output)
}
func main() {
arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
fmt.Println("原始数组:", arr)
sortedArr := RadixSort(arr)
fmt.Println("基数排序后:", sortedArr)
}
3. 复杂度分析与特点：
- 时间复杂度： $O(d * (n + k))$，其中 $d$ 是数字的最大位数，$n$ 是元素个数，$k$ 是基数（例如，十进制是 10）。如果 $k$ 是常数，时间复杂度为 $O(d * n)$。对于整数，位数 $d$ 通常与 $\log_k(maxVal)$ 相关，所以时间复杂度通常可以认为是 $O(n \log_k(maxVal))$，在某些情况下可以接近 $O(n)$。
- 空间复杂度： $O(n + k)$ (取决于内部稳定排序所需的空间，计数排序需要 $O(n+k)$)
- 稳定性： 稳定 (取决于内部使用的稳定排序算法，如计数排序)
- 原地排序： 否 (需要额外的输出数组和计数数组)
4. 解题模式与适用场景：
模式：多次对序列进行稳定排序，每次排序都关注元素的不同“位”。 适用场景：
- 待排序元素可以按位分解（如整数、字符串）。
- 元素的取值范围或位数不是非常大。
5. 泛化与对比：
基数排序通过避免比较，在特定情况下可以比比较排序更快。它的主要缺点是需要额外的空间，并且对数据类型有要求。LSD 和 MSD（Most Significant Digit - 最高有效位优先）是两种常见的基数排序策略。
总结与对比 #
| 算法 | 时间复杂度 (平均) | 时间复杂度 (最坏) | 空间复杂度 | 稳定性 | 原地排序 | 适用场景 | 备注 |
|---|---|---|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 | 是 | 小规模数据，教学 | 最简单直观，但效率低 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 | 是 | 小规模数据，交换成本高 | 交换次数最少 |
| 插入排序 | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 | 是 | 小规模数据，接近有序数据 | 对接近有序数据效率高 |
| 归并排序 | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | 稳定 | 否 | 需要稳定排序，可以接受额外空间，链表排序 | 时间性能稳定 |
| 快速排序 | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ | 不稳定 | 是 | 大多数通用场景 | 实际应用中常最快，但最坏情况较差 |
| 堆排序 | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | 不稳定 | 是 | 需要原地排序，Top K 问题 | 最坏情况性能稳定的原地排序算法 |
| 计数排序 | $O(n+k)$ | $O(n+k)$ | $O(k)$ | 稳定 | 否 | 小范围非负整数 | 线性时间，非比较 |
| 基数排序 | $O(dn)$ | $O(dn)$ | $O(n+k)$ | 稳定 | 否 | 可以按位分解的数据（整数、字符串等） | 线性时间，非比较，依赖内部稳定排序 |
Go 语言中的排序：
Go 语言的标准库 sort 包提供了通用的排序接口和常用的排序算法实现。sort.Ints、sort.Float64s、sort.Strings 等函数使用的是一种称为内省排序 (Introsort) 的混合排序算法。内省排序是结合了快速排序、堆排序和插入排序的策略：
- 主算法是快速排序，因为它在平均情况下表现最优。
- 当递归深度超过一定阈值时，切换到堆排序，以避免快速排序在最坏情况下的 $O(n^2)$ 性能。
- 对于小规模的子数组，切换到插入排序，因为插入排序在这种情况下性能更好，且常数因子小。
这种混合策略使得 Go 语言标准库的排序既有快速排序的平均高性能，又能保证 $O(n \log n)$ 的最坏时间复杂度。
泛化类似问题： #
学习排序算法不仅仅是为了记住这些算法本身，更重要的是理解它们背后的思想和模式。这些思想可以应用于解决很多其他问题：
- 查找问题： 排序是很多高效查找算法（如二分查找）的前提。
- Top K 问题： 快速选择（QuickSelect，基于快速排序的分区思想）和堆（堆排序的一部分）是解决 Top K 问题的常用方法。
- 计数和统计： 计数排序的思想可以用于统计元素频率或在特定范围内进行高效计数。
- 桶和分治： 归并排序和快速排序的分治思想，以及计数排序和基数排序的桶/分桶思想，是解决大规模数据处理和并行计算中常见策略。
- 数据结构的设计： 堆排序引出了堆这种重要的数据结构，它在优先队列等场景中广泛应用。
掌握这些排序算法，你就掌握了处理数据序列的基本功，能够更好地理解和设计更复杂的算法。
希望这个详细的讲解能帮助你理解排序算法！如果你想进一步深入某个算法的细节，或者有其他算法问题，随时都可以问我！