排序基础：排序的基本概念与分类

排序，说白了就是把一堆乱序的数据整理成有序序列。我刚开始学数据结构时，觉得排序不就是排个序嘛，有啥好讲的？直到后来在项目中处理百万级数据时，才发现选错排序算法，程序能慢到让你怀疑人生。

排序的核心价值在于：有序数据能大幅提升后续操作的效率。比如二分查找，前提就是数据必须有序。你想想看，如果数据是乱序的，查找只能一个个遍历，那效率得多低？

排序的基本概念

排序的定义其实很简单：给定一个记录序列，按照某个关键字的大小，重新排列成递增或递减的序列。

这里有几个关键术语，我建议你记牢：

  • 排序码：作为排序依据的数据项，可以是主关键字或次关键字
  • 稳定性：如果两个相等的元素在排序前后相对位置不变，这个排序就是稳定的
  • 内排序与外排序：内排序在内存中完成，外排序涉及磁盘等外部存储

稳定性为什么重要？

我在做电商订单系统时，需要先按时间排序，再按金额排序。如果排序不稳定，第二次排序会打乱第一次的结果，导致数据错乱。嗯，这里要注意，稳定排序在某些场景下是刚需。

排序的分类

排序算法五花八门，但大体上可以分成几类。我习惯按实现思路来划分：

分类 典型算法 特点
插入排序 直接插入、折半插入、希尔 逐步构建有序序列
交换排序 冒泡、快速 通过交换消除逆序
选择排序 简单选择、堆排序 每次选最小/最大
归并排序 二路归并 分治合并
基数排序 基数排序 按位分配收集

今天我们先啃插入排序这块硬骨头。为什么先讲它？因为插入排序的思想最直观，而且在实际开发中，小规模数据用插入排序往往比快排还快。

排序知识体系 排序算法 插入排序 交换排序 选择排序 直接插入 折半插入 希尔排序 本章重点：插入排序家族

直接插入排序

直接插入排序的思路，跟你打扑克牌时理牌一模一样。你摸到一张新牌，会把它插到手中已经排好序的牌堆里合适的位置。对吧？

算法步骤很简单：

  1. 把第一个元素视为已排序序列
  2. 取出下一个元素，在已排序序列中从后往前扫描
  3. 如果已排序元素大于新元素，就往后移一位
  4. 找到合适位置后插入新元素
  5. 重复直到所有元素处理完毕
// 直接插入排序 - C语言实现
void insertSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];      // 摸到的新牌
        j = i - 1;
        
        // 从后往前找插入位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // 往后挪
            j--;
        }
        arr[j + 1] = key;  // 插入
    }
}

我的经验之谈：直接插入排序在数据基本有序时效率极高，时间复杂度接近 O(n)。我在做日志时间戳排序时，数据本身就是按时间顺序生成的，只有少量乱序，用插入排序比快排还快。

时间复杂度分析：

  • 最好情况（已有序）：O(n)，只需比较 n-1 次
  • 最坏情况（逆序）：O(n²)，比较和移动次数都是 n(n-1)/2
  • 平均情况：O(n²)
  • 空间复杂度：O(1)，原地排序

稳定性：稳定。因为相等元素不会交换位置，相对顺序保持不变。

折半插入排序

直接插入排序有个明显的缺点：查找插入位置时是顺序查找，效率低。你想想看，既然前面已经是有序序列了，为什么不用二分查找呢？

折半插入排序就是干这个的——用二分查找替代顺序查找，减少比较次数。

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

注意：折半插入排序只是减少了比较次数（从 O(n) 降到 O(log n)），但移动次数仍然是 O(n²)。所以整体时间复杂度还是 O(n²)，只是常数因子变小了。

我曾经在嵌入式项目中用过这个算法。当时 CPU 资源紧张，比较操作比移动操作更耗资源，折半插入排序正好派上用场。虽然整体复杂度没变，但实际运行时间减少了约 30%。

希尔排序

希尔排序是插入排序的升级版。它的核心思想是：先让数据局部有序，再逐步全局有序。

具体做法是：

  1. 选择一个增量序列（比如 n/2, n/4, ..., 1）
  2. 按增量分组，对每组进行直接插入排序
  3. 缩小增量，重复上述过程
  4. 当增量为 1 时，就是一次完整的直接插入排序
// 希尔排序 - C语言实现
void shellSort(int arr[], int n) {
    int gap, i, j, key;
    
    // 增量从 n/2 开始，每次减半
    for (gap = n / 2; gap > 0; gap /= 2) {
        // 对每个分组进行插入排序
        for (i = gap; i < n; i++) {
            key = arr[i];
            j = i - gap;
            
            while (j >= 0 && arr[j] > key) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = key;
        }
    }
}

避坑指南：希尔排序的增量选择很关键。我最初用 n/2 的增量序列，效果还行。但后来发现用 Hibbard 增量（2^k - 1）或 Sedgewick 增量，性能能提升不少。千万别用固定的增量序列，要根据数据规模调整。

希尔排序的时间复杂度分析比较复杂：

  • 最坏情况：O(n²)（使用 n/2 增量时）
  • 最好情况：O(n log n)
  • 平均情况：约 O(n^1.3) 到 O(n^1.5)
  • 空间复杂度：O(1)

稳定性：不稳定。因为分组排序时，相等元素可能被分到不同组，导致相对顺序改变。

三种插入排序对比

算法 平均时间复杂度 空间复杂度 稳定性 适用场景
直接插入 O(n²) O(1) 稳定 小规模数据、基本有序
折半插入 O(n²) O(1) 稳定 比较操作代价高时
希尔排序 O(n^1.3~1.5) O(1) 不稳定 中等规模数据

我个人习惯这样选：数据量小于 100 用直接插入，数据量在 100 到 10000 之间用希尔排序，再大的数据就要考虑快速排序或归并排序了。当然，这只是一个经验值，具体还要看数据特征。

小技巧：希尔排序的代码其实很好记。你只需要记住三层循环：最外层是增量变化，中间层是分组遍历，最内层是插入排序。每次写代码时，先写最内层的插入排序，再套上外层循环，就不容易出错。

好了，插入排序就讲到这里。这三种排序算法虽然简单，但它们是理解更复杂排序算法的基础。特别是希尔排序，它打破了 O(n²) 的魔咒，为后来的快速排序、堆排序等高级算法铺平了道路。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →