前置说明分类简单排序冒泡、选择、插入进阶插入希尔排序分治排序快速、归并堆排序基于堆核心概念稳定排序相等元素相对顺序不变冒泡、插入、归并不稳定选择、希尔、快排、堆排1. 冒泡排序 BubbleSort原理相邻元素两两比较逆序则交换每一轮把最大值 “浮” 到末尾。优化标记本轮是否交换无交换直接退出有序提前终止。#include iostream #include vector using namespace std; void BubbleSort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { bool swapped false; // 每轮末尾i个已排好不用比较 for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j1]) { swap(arr[j], arr[j1]); swapped true; } } if (!swapped) break; // 全程无交换已有序 } } // 测试 int main() { vectorint a {3,1,4,1,5,9,2,6}; BubbleSort(a); for (int x : a) cout x ; return 0; }时间复杂度最好完全有序O(n)一次遍历无交换直接退出平均 / 最坏完全逆序O(n2)2. 选择排序 SelectSort原理分有序区、无序区每轮遍历无序区找到最小值和无序区首元素交换。void selectSort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { int mini; for (int j i; j n; j) { if (arr[j] arr[min]) { min j; } } swap(arr[min], arr[i]); }时间复杂度无论有序 / 无序最好 / 平均 / 最坏全是 O(n2)全程必须完整遍历找最小值。3. 插入排序 InsertSort原理左侧是有序数组依次取右侧元素向前插入到合适位置void insertSort(vectorint arr) { int n arr.size(); for (int i 1; i n; i) { int tmp arr[i]; int j; for (j i - 1; j 0; j--) { if (arr[j] tmp) { arr[j 1] arr[j]; } else break; } arr[j1] tmp; } }时间复杂度最好完全有序O(n)仅比较不移动平均 / 最坏逆序O(n2)。4. 希尔排序 ShellSort插入排序优化希尔排序是插入排序的优化版本。原理分组插入排序设置间隔 gap每组单独插入排序不断缩小 gap 至 1退化为普通插入。void shellSort(vectorint arr) { int n arr.size(); for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int tmp arr[i]; int j; for (j i - gap; j 0; j-gap) { if (arr[j] tmp) arr[j gap] arr[j]; else break; } arr[jgap] tmp; } } }时间复杂度最好O(n)平均O(n1.3)二分增量序列最坏O(n2)。5. 快速排序 QuickSort快排详解这里面讲解了快排的几种实现方法https://blog.csdn.net/w8848w/article/details/147365474?fromshareblogdetailsharetypeblogdetailsharerId147365474sharereferPCsharesourcew8848wsharefromfrom_link原理分治选基准 pivot分区小于 pivot 放左大于放右递归排序左右子区间挖坑法void QS(vectorint arr, int left, int right) { if (left right) return; int key arr[left]; int begin left, end right; while (left right) { while (left right arr[right]key) { right--; } arr[left] arr[right]; while (left right arr[left]key) { left; } arr[right] arr[left]; } arr[left] key; QS(arr,begin, left - 1); QS(arr, left 1, end); } void QuickSort(vectorint arr) { QS(arr, 0, arr.size() - 1); }时间复杂度最好 / 平均基准平分区间O(nlogn)最坏有序 / 逆序基准取端点O(n2)。随机基准优化int partition_rand(vectorint arr, int l, int r) { int randIdx l rand() % (r - l 1); swap(arr[randIdx], arr[r]); return partition(arr, l, r); }6. 归并排序 MergeSort稳定 O (nlogn)原理分治二分拆分数组直到单个元素有序合并两个子数组需要辅助数组C 完整代码void _MergeSort(vectorint arr,vectorint vec,int left,int right) { if (right left) return; int mid (left right) / 2; _MergeSort(arr, vec, left, mid); _MergeSort(arr, vec, mid 1, right); int begin1 left, end1 mid; int begin2 mid 1, end2 right; int ileft; //将两段有序序列归并成一段 while (begin1 end1 begin2 end2) { if (arr[begin1] arr[begin2]) vec[i] arr[begin1]; else vec[i] arr[begin2]; } //将剩下的数组添加到新数组尾部 while (begin1 end1) { vec[i] arr[begin1]; } while (begin2 end2) { vec[i] arr[begin2]; } //拷贝 for (int i left; i right; i) { arr[i] vec[i]; } } void MergeSort(vectorint arr) { int n arr.size(); vectorint vec(n); _MergeSort(arr,vec,0,n-1); }时间复杂度最好 / 平均 / 最坏稳定 O(nlogn)无退化风险。7. 堆排序 HeapSort原理数组模拟完全二叉树构建大顶堆堆顶为最大值交换到数组末尾缩小堆反复下沉调整堆。父 i → 左孩子2*i1右2*i2孩子 i → 父(i-1)/2C 代码// 下沉调整大顶堆 void heapify(vectorint arr, int n, int i) { int largest i; int left 2*i 1; int right 2*i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void HeapSort(vectorint arr) { int n arr.size(); // 1. 建大顶堆从最后一个父节点向前遍历 for (int i n/2 - 1; i 0; --i) heapify(arr, n, i); // 2. 堆顶放末尾调整堆 for (int i n - 1; i 0; --i) { swap(arr[0], arr[i]); heapify(arr, i, 0); } }时间复杂度最好 / 平均 / 最坏全部稳定 O(nlogn)。