为什么排序是算法第一课

不管你以后做什么方向——竞赛、后端、数据、AI——排序都是绕不开的基本功。排序是"把一串乱序数字变成有序"这个问题的标准化解法，每种排序背后都是一种算法思想。

学排序不是为了手写排序（竞赛里直接调 sort()），而是通过排序学会怎么分析一个算法的快慢、怎么用分治、怎么权衡时间和空间。

会写 sort() 不算本事，能讲清为什么 sort() 这么快才是本事。
本文核心知识点
  • 冒泡/选择/插入O(n²) 入门三件套。
  • 快排/归并O(n log n) 进阶。
  • 时间复杂度算法快慢的尺子。
  • 分治大问题拆小。
C++ 排序算法配图：蓝色渐变背景上一排彩色柱状图从矮到高，旁边双向箭头比较高低，小放大镜在看柱子，一个漏斗把散乱彩色小球倒进去后排成整齐队列
从乱序到有序：排序的本质就是把柱子排齐。

冒泡排序：最直白的交换

冒泡排序的思想：从左到右两两比较，前面比后面大就交换。一轮下来，最大的数像气泡一样"冒"到最后。

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

两轮循环嵌套，每轮比较 n 次，总共约 n²/2 次。这就是 O(n²)。

选择排序与插入排序

选择排序：每轮选最小的放到前面。n 轮，每轮扫一遍找最小，也是 O(n²)。

插入排序：像打扑克理牌——拿到新牌，从右往左找到它该插的位置。数据近乎有序时很快，最坏也是 O(n²)。

这三个 O(n²) 排序写法简单，但数据量一大就慢——10 万元素要算几亿次。

时间复杂度：O(n²) 和 O(n log n)

n=100000 时：

  • O(n²) = 100 亿次操作，要几秒到几分钟。
  • O(n log n) ≈ 100000 × 17 ≈ 170 万次，一瞬间。

差距是一万倍。这就是为什么竞赛里必须用 O(n log n) 的排序。

快速排序：分治的力量

快排的思想：选一个基准数 pivot，把比它小的放左边、比它大的放右边，再对左右两半递归快排。

void quickSort(int a[], int l, int r) {
  if (l >= r) return;
  int i = l, j = r, pivot = a[l];
  while (i < j) {
    while (i < j && a[j] >= pivot) j--;
    a[i] = a[j];
    while (i < j && a[i] <= pivot) i++;
    a[j] = a[i];
  }
  a[i] = pivot;
  quickSort(a, l, i - 1);
  quickSort(a, i + 1, r);
}

每次分成两半，递归深度 log n，每层总共扫 n 次，所以平均 O(n log n)。