排序算法总结

数据结构与算法 / 作者： /

1 各种排序的复杂度和稳定性

排序算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
冒泡排序 O(n²) O(n²) O(n) O(1) 稳定
选择排序 O(n²) O(n²) O(n²) O(1) 不稳定
直接插入排序 O(n²) O(n²) O(n) O(1) 稳定
快速排序 O(nlogn) O(n²) O(nlogn) O(nlogn) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
希尔排序 O(n1.3) O(n2) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
计数排序 O(n+k) O(n+k) O(n+k) O(n+k) 稳定
基数排序 O(d*(n+k)) O(d*(n+k)) O(d*(n+k)) O(n+k) 稳定
桶排序 O(n+C) O(n2) O(n) O(n+k) 稳定

冒泡排序：对数据的有序性敏感。通过优化（如设置交换标志），可提前终止排序过程

选择排序：完全不受数据初始状态影响，无论有序或逆序，比较次数固定为 n(n-1)/2

插入排序：在数据接近有序时效率极高，甚至优于某些 O(nlogn) 算法；但在完全逆序时效率最低；常用于其他排序算法（如快速排序）的优化子过程

计数排序、基数排序、桶排序都叫外部排序，当数据量过大，不可能全部加载到内存中时使用。外部排序通常涉及到数据的分区处理，部分数据被暂时存储在外部磁盘等存储设备上。这三种排序都可以将数据进行分区处理。

2 各种排序的源代码

2.1 冒泡排序

// FLAG是对冒泡排序的优化，当已经排好序后，不用再循环比较了，可以直接退出。
void BubbleSort(std::vector<int>& vec) {
  bool flag = true;
  for (int i = 0; i < vec.size() && flag; ++i) {
    bool flag = false;
    for (int j = vec.size() - 2; j >= i; --j) {
      if (vec[j] > vec[j + 1]) {
        std::swap(vec[j], vec[j + 1]);
        flag = true;
      }
    }
  }
}

2.2 选择排序

void SelectionSort(std::vector<int>& vec) {
  int min;
  for (int i = 0; i < vec.size(); ++i) {
    min = i;
    for (int j = i + 1; j < vec.size(); ++j) {
      if (vec[min] > vec[j]) {
        min = j;
      }
    }
    if (min != i) {
      std::swap(vec[i], vec[min]);
    }
  }
}

2.3 插入排序

void InsertSort(std::vector<int>& vec) {
  int sentinel, j;
  for (int i = 1; i < vec.size(); ++i) {
    sentinel = vec[i];
    j = i - 1;
    if (vec[j] <= sentinel) {
      continue;
    }
    for (; j >= 0; --j) {
      if (vec[j] <= sentinel) {
        break;
      }
      vec[j + 1] = vec[j];
    }
    vec[j + 1] = sentinel;
  }
}

2.4 希尔排序

// 便于理解版本
// 分组不交错处理，先处理完一个分组，再去处理另一个分组
// 先排序1A->1E，在排序2A->2E
void ShellSort1(std::vector<int>& vec) {
  int n = vec.size();
  for (int gap = n / 2; gap > 0; gap >>= 1) {  // 步长
    for (int i = 0; i < gap; ++i) {
      // 插入排序
      for (int j = i + gap; j < n; j += gap) {
        if (vec[j] < vec[j - gap]) {
          int sentinel = vec[j];
          int k = j - gap;
          while (k >= 0 && vec[k] > sentinel) {
            vec[k + gap] = vec[k];
            k -= gap;
          }
          vec[k + gap] = sentinel;
        }
      }
    }
  }
}

上面的shellsort1代码虽然对直观的理解希尔排序有帮助，但代码量太大了，不够简洁清晰。因此进行下改进和优化，以第二次排序为例，原来是每次从1A到1E，从2A到2E，可以改成从1B开始，先和1A比较，然后取2B与2A比较，再取1C与前面自己组内的数据比较…….。这种每次从数组第gap个元素开始，每个元素与自己组内的数据进行直接插入排序显然也是正确的。

// 优化版本
// 分组和分组交错处理
// 从1B开始，先与1A比较；然后从2B开始，与2A比较；
void ShellSort2(std::vector<int>& vec) {
  int n = vec.size();
  for (int gap = n / 2; gap > 0; gap >>= 1) {  // 步长

    // 从数组的第gap个元素开始
    for (int j = gap; j < n; j++) {
      // 每个元素与自己组内的数据插入排序
      if (vec[j] < vec[j - gap]) {
        int sentinel = vec[j];
        int k = j - gap;
        while (k >= 0 && vec[k] > sentinel) {
          vec[k + gap] = vec[k];
          k -= gap;
        }
        vec[k + gap] = sentinel;
      }
    }
  }
}

2.5 堆排序

在完全二叉树中（下标从1开始），若当前节点的下标为 i， 则其父节点的下标为 i/2（向下取整），其左子节点的下标为 i*2，其右子节点的下标为i*2+1；

在完全二叉树中（下标从0开始），若当前节点的下标为 i， 则其父节点的下标为 (i-1)/2（向下取整），其左子节点的下标为 i*2+1，其右子节点的下标为i*2+2；

#include <iostream>
#include <vector>
using namespace std;

// 最大堆排序的结果是从小到大。
// 堆调整函数（维护最大堆性质）
void heapify(vector<int>& arr, int heapSize, int parentIndex) {
  int largest = parentIndex;  // 初始化最大元素为父节点
  int leftChild = 2 * parentIndex + 1;
  int rightChild = 2 * parentIndex + 2;

  // 比较左子节点与父节点
  if (leftChild < heapSize && arr[leftChild] > arr[largest])
    largest = leftChild;

  // 比较右子节点与当前最大值
  if (rightChild < heapSize && arr[rightChild] > arr[largest])
    largest = rightChild;

  // 若最大值不是父节点则交换，并递归调整
  if (largest != parentIndex) {
    swap(arr[parentIndex], arr[largest]);
    heapify(arr, heapSize, largest);
  }
}

// 堆排序主函数
void heapSort(vector<int>& arr) {
  int n = arr.size();

  // 构建最大堆（从最后一个非叶子节点开始）
  for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // 逐个提取堆顶元素排序
  for (int i = n - 1; i > 0; i--) {
    swap(arr[0], arr[i]);  // 将当前最大值移到数组末尾
    heapify(arr, i, 0);    // 调整剩余元素为最大堆
  }
}

// 测试示例
int main() {
  vector<int> arr = {12, 11, 13, 5, 6, 7};
  cout << "原始数组: ";
  for (int num : arr) cout << num << " ";

  heapSort(arr);

  cout << "\n排序后数组: ";
  for (int num : arr) cout << num << " ";
  return 0;
}

建堆的复杂度为O(n)，排序的复杂度为O(n*logn)，其实堆排序相当于是选择排序的一种。
堆排序就相当于是堆的元素删除过程，堆的元素删除只能删除堆顶元素。

堆排序视频
除此之外，需要补充堆的插入操作（即如何shift-up），注意堆的删除和构建都是（shift-down）操作，参考堆插入、删除、构建操作，
以及C++基于vector如何进行make_heap、push_heap、pop_heap，pop_heap后需要pop_back，push_heap前需要push_back。

pop_heap(v.begin(), v.end());       // move heap top to the end
v.pop_back();                       // pop/remove back the last element

v.push_back(99);                    // insert an element to the end
push_heap(v.begin(), v.end());      // rearrange elements to form a heap

扩展: C++ priority_queue、LCR159

2.6 归并排序

主要需要注意需要一个临时的辅助数组。

#include <algorithm>
#include <iostream>

using namespace std;

