排序算法百科全书：从基础到精进的完整指南

排序算法是算法的“基石”——你可以在不了解其他算法的情况下写出程序，但没有排序算法，你连二分查找都跑不起来。理解排序算法，就是理解整个算法思维的开端。

一、排序算法基础：重新认识“排序”

1.1 什么是排序算法？

排序算法的核心目标很简单：将一组数据按照特定顺序（通常是升序或降序）重新排列。但“简单”的目标下，隐藏着计算机科学中最丰富、最深刻的问题域。

从1945年冯·诺依曼提出归并排序至今，排序算法已经演变为一个庞大的算法家族——每种算法都代表了不同的计算机科学思想：

• 插入排序代表“增量构建”

• 归并排序代表“分治策略”

• 堆排序代表“优先队列抽象”

• 快速排序代表“随机化与概率”

• 基数排序代表“非比较排序”

核心指标：排序算法的优劣通常用三个维度衡量——时间复杂度、空间复杂度和稳定性。

1.2 稳定性：一个容易被忽视的关键特性

稳定排序指：如果两个元素相等，排序后它们的相对顺序保持不变。稳定性的价值在于——当你要对复杂对象按多个字段排序时，逐次稳定排序可以叠加排序结果。

1.3 算法分类总览

二、经典排序算法深度解析

2.1 冒泡排序：最直观的排序

思想：重复遍历数列，每次比较相邻元素，将较大的“冒泡”到末尾。

c

void bubble_sort(int arr[], int n) { for (int i = 0; i < n-1; i++) { int swapped = 0; for (int j = 0; j < n-1-i; j++) { if (arr[j] > arr[j+1]) { swap(&arr[j], &arr[j+1]); swapped = 1; } } if (!swapped) break; // 提前终止优化 } }

复杂度：O(n²)时间，O(1)空间，稳定。

特点：简单易实现，小规模数据可用。优化后，当数据已基本有序时，时间复杂度可降至O(n)。

2.2 插入排序：打扑克牌的思维方式

思想：将元素逐一插入到已经排序好的序列中的正确位置。

c

void insertion_sort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j--; }