排序算法总结（C++）

一、稳定性

排序算法的稳定性是指：同样大小的样本 **（同样大小的数据）**在排序之后不会改变原始的相对次序。

稳定性对基础类型对象（如平常的数组）来说毫无意义；稳定性对非基础类型对象（如一些自定义类）有意义，可以保留之前的相对次序。

二、排序算法

• 基于比较的排序：
  只需要定义好两个对象之间怎么比较即可，对象的数据特征并不关心，很通用（除下面两种）；

• 不基于比较的排序：
  和比较无关的排序，对于对象的数据特征有要求，并不通用（如计数排序、基数排序）；

选择、冒泡、插入排序

// 交换数组中的两个元素
void swap(int arr[], int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;
}// 选择排序
void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}swap(arr, i, minIndex);}
}// 冒泡排序
void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);}}}
}// 插入排序
void insertionSort(int arr[], int n) {if (arr == nullptr || n < 2) {return;}for (int i = 1; i < n; i++) {for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {swap(arr, j, j + 1);// printarr(arr, n); // 打印当前数组状态}}
}

归并排序

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // 用于 std::memsetconst int MAXN = 100001;int arr[MAXN];
int help[MAXN];
int n;// 归并排序递归版
void mergeSort1(int l, int r) {if (l == r) {return;}int m = (l + r) / 2;mergeSort1(l, m);mergeSort1(m + 1, r);int i = l, a = l, b = m + 1;while (a <= m && b <= r) {help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];}while (a <= m) {help[i++] = arr[a++];}while (b <= r) {help[i++] = arr[b++];}for (i = l; i <= r; i++) {arr[i] = help[i];}
}// 归并排序非递归版
void mergeSort2() {for (int step = 1; step < n; step <<= 1) {int l = 0;while (l < n) {int m = l + step - 1;if (m + 1 >= n) {break;}int r = std::min(l + (step << 1) - 1, n - 1);int i = l, a = l, b = m + 1;while (a <= m && b <= r) {help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];}while (a <= m) {help[i++] = arr[a++];}while (b <= r) {help[i++] = arr[b++];}for (i = l; i <= r; i++) {arr[i] = help[i];}l = r + 1;}}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cin >> n;for (int i = 0; i < n; i++) {std::cin >> arr[i];}// 选择一种归并排序方式// mergeSort1(0, n - 1);mergeSort2();for (int i = 0; i < n - 1; i++) {std::cout << arr[i] << " ";}std::cout << arr[n - 1] << std::endl;return 0;
}

随机快速排序

#include <iostream>
#include <cstdlib> // 用于 rand() 和 srand()
#include <ctime>   // 用于 time()const int MAXN = 100001;
int arr[MAXN];
int n;// 随机快速排序改进版
void quickSort2(int l, int r) {if (l >= r) {return;}// 随机选择基准值int x = arr[l + rand() % (r - l + 1)];// 调用荷兰国旗问题的划分函数partition2(l, r, x);// 获取等于区域的左右边界int left = first;int right = last;// 递归排序左右两部分quickSort2(l, left - 1);quickSort2(right + 1, r);
}// 荷兰国旗问题的划分函数
int first, last;//分别控制左右两侧的边界移动void partition2(int l, int r, int x) {first = l;last = r;int i = l;while (i <= last) {if (arr[i] == x) {i++;} else if (arr[i] < x) {std::swap(arr[first++], arr[i++]);} else {std::swap(arr[i], arr[last--]);}}
}// 主函数
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cin >> n;for (int i = 0; i < n; i++) {std::cin >> arr[i];}// 初始化随机数种子std::srand(std::time(nullptr));// 调用快速排序quickSort2(0, n - 1);// 输出排序结果for (int i = 0; i < n - 1; i++) {std::cout << arr[i] << " ";}std::cout << arr[n - 1] << std::endl;return 0;
}

堆排序