void Merge(std::vector<int>& a, int left, int mid, int right) {
  vector<int> temp(right - left + 1);  // 临时数组用于存储排序时的数
  int i = left;  // 分成两块 i指向左边的数字 j指向右边的数字
  int j = mid + 1;
  int k = 0;  // k用于存储数字到临时数组

  while (i <= mid && j <= right) {
    if (a[i] < a[j])       // 永远都是 i 和 j 指向的数进行比较
      temp[k++] = a[i++];  // 谁小，谁就先放到临时数组中
    else
      temp[k++] = a[j++];
  }

  while (i <= mid)  // 如果左边还有数没放上去，就依次放上去
    temp[k++] = a[i++];
  while (j <= right)  // 如果是右边还有同上
    temp[k++] = a[j++];

  // 临时数组已经排好序，复制到原数组中。
  copy(temp.begin(), temp.end(), a.begin() + left);
  /*
  for (int m = left, n = 0; m <= right; m++, n++)
    a[m] = temp[n];
  */
}

void MergeSort(std::vector<int>& a, int left, int right) {
  if (left == right) return;

  int mid = (left + right) / 2;
  // 递归拆分成较小规模子序列排序
  MergeSort(a, left, mid);
  MergeSort(a, mid + 1, right);
  Merge(a, left, mid, right);  // 合并较小规模问题解
}

int main() {
  std::vector<int> vec({4, 3, 6, 2, 1, 7, 5});
  std::cout << "before sort: " << std::endl;
  for (int i : vec) {
    std::cout << i << ", ";
  }
  std::cout << std::endl;
  MergeSort(vec, 0, vec.size() - 1);
  std::cout << "after sort: " << std::endl;
  for (int i : vec) {
    std::cout << i << ", ";
  }
  std::cout << std::endl;
}

扩展：LCR170

2.7 快速排序

#include <iostream>
#include <vector>

int Partition1(std::vector<int>& vec, int low, int high) {
  // 可以用三数取中的方法将选中的值交换到vec[low]
  int pivotkey = vec[low];
  while (low < high) {
    while (low < high && vec[high] >= pivotkey) {
      high--;
    }
    std::swap(vec[low], vec[high]);
    while (low < high && vec[low] <= pivotkey) {
      low++;
    }
    std::swap(vec[low], vec[high]);
  }
  // 这种方法枢轴自动在中间了
  // return pivot
  return low;
}

int Partition2(std::vector<int>& vec, int low, int high) {
  // 可以用三数取中的方法将选中的值交换到vec[low]
  int pivotkey = vec[low];
  while (low < high) {
    while (low < high && vec[high] >= pivotkey) {
      high--;
    }
    // 使用替换代替swap，提高效率
    vec[low] = vec[high];
    while (low < high && vec[low] <= pivotkey) {
      low++;
    }
    vec[high] = vec[low];
  }
  // 但需要对枢轴进行赋值
  vec[low] = pivotkey;
  // return pivot
  return low;
}

int Partition3(std::vector<int>& vec, int low, int high) {
  // 可以用三数取中的方法将选中的值交换到vec[low]
  int pivotkey = vec[low];
  int start = low; // 记住这一行
  while (low < high) {
    while (low < high && vec[high] >= pivotkey) {
      high--;
    }
    while (low < high && vec[low] <= pivotkey) {
      low++;
    }
    // 同时交换
    std::swap(vec[low], vec[high]);
  }
  // 这是枢轴在哨兵start处，需要将哨兵和low交换，将枢轴换到中间来
  std::swap(vec[low], vec[start]);
  return low;
}

void QuickSort(std::vector<int>& vec, int low, int high) {
  if (low < high) {
    int pivot = Partition3(vec, low, high);
    // 可以判断high-low+1的大小，较小时使用插入排序
    QuickSort(vec, low, pivot - 1);
    // *可以使用尾递归的方式，减少递归
    QuickSort(vec, pivot + 1, high);
  }
}

int main() {
  std::vector<int> vec({4,3,6,2,1,7, 5});
  std::cout << "before sort: " << std::endl;
  for (int i : vec) {
    std::cout << i << ", ";
  }
  std::cout << std::endl;
  QuickSort(vec, 0, vec.size() - 1);
  std::cout << "after sort: " << std::endl;
  for (int i : vec) {
    std::cout << i << ", ";
  }
  std::cout << std::endl;
}

扩展：
LCR139、LCR158、LCR159、LCR164

