排序是数据处理领域的核心操作，广泛应用于日常开发与生活场景。无论是电商平台的商品排序、报表数据的整理，还是系统后台的日志分析，都离不开高效的排序算法。本文将系统梳理排序的基础概念，拆解常见排序算法的实现逻辑与特性，并附上完整代码，帮助你全面掌握排序技术。

一、排序的核心基础概念

在学习具体算法前，需先明确几个关键概念，它们是判断排序算法适用性的重要依据。

1. 排序的定义

排序是指将一串记录，按照其中某个或某些关键字的大小，以递增或递减的顺序排列起来的操作。这里的 “记录” 可以是数字、商品信息、学生成绩等，“关键字” 则是排序的依据，如数字大小、商品价格、成绩高低等。

2. 稳定性

稳定性是排序算法的重要特性：假定待排序序列中存在多个关键字相同的记录，若排序后这些记录的相对次序保持不变（即原序列中r[i]=r[j]且r[i]在r[j]之前，排序后r[i]仍在r[j]之前），则该算法是稳定的；反之则为不稳定。稳定性在多关键字排序场景中至关重要，例如 “先按商品价格排序，再按上架时间排序”，若价格排序不稳定，相同价格商品的上架时间顺序会被打乱。

3. 内部排序与外部排序

• 内部排序：所有数据元素都能存放在内存中，排序过程无需依赖外部存储（如数组排序），是日常开发中最常用的排序类型。
• 外部排序：数据元素数量过大，无法同时存入内存，需在排序过程中频繁在内存与外部存储（如磁盘）之间移动数据（如 100GB 日志文件的排序）。

二、常见排序算法分类与实现

内部排序算法可分为插入排序、选择排序、交换排序、归并排序和非比较排序五大类，各类算法的思路与性能差异显著，以下逐一拆解。

1. 插入排序：逐步插入构建有序序列

插入排序的核心思想是 “将待排序元素逐个插入已有的有序序列中”，就像玩扑克牌时将新摸到的牌插入手中的有序牌堆，主要包括直接插入排序和希尔排序。

（1）直接插入排序

基本逻辑：当插入第i个元素时，前面的array[0]~array[i-1]已形成有序序列，此时用array[i]的关键字从后往前与有序序列中的元素比较，找到合适的插入位置后，将该位置及后续元素后移，再将array[i]插入。

代码实现：

// 直接插入排序
void InsertSort(int* a, int n)
{
    // 从第2个元素（下标1）开始，第1个元素（下标0）默认有序
    for (int i = 1; i < n; i++)
    {
        int tmp = a[i]; // 保存待插入元素，避免后续移动覆盖
        int j = i - 1;  // 指向有序序列的最后一个元素
        // 从后往前找插入位置，比tmp大的元素依次后移
        while (j >= 0 && a[j] > tmp)
        {
            a[j + 1] = a[j];
            j--;
        }
        // 插入待排序元素到正确位置
        a[j + 1] = tmp;
    }
}

特性：

• 时间复杂度：元素越接近有序，效率越高，最好情况O(n)（已排序数组），平均与最坏情况均为O(n²)；
• 空间复杂度：O(1)，仅需临时变量存储待插入元素，属于原地排序；
• 稳定性：稳定，相同元素不会因插入操作改变相对次序。

（2）希尔排序（缩小增量排序）

基本逻辑：希尔排序是对直接插入排序的优化，通过 “分组排序” 让数组逐步接近有序，最终用直接插入排序完成收尾。具体步骤为：先选定一个增量gap，将数组按gap分成多组（每组元素下标差为gap），对每组内元素做直接插入排序；逐步缩小gap（如gap = gap/3 + 1），重复分组与排序；直到gap=1，此时数组已接近有序，执行最后一次直接插入排序。

代码实现：

// 希尔排序
void ShellSort(int* a, int n)
{
    // 增量按Knuth方案取值：gap = gap/3 + 1，确保最终gap=1
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        // 对每组内元素执行直接插入排序
        for (int i = gap; i < n; i++)
        {
            int tmp = a[i];
            int j = i - gap;
            while (j >= 0 && a[j] > tmp)
            {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = tmp;
        }
    }
}

特性：

• 时间复杂度：无固定值，取决于增量gap的选择，按 Knuth 增量方案，效率约为O(n^1.25)~O(1.6n^1.25)；
• 空间复杂度：O(1)，原地排序；
• 稳定性：不稳定，分组排序过程中可能打乱相同元素的相对次序。

2. 选择排序：筛选最值构建有序序列