#include <iostream>
#include <vector>// 主函数，对数组进行排序
std::vector<int> sortArray(std::vector<int>& nums) {if (nums.size() > 1) {// heapSort1为从顶到底建堆然后排序// heapSort2为从底到顶建堆然后排序// 用哪个都可以// heapSort1(nums);heapSort2(nums);}return nums;
}// i位置的数，向上调整大根堆
// arr[i] = x，x是新来的！往上看，直到不比父亲大，或者来到0位置(顶)
void heapInsert(std::vector<int>& arr, int i) {while (arr[i] > arr[(i - 1) / 2]) {swap(arr, i, (i - 1) / 2);i = (i - 1) / 2;}
}// i位置的数，变小了，又想维持大根堆结构
// 向下调整大根堆
// 当前堆的大小为size
void heapify(std::vector<int>& arr, int i, int size) {int l = i * 2 + 1;while (l < size) {// 有左孩子，l// 右孩子，l+1// 评选，最强的孩子，是哪个下标的孩子int best = (l + 1 < size && arr[l + 1] > arr[l]) ? l + 1 : l;// 上面已经评选了最强的孩子，接下来，当前的数和最强的孩子之前，最强下标是谁best = (arr[best] > arr[i]) ? best : i;if (best == i) {break;}swap(arr, best, i);i = best;l = i * 2 + 1;}
}void swap(std::vector<int>& arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;
}// 从顶到底建立大根堆，O(n * logn)
// 依次弹出堆内最大值并排好序，O(n * logn)
// 整体时间复杂度O(n * logn)
void heapSort1(std::vector<int>& arr) {int n = arr.size();for (int i = 0; i < n; i++) {heapInsert(arr, i);}int size = n;while (size > 1) {swap(arr, 0, --size);heapify(arr, 0, size);}
}// 从底到顶建立大根堆，O(n)
// 依次弹出堆内最大值并排好序，O(n * logn)
// 整体时间复杂度O(n * logn)
void heapSort2(std::vector<int>& arr) {int n = arr.size();for (int i = n - 1; i >= 0; i--) {heapify(arr, i, n);}int size = n;while (size > 1) {swap(arr, 0, --size);heapify(arr, 0, size);}
}int main() {// 示例测试std::vector<int> nums = {3, 2, 1, 5, 6, 4};std::vector<int> sortedNums = sortArray(nums);std::cout << "排序后的数组: ";for (int num : sortedNums) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

基数排序

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // 用于 memsetusing namespace std;const int BASE = 100; // 可以设置进制
const int MAXN = 50001;int help[MAXN];
int cnts[BASE];// 返回 number 在 BASE 进制下有几位
int bits(int number) {int ans = 0;while (number > 0) {ans++;number /= BASE;}return ans;
}// 基数排序核心代码
// arr 内要保证没有负数
// n 是 arr 的长度
// bits 是 arr 中最大值在 BASE 进制下有几位
void radixSort(vector<int>& arr, int n, int bits) {for (int offset = 1; bits > 0; offset *= BASE, bits--) {memset(cnts, 0, sizeof(cnts)); // 初始化计数数组for (int i = 0; i < n; i++) {// 数字提取某一位的技巧cnts[(arr[i] / offset) % BASE]++;}// 处理成前缀次数累加的形式for (int i = 1; i < BASE; i++) {cnts[i] = cnts[i] + cnts[i - 1];}for (int i = n - 1; i >= 0; i--) {// 前缀数量分区的技巧// 数字提取某一位的技巧help[--cnts[(arr[i] / offset) % BASE]] = arr[i];}for (int i = 0; i < n; i++) {arr[i] = help[i];}//      for (int num : arr) {//     cout << num << " ";// }// cout << endl;}
}vector<int> sortArray(vector<int>& arr) {if (arr.size() > 1) {int n = arr.size();// 找到数组中的最小值int min_val = arr[0];for (int i = 1; i < n; i++) {min_val = min(min_val, arr[i]);}int max_val = 0;for (int i = 0; i < n; i++) {// 数组中的每个数字，减去最小值，转成非负数组arr[i] -= min_val;// 记录数组中的最大值max_val = max(max_val, arr[i]);}// 根据最大值在 BASE 进制下的位数，决定基数排序做多少轮radixSort(arr, n, bits(max_val));// 数组中所有数都减去了最小值，最后还原for (int i = 0; i < n; i++) {arr[i] += min_val;}}return arr;
}int main() {int n;cout << "Enter the number of elements: ";// cin >> n;vector<int> arr({170, 45, 75, 90, 802, 24, 2, 66}); // 示例数组cout << "Enter the elements: ";// for (int i = 0; i < n; i++) {//     cin >> arr[i];// }vector<int> sorted_arr = sortArray(arr);cout << "Sorted array: ";for (int num : sorted_arr) {cout << num << " ";}cout << endl;return 0;
}

计数排序

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 计数排序方法，接受一个整数数组作为参数，返回排序后的数组
vector<int> countingSort(const vector<int>& arr) {// 如果输入数组为空或者长度小于等于1，直接返回原数组// 因为空数组或只有一个元素的数组本身就是有序的if (arr.size() <= 1) {return arr;}// 找出数组中的最大值和最小值，用于确定计数数组的范围int max_val = arr[0];int min_val = arr[0];for (int num : arr) {// 如果当前数字大于最大值，则更新最大值if (num > max_val) {max_val = num;}// 如果当前数字小于最小值，则更新最小值else if (num < min_val) {min_val = num;}}// 创建计数数组，其长度为最大值与最小值的差加1// 这样计数数组的每个索引就可以对应于原数组中的一个值（经过最小值偏移）vector<int> count(max_val - min_val + 1, 0);// 统计原数组中每个值出现的次数// 通过将每个数减去最小值来得到在计数数组中的偏移索引for (int num : arr) {count[num - min_val]++;}// 将计数数组转换为每个元素的最终位置索引数组// 这里的操作是对计数数组进行累加// 例如，如果count[0]=3，count[1]=2，那么经过这个循环后count[1]=5// 表示原数组中值为1（假设最小值为0）的最后一个元素应该放在新数组的第5个位置（索引为4）for (size_t i = 1; i < count.size(); i++) {count[i] += count[i - 1];}// 创建一个与原数组长度相同的输出数组，用于存储排序后的结果vector<int> output(arr.size());// 从原数组的末尾开始遍历for (int i = arr.size() - 1; i >= 0; i--) {// 根据计数数组中的位置信息，将原数组中的元素放入输出数组中正确的位置// 注意这里要先减1，因为数组索引从0开始output[count[arr[i] - min_val] - 1] = arr[i];// 将计数数组中对应位置的值减1，表示已经处理了一个该值的元素count[arr[i] - min_val]--;}// 返回排序后的数组return output;
}// 主函数，用于测试计数排序算法
int main() {vector<int> arr = {4, 2, 2, 8, 3, 3, 1};// 调用计数排序方法对数组进行排序vector<int> sorted = countingSort(arr);// 输出排序后的数组for (int num : sorted) {cout << num << " ";}cout << endl;return 0;
}

三、总结

• 数据量非常小的情况下可以做到非常迅速：插入排序
• 性能优异、实现简单且利于改进（面对不同业务可以选择不同划分策略）、不在乎稳定性：随机快排
• 性能优异、不在乎额外空间占用、具有稳定性：归并排序
• 性能优异、额外空间占用要求O(1)、不在乎稳定性：堆排序