2.8 计数排序

#include <vector>
#include <algorithm>

void countingSort(std::vector<int>& arr) {
    if (arr.empty()) return;

    // 确定数据范围
    int max_val = *std::max_element(arr.begin(), arr.end());
    int min_val = *std::min_element(arr.begin(), arr.end());
    int range = max_val - min_val + 1;

    // 创建计数数组和结果数组
    std::vector<int> count(range, 0);
    std::vector<int> output(arr.size());

    // 统计元素出现次数
    for (int num : arr) 
        ++count[num - min_val];

    // 计算前缀和确定位置
    for (int i = 1; i < range; ++i)
        count[i] += count[i - 1];

    // 反向填充保证稳定性
    for (int i = arr.size() - 1; i >= 0; --i) {
        output[count[arr[i] - min_val] - 1] = arr[i];
        --count[arr[i] - min_val];
    }

    arr = output;
}

疑惑点：
直接从前往后根据下标输出不就好了吗。为什么还需要计算前缀和和反向填充呢？
这是因为每个元素都是一个个体，如果遇到相同元素为了保证稳定性，即排序后相同元素前后次序和原数组中的前后顺序要保持一致。
为了避免数据混乱即保持稳定性，我们从后往前进行遍历。每次都将元素对应的 nums 值减 1 ，这个值就是位置，直接反向填充到output数组中。
时间复杂度：O(n + k)（k为数据范围），空间复杂度O(n+k)
适合数据范围小的整数

2.9 基数排序

#include <vector>
#include <algorithm>

// 辅助计数排序（按特定位排序）
void countingSortForRadix(std::vector<int>& arr, int exp) {
    std::vector<int> output(arr.size());
    std::vector<int> count(10, 0);

    // 统计当前位出现次数
    for (int num : arr)
        ++count[(num / exp) % 10];

    // 计算前缀和
    for (int i = 1; i < 10; ++i)
        count[i] += count[i - 1];

    // 反向填充
    for (int i = arr.size() - 1; i >= 0; --i) {
        output[count[(arr[i]/exp)%10] - 1] = arr[i];
        --count[(arr[i]/exp)%10];
    }

    arr = output;
}

void radixSort(std::vector<int>& arr) {
    if (arr.empty()) return;

    // 获取最大值的位数
    int max_val = *std::max_element(arr.begin(), arr.end());
    for (int exp = 1; max_val/exp > 0; exp *= 10)
        countingSortForRadix(arr, exp); // 逐位排序[10](@ref)
}

代码不用记，只用弄懂原理。
时间复杂度O(d*(n+k))，d为数据的最大位数，k为基数（十进制为 10，字母为 26）
空间复杂度O(n+k)
适合大整数排序

2.10 桶排序

#include <vector>
#include <algorithm>

void bucketSort(std::vector<int>& arr) {
    if (arr.empty()) return;

    // 确定数据范围
    int max_val = *std::max_element(arr.begin(), arr.end());
    int min_val = *std::min_element(arr.begin(), arr.end());
    int range = max_val - min_val;

    // 创建动态桶（每桶范围=总范围/桶数量）
    int bucket_num = arr.size();
    std::vector<std::vector<int>> buckets(bucket_num);

    // 分配元素到桶中
    for (int num : arr) {
        int index = (num - min_val) * bucket_num / (range + 1);
        buckets[index].push_back(num);
    }

    // 对各桶排序并合并
    int idx = 0;
    for (auto& bucket : buckets) {
        std::sort(bucket.begin(), bucket.end());
        for (int num : bucket)
            arr[idx++] = num;
    }
}

适合均匀分布的数据，可用于浮点数排序
时间复杂度分析：
最佳O(n)：当数据均匀分布在各个桶中，且桶的数量足够多（例如每个桶仅含一个元素）时，桶内无需排序，只需线性时间完成数据分配和合并
最坏O(n²)：当所有元素集中在一个桶中，且桶内使用冒泡排序、插入排序等 O(n²) 算法时，时间复杂度退化为平方级
平均O(n + C)（C = n(log n – log m)，m为桶数量）
假设数据均匀分布，每个桶内元素数量为 n/m，若采用快速排序等 O(k log k) 的算法对单个桶排序（k为桶内元素数），则总时间复杂度为：O(n)+O(m*n/m*log(n/m))=O(n+nlog(n/m))