选择排序的核心思想是 “每次从待排序元素中筛选出最小（或最大）元素，放入已排序序列的末尾”，主要包括直接选择排序和堆排序。

（1）直接选择排序

基本逻辑：从待排序区间中找到最小元素，与区间起始位置的元素交换；再从剩余待排序区间中找到最小元素，与区间第二个位置的元素交换；重复此过程，直到所有元素排序完成。

代码实现：

// 直接选择排序（每次选最小元素放入有序区间）
void SelectSort(int* a, int n)
{
    // 只需处理前n-1个元素，最后一个元素默认有序
    for (int i = 0; i < n - 1; i++)
    {
        int minIdx = i; // 记录最小元素的下标
        // 遍历待排序区间[i, n-1]，找到最小元素
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < a[minIdx])
            {
                minIdx = j;
            }
        }
        // 若最小元素不在起始位置，交换元素
        if (minIdx != i)
        {
            int tmp = a[i];
            a[i] = a[minIdx];
            a[minIdx] = tmp;
        }
    }
}

特性：

• 时间复杂度：无论数据是否有序，均需遍历筛选最值，时间复杂度恒为O(n²)；
• 空间复杂度：O(1)，原地排序；
• 稳定性：不稳定，例如序列[2, 2, 1]，第一次筛选后1与第一个2交换，两个2的相对次序被打乱。

（2）堆排序

基本逻辑：堆排序是选择排序的优化版本，利用 “堆”（完全二叉树）这种数据结构快速筛选最值。排升序时需构建 “大堆”（堆顶为最大元素），步骤为：先将数组构建成大堆；将堆顶（最大元素）与堆尾元素交换，此时最大元素固定在数组末尾；再将剩余元素重新调整为大堆，重复交换与调整操作，直到所有元素排序完成。

代码实现：

// 堆排序辅助函数：将以root为根的子树调整为大堆
void AdjustDwon(int* a, int n, int root)
{
    int parent = root;
    int child = 2 * parent + 1; // 左孩子下标（堆的性质：左孩子=2*父+1，右孩子=2*父+2）
    while (child < n)
    {
        // 选择左右孩子中较大的那个
        if (child + 1 < n && a[child + 1] > a[child])
        {
            child++;
        }
        // 若父节点小于孩子节点，交换并继续向下调整
        if (a[parent] < a[child])
        {
            int tmp = a[parent];
            a[parent] = a[child];
            a[child] = tmp;
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break; // 父节点大于孩子节点，堆已满足条件
        }
    }
}

// 堆排序（升序排序）
void HeapSort(int* a, int n)
{
    // 1. 构建大堆：从最后一个非叶子节点（下标(n-1-1)/2）向前调整
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDwon(a, n, i);
    }
    // 2. 交换堆顶与堆尾，调整剩余元素为大堆
    for (int i = n - 1; i > 0; i--)
    {
        // 交换堆顶（最大元素）与堆尾
        int tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;
        // 调整剩余i个元素为大堆（堆尾元素已固定，无需参与调整）
        AdjustDwon(a, i, 0);
    }
}

特性：

• 时间复杂度：构建堆的时间为O(n)，每次调整堆的时间为O(log n)，共需调整n-1次，整体时间复杂度O(n log n)；
• 空间复杂度：O(1)，原地排序；
• 稳定性：不稳定，交换堆顶与堆尾元素时可能打乱相同元素的相对次序。

3. 交换排序：通过交换调整元素次序

交换排序的核心思想是 “根据两个元素关键字的比较结果，交换它们在序列中的位置”，将关键字大的元素向序列尾部移动，关键字小的元素向序列前部移动，主要包括冒泡排序和快速排序。

（1）冒泡排序

基本逻辑：从左到右依次比较相邻元素，若顺序错误（前大后小）则交换，通过多轮比较，将最大元素逐步 “浮” 到序列末尾，就像气泡在水中上升。为优化效率，可添加 “交换标记”，若某轮未发生交换，说明数组已有序，可提前退出。

代码实现：

// 冒泡排序（含优化：无交换时提前退出）
void BubbleSort(int* a, int n)
{
    // 最多需要n-1轮比较，每轮确定一个最大元素的位置
    for (int i = 0; i < n - 1; i++)
    {
        int exchange = 0; // 标记本轮是否发生交换
        // 每轮比较范围：[0, n-1-i]（尾部i个元素已有序）
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                // 交换相邻元素
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                exchange = 1;
            }
        }
        if (exchange == 0)
        {
            break; // 无交换，数组已有序，提前结束
        }
    }
}

特性：

