本篇核心知识点算法时间复杂度分级、稳定 / 不稳定排序定义、快速排序、堆排序、归并排序原理与完整代码、八大排序分类一、算法时间复杂度分级1. 概念时间复杂度用来衡量算法运行步数随数据量n的增长趋势采用大 O 记法只保留最高次项忽略常数与低次项是选择算法、数据结构核心依据。2. 各类复杂度概念 特性O (1) 常数级概念无循环执行步骤固定与数据量无关。特性数组下标随机访问、哈希表单点查找。O (logn) 对数级概念每次处理后数据规模折半循环条件成倍变化。特性平衡二叉搜索树、二分查找每次排除一半数据。O (n) 线性级概念单层循环遍历全部数据一次。特性链表完整遍历、普通顺序查找。O (nlogn) 线性对数级概念一层线性循环嵌套一层对数循环。特性快速排序、堆排序、归并排序平均复杂度。O (n²) 平方级概念两层嵌套循环数据越大效率暴跌。特性冒泡、选择、插入基础排序。拓展对比数据量大时优先级O (1) O (logn) O (nlogn) O (n) O (n²)二、排序基础核心概念2.1 稳定排序概念待排序序列中值相等元素排序后相对先后顺序保持不变。稳定排序集合冒泡、插入、归并、基数排序2.2 不稳定排序概念等值元素排序后原有前后位置可能颠倒不稳定排序集合选择、快速、堆排序、希尔拓展业务场景要求保留原始同等数据顺序时必须选用稳定排序。三、快速排序1. 概念分治思想选取基准值pivot一轮遍历将序列划分为「小于基准」左区间、「大于基准」右区间再递归处理左右子区间直到区间长度为 1 天然有序。2. 特性平均时间复杂度 O (nlogn)最坏有序数组 O (n²)不稳定排序原地交换无需额外数组空间开销小基准一般选区间首元素也可随机基准优化最坏情况。3. 完整代码实现#include iostream using namespace std; ​ // 快速排序 左闭右闭区间 [l, r] void QuickSort(int arr[], int l, int r) { if (l r) return; // 区间仅一个元素终止递归 int pivot arr[l]; // 基准取最左侧元素 int i l, j r; while (i j) { // 右指针向左找小于基准的值 while (i j arr[j] pivot) j--; arr[i] arr[j]; // 左指针向右找大于基准的值 while (i j arr[i] pivot) i; arr[j] arr[i]; } arr[i] pivot; // 基准归位i为分割点 QuickSort(arr, l, i - 1); // 递归处理左区间 QuickSort(arr, i 1, r); // 递归处理右区间 } ​ int main() { int arr[] {3,9,4,7,12,5}; int len sizeof(arr)/sizeof(int); QuickSort(arr,0,len-1); for(int i0;ilen;i) cout arr[i] ; return 0; }拓展优化随机选取基准、三数取中法规避有序数组最坏时间复杂度。四、堆排序1. 概念基于完全二叉树堆实现排序分为大顶堆、小顶堆升序排序使用大顶堆堆顶为最大值每次交换堆顶与末尾元素再重新调整堆逐步完成有序序列。大顶堆规则任意父节点值 ≥ 左右子节点值2. 堆下标数学公式数组存储完全二叉树当前下标i左孩子2*i 1右孩子2*i 2父节点(i-1)/23. 特性时间复杂度稳定 O (nlogn)不稳定排序原地排序无额外数组开销适合海量数据 TOP-K 极值筛选。4. 完整代码#include iostream using namespace std; ​ // 调整以i为根的子树为大顶堆size为数组有效长度 void HeapAdjust(int arr[], int i, int size) { int temp arr[i]; // 保存根值 int left 2*i 1; while(left size) { int maxIdx left; int right left 1; // 找出左右子节点最大值下标 if(right size arr[right] arr[left]) maxIdx right; if(arr[maxIdx] temp) { arr[i] arr[maxIdx]; i maxIdx; left 2*i 1; } else break; } arr[i] temp; } ​ // 堆排序主函数 void HeapSort(int arr[], int len) { // 1. 初始化大顶堆从最后一个非叶子节点向前调整 for(int i (len-2)/2; i 0; i--) HeapAdjust(arr,i,len); // 2. 交换堆顶最大值到末尾逐步缩小区间 for(int i len-1; i 0; i--) { swap(arr[0], arr[i]); HeapAdjust(arr,0,i); } } ​ int main() { int arr[] {2,8,5,3,7,1}; int len sizeof(arr)/sizeof(int); HeapSort(arr, len); for(int x : arr) cout x ; return 0; }五、归并排序1. 概念分治递归思想先把长数组不断拆分为长度 1 的子数组天然有序再两两合并两个有序子数组逐层向上合并得到完整有序序列。2. 特性稳定排序时间复杂度稳定 O (nlogn)需要临时数组存储合并结果存在额外内存开销链表排序优先选用归并无数组拷贝开销。3. 完整代码#include iostream #include vector using namespace std; ​ // 合并两个有序区间 [l,mid] [mid1, r] void Merge(int arr[], int l, int mid, int r, int temp[]) { int i l, j mid1, k l; while(i mid j r) { if(arr[i] arr[j]) temp[k] arr[i]; else temp[k] arr[j]; } while(i mid) temp[k] arr[i]; while(j r) temp[k] arr[j]; // 临时数组拷贝回原数组 for(int pl;pr;p) arr[p] temp[p]; } ​ void MergeSort(int arr[], int l, int r, int temp[]) { if(l r) return; int mid (l r)/2; MergeSort(arr, l, mid, temp); // 拆分左半 MergeSort(arr, mid1, r, temp); // 拆分右半 Merge(arr, l, mid, r, temp); // 合并有序区间 } ​ // 封装入口 void MergeSortWrap(int arr[], int len) { int* temp new int[len]; MergeSort(arr, 0, len-1, temp); delete[] temp; } ​ int main() { int arr[] {9,2,7,4,1,6}; int len sizeof(arr)/sizeof(int); MergeSortWrap(arr, len); for(int x : arr) cout x ; return 0; }六、八大排序整体分类拓展1. 简单平方级排序 O (n²)冒泡排序、插入排序、选择排序稳定冒泡、插入不稳定选择2. 线性对数级 O (nlogn)快速排序、堆排序、归并排序稳定归并不稳定快排、堆排3. 线性特殊排序 O (n)数据有范围约束基数排序、计数排序稳定