空间复杂度分析：O(n+m)，m为桶的数量

桶排序、计数排序、基数排序参考：
https://blog.csdn.net/Newin2020/article/details/125501274

3 排序相关问题

3.1 为什么堆排序相对于快速排序更加适合大规模数据？

堆排序相对于快速排序更适合大规模数据处理的原因，主要源自其算法特性与资源效率的优化方向。以下从多个维度详细分析：

3.1.1 时间复杂度稳定性

  1. 最坏情况下的保障
    堆排序的时间复杂度始终为 O(n log n)，无论数据分布如何。这对大规模数据尤为重要，因为数据量越大，出现极端分布（如已排序或逆序数据）的概率增加。而快速排序在最坏情况下（如基准值总选最小/最大值）会退化到 O(n²)，这在处理千万级以上的数据时可能引发性能灾难。

  2. 避免递归深度问题
    快速排序的递归调用栈深度与数据分割方式相关，极端情况下可能导致栈溢出（如处理10亿数据时递归深度可能达数万层）。堆排序通过非递归的堆调整操作规避了这一风险。

3.1.2 空间效率与内存管理

  1. 原地排序特性
    堆排序仅需 O(1) 的额外空间，完全在原数组上操作。快速排序虽也是原地排序，但其递归调用栈会消耗 O(log n) 的隐式空间。当数据规模达到TB级时，堆排序的内存占用优势更为显著。

  2. 外部排序的适配性
    对于无法一次性加载到内存的超大规模数据，堆排序可结合分块策略实现外部排序。例如，将数据分割为多个子块分别构建堆，再通过多路归并完成全局排序。这种特性使其在大数据存储系统（如HDFS）中广泛应用。

3.1.3 算法稳定性与数据敏感性

  1. 对数据分布的鲁棒性
    快速排序的性能高度依赖基准值选择，若数据分布不均（如大量重复值或部分有序），即使采用三数取中法优化，仍可能出现性能波动。堆排序的完全二叉树结构使其对数据分布不敏感，尤其适合金融风控等需处理海量异构数据的场景。

  2. 避免“交换抖动”问题
    堆排序通过逐层筛选减少数据移动次数，而快速排序在分区过程中频繁交换元素，导致缓存命中率降低。测试表明，在10亿级数据排序时，堆排序的缓存友好性可减少约30%的I/O耗时。

3.1.4 特定场景的扩展性

  1. 动态数据流的处理
    在实时数据流（如网络日志分析）中，堆排序可通过动态维护最大/最小堆，实现Top-K查询（如实时热搜榜）。而快速排序需等待数据完全输入后才能排序，无法满足实时性要求。

  2. 并行化潜力
    堆排序的建堆与调整过程可分解为独立子树操作，更易通过多线程或分布式计算加速。例如，在GPU上并行构建多个子堆，相比快速排序的分区依赖，并行效率提升可达2-3倍。

3.1.5 性能权衡与选型建议

维度 堆排序优势 快速排序劣势
最坏时间复杂度 O(n log n) 稳定 可能退化为 O(n²)
内存消耗 严格 O(1) 递归栈消耗 O(log n)
数据敏感性 不受分布影响 依赖基准值选择优化
扩展性 支持外部排序、实时查询 需全量数据加载

3.1.6 总结

尽管快速排序在平均情况下（随机数据）速度更快，但堆排序凭借时间复杂度稳定、内存效率高、适应性强等特性，更适用于大规模数据场景，尤其在数据分布不可预测、内存资源受限或需实时处理的系统中占据优势。实际选型时，若对稳定性要求严格且数据规模极大，应优先考虑堆排序；若追求平均性能且数据规模可控，快速排序仍是优选。

相关文章

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

目录

→ Contents
滚动至顶部