• 时间复杂度：最好情况O(n)（已排序数组，触发提前退出），平均与最坏情况O(n²)；
• 空间复杂度：O(1)，原地排序；
• 稳定性：稳定，仅交换相邻元素，相同元素不会改变相对次序。

（2）快速排序

快速排序是综合性能最优的排序算法之一，基于 “分治法” 思想，由 Hoare 于 1962 年提出，核心是 “按基准值划分数组，再递归排序子数组”。

① 核心步骤

1. 选择基准值：从数组中选一个元素作为基准值（如左边界元素）；
2. 划分区间：将数组划分为两部分，左区间元素均小于基准值，右区间元素均大于基准值，基准值位于最终排序位置；
3. 递归排序：对左、右区间分别重复步骤 1-2，直到区间长度为 1（默认有序）。

② 三种常见划分方式

• Hoare 版本（左右指针法）：

  // Hoare划分：基准值选左边界，左右指针向中间移动
  int PartSort1(int* a, int left, int right)
  {
      int keyIdx = left; // 基准值下标
      while (left < right)
      {
          // 右指针找比基准值小的元素（从右向左）
          while (left < right && a[right] >= a[keyIdx])
          {
              right--;
          }
          // 左指针找比基准值大的元素（从左向右）
          while (left < right && a[left] <= a[keyIdx])
          {
              left++;
          }
          // 交换找到的两个元素
          if (left < right)
          {
              int tmp = a[left];
              a[left] = a[right];
              a[right] = tmp;
          }
      }
      // 交换基准值与左右指针相遇位置的元素，确定基准值最终位置
      int tmp = a[keyIdx];
      a[keyIdx] = a[left];
      a[left] = tmp;
      return left; // 返回基准值下标，用于划分左右区间
  }

  挖坑法

• // 挖坑划分：先将基准值存为“坑”，填充后形成新坑，最终将基准值填入最后一个坑
  int PartSort2(int* a, int left, int right)
  {
      int key = a[left]; // 保存基准值，形成第一个“坑”
      while (left < right)
      {
          // 右指针找比基准值小的元素，填入左坑
          while (left < right && a[right] >= key)
          {
              right--;
          }
          a[left] = a[right]; // 右元素填入左坑，右指针处形成新坑
          // 左指针找比基准值大的元素，填入右坑
          while (left < right && a[left] <= key)
          {
              left++;
          }
          a[right] = a[left]; // 左元素填入右坑，左指针处形成新坑
      }
      a[left] = key; // 基准值填入最后一个坑
      return left;
  }

• 前后指针法：

// 前后指针划分：prev指向已处理区间末尾，cur遍历未处理区间，交换小元素到前方
int PartSort3(int* a, int left, int right)
{
    int keyIdx = left;
    int prev = left;   // 前指针：指向已处理区间的最后一个元素
    int cur = left + 1;// 后指针：遍历未处理区间
    while (cur <= right)
    {
        // 若cur找到比基准值小的元素，prev后移并交换（避免自身交换）
        if (a[cur] < a[keyIdx] && ++prev != cur)
        {
            int tmp = a[prev];
            a[prev] = a[cur];
            a[cur] = tmp;
        }
        cur++;
    }
    // 交换基准值与prev位置的元素，确定基准值最终位置
    int tmp = a[keyIdx];
    a[keyIdx] = a[prev];
    a[prev] = tmp;
    return prev;
}

③ 递归实现

// 快速排序递归实现
void QuickSort(int* a, int left, int right)
{
    if (left >= right)
    {
        return; // 区间长度≤1，无需排序
    }
    // 调用任意一种划分方式（以Hoare为例）
    int div = PartSort1(a, left, right);
    // 递归排序左区间[left, div-1]和右区间[div+1, right]
    QuickSort(a, left, div - 1);
    QuickSort(a, div + 1, right);
}

④ 非递归实现（栈模拟递归）

为避免递归深度过大导致栈溢出，可使用栈存储区间边界，模拟递归过程：

#include <stack.h> // 需包含栈的实现（初始化、入栈、出栈、判空、销毁）

// 快速排序非递归实现
void QuickSortNonR(int* a, int left, int right)
{
    Stack st;
    StackInit(&st);          // 初始化栈
    StackPush(&st, left);    // 左边界入栈
    StackPush(&st, right);   // 右边界入栈

    while (!StackEmpty(&st)) // 栈不为空则继续处理
    {
        // 栈先进后出，需先出右边界，再出左边界
        int r = StackTop(&st);
        StackPop(&st);
        int l = StackTop(&st);
        StackPop(&st);

        if (l >= r)
        {
            continue;
        }

        // 划分区间，得到基准值下标
        int div = PartSort1(a, l, r);
        // 右区间[div+1, r]的边界入栈
        StackPush(&st, div + 1);
        StackPush(&st, r);
        // 左区间[l, div-1]的边界入栈
        StackPush(&st, l);
        StackPush(&st, div - 1);
    }

    StackDestroy(&st); // 销毁栈，释放资源
}

⑤ 优化策略

1. 三数取中法：选择左、中、右三个位置元素的中位数作为基准值，避免数组有序时基准值选到最值（此时快速排序退化为O(n²)）；
2. 小区间用插入排序：当区间长度小于阈值（如 7）时，改用插入排序，减少递归开销（递归调用的栈开销对小区间影响更显著）：

#define MAX_LENGTH_INSERT_SORT 7 // 小区间阈值

void QSort(int* a, int low, int high)
{
    if (high - low > MAX_LENGTH_INSERT_SORT)
    {
        // 区间较大，用快速排序
        int div = PartSort1(a, low, high);
        QSort(a, low, div - 1);
        QSort(a, div + 1, high);
    }
    else
    {
        // 区间较小，用直接插入排序（排序区间为[a+low, high-low+1]）
        InsertSort(a + low, high - low + 1);
    }
}

⑥ 特性

• 时间复杂度：平均O(n log n)，最坏O(n²)（未优化时基准值选到最值），优化后极少出现最坏情况；
• 空间复杂度：递归实现O(log n)（递归栈深度，与划分次数一致），非递归实现O(log n)（栈存储区间边界）；
• 稳定性：不稳定，划分过程中可能交换非相邻的相同元素，改变其相对次序。

4. 归并排序：分治合并构建有序序列

归并排序是 “分治法” 的典型应用，核心思想是 “先将数组分成若干子数组，分别排序后，再将有序子数组合并为一个完整的有序数组”，是少数稳定且时间复杂度为O(n log n)的算法之一。

（1）递归实现

基本逻辑：将数组从中间分成左右两个子数组，递归排序两个子数组，再通过 “合并” 操作将两个有序子数组合并为一个有序数组。合并时需借助临时数组存储中间结果，避免原数组元素被覆盖。

代码实现：

// 归并排序辅助函数：合并两个有序子数组[left, mid]和[mid+1, right]
void Merge(int* a, int left, int mid, int right, int* tmp)
{
    int i = left;    // 左子数组起始下标
    int j = mid + 1; // 右子数组起始下标
    int k = left;    // 临时数组tmp的起始下标

    // 比较两个子数组元素，按升序存入tmp
    while (i <= mid && j <= right)
    {
        if (a[i] <= a[j])
        {
            tmp[k++] = a[i++];
        }
        else
        {
            tmp[k++] = a[j++];
        }
    }

    // 处理左子数组剩余元素
    while (i <= mid)
    {
        tmp[k++] = a[i++];
    }

    // 处理右子数组剩余元素
    while (j <= right)
    {
        tmp[k++] = a[j++];
    }

    // 将临时数组中的有序元素拷贝回原数组
    for (k = left; k <= right; k++)
    {
        a[k] = tmp[k];
    }
}

// 归并排序递归核心（需提前创建临时数组，避免递归中频繁开辟内存）
void MergeSortRecur(int* a, int left, int right, int* tmp)
{
    if (left >= right)
    {
        return; // 区间长度≤1，无需排序
    }

    int mid = (left + right) / 2;
    // 递归排序左子数组[left, mid]
    MergeSortRecur(a, left, mid, tmp);
    // 递归排序右子数组[mid+1, right]
    MergeSortRecur(a, mid + 1, right, tmp);
    // 合并两个有序子数组
    Merge(a, left, mid, right, tmp);
}

// 归并排序对外接口
void MergeSort(int* a, int n)
{
    // 开辟临时数组，存储合并过程中的有序元素
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc fail"); // 内存开辟失败提示
        return;
    }

    MergeSortRecur(a, 0, n - 1, tmp);
    free(tmp); // 释放临时数组，避免内存泄漏
    tmp = NULL;
}

（2）非递归实现

基本逻辑：通过 “步长” 控制分组，初始步长为 1（每组 1 个元素，默认有序），按步长将数组分成若干组，每组包含两个有序子数组，合并后步长翻倍；重复分组与合并操作，直到步长大于数组长度，完成排序。

代码实现：

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc fail");
        return;
    }

    int step = 1; // 初始步长：每组1个元素
    while (step < n)
    {
        // 按步长分组，每组包含两个子区间，合并后步长翻倍
        for (int i = 0; i < n; i += 2 * step)
        {
            int left = i;
            int mid = i + step - 1;
            int right = i + 2 * step - 1;

            // 处理右子区间超出数组长度的情况
            if (mid >= n)
            {
                mid = n - 1;
            }
            if (right >= n)
            {
                right = n - 1;
            }

            // 合并当前两个子区间
            Merge(a, left, mid, right, tmp);
        }
        step *= 2; // 步长翻倍，进入下一轮合并
    }

    free(tmp);
    tmp = NULL;
}

（3）特性

• 时间复杂度：分解过程需O(log n)层，每层合并需O(n)，整体时间复杂度O(n log n)；
• 空间复杂度：O(n)，需借助临时数组存储合并结果，非原地排序；
• 稳定性：稳定，合并时相同元素按原数组中的相对次序存入临时数组，不会改变其位置关系；
• 适用场景：需稳定排序的场景，或外部排序（如磁盘大文件排序，可分块排序后再合并）。

5. 计数排序：非比较排序的典型应用

计数排序属于 “非比较排序”，不通过比较元素大小排序，而是基于 “鸽巢原理”，通过统计元素出现次数实现排序，适用于元素值范围较小且为整数的场景（如学生成绩、年龄排序）。

（1）基本逻辑

1. 确定范围：找出待排序数组中的最大值和最小值，确定统计数组的长度（长度 = 最大值 - 最小值 + 1）；
2. 统计次数：遍历待排序数组，统计每个元素的出现次数，存入统计数组；
3. 生成结果：根据统计数组的次数，从前往后（或从后往前，保证稳定性）将元素按次数填入原数组，生成有序序列。

代码实现：

// 计数排序（支持负整数，通过偏移量处理）
void CountSort(int* a, int n)
{
    if (n <= 1)
    {
        return; // 数组长度≤1，无需排序
    }

    // 1. 找出数组中的最大值和最小值，确定统计数组范围
    int min = a[0], max = a[0];
    for (int i = 1; i < n; i++)
    {
        if (a[i] < min)
        {
            min = a[i];
        }
        if (a[i] > max)
        {
            max = a[i];
        }
    }

    // 2. 开辟统计数组，初始化并统计元素出现次数
    int range = max - min + 1;
    int* count = (int*)calloc(range, sizeof(int)); // calloc自动初始化为0
    if (count == NULL)
    {
        perror("calloc fail");
        return;
    }

    for (int i = 0; i < n; i++)
    {
        count[a[i] - min]++; // 偏移量：将元素映射到统计数组的非负下标
    }

    // 3. 根据统计数组生成有序序列（从后往前遍历，保证稳定性）
    int idx = n - 1;
    for (int i = range - 1; i >= 0; i--)
    {
        while (count[i] > 0)
        {
            a[idx--] = i + min; // 还原元素值（偏移量回退）
            count[i]--;
        }
    }

    free(count);
    count = NULL;
}

（2）特性

• 时间复杂度：O(n + range)（n为元素个数，range为元素值范围），当range远小于n时，效率极高；
• 空间复杂度：O(range)，取决于元素值范围；
• 稳定性：稳定，从后往前遍历统计数组生成结果时，可保持相同元素的相对次序；
• 适用场景：元素值范围小且为整数的场景，如 0-100 的学生成绩排序、0-120 的年龄排序等。

三、排序算法性能对比与选择

不同排序算法的性能差异显著，实际开发中需根据数据规模、数据特性（是否有序、是否为整数）、稳定性需求等选择合适的算法，以下为核心算法的性能对比：

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性	核心适用场景
直接插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定	数据量小、基本有序（如小表格排序）
希尔排序	O(n^1.25)	O(n)	O(n²)	O(1)	不稳定	数据量中等，需原地排序
直接选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定	数据量极小，对效率无要求
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定	内存紧张，需高效原地排序（如嵌入式设备）
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定	教学场景，理解排序基本逻辑
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定	大多数高效排序场景（默认首选，如数据库排序、框架底层）
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定	需稳定排序、外部排序（如磁盘大文件）
计数排序	O(n + range)	O(n + range)	O(n + range)	O(range)	稳定	元素值范围小的整数排序（如成绩、年龄）

四、总结

排序算法是数据结构与算法的基础，掌握不同算法的核心逻辑、性能特性与适用场景，是高效解决实际问题的关键。日常开发中，快速排序因综合性能最优成为首选；需稳定排序时可选择归并排序；内存紧张时堆排序更合适；元素值范围小时计数排序效率极高。通过理解算法的设计思想（如分治法、鸽巢原理），还能为复杂问题的解决提供思路，助力提升编程能力。