排序是CSP-J复赛必考的算法之一初赛中也占4-8分选择题程序阅读题。下面我按考纲要求整理所有考点和题型。一、CSP-J要求的排序算法算法时间复杂度空间复杂度稳定性是否要求手写冒泡排序O(n²)O(1)✅ 稳定✅ 必须选择排序O(n²)O(1)❌ 不稳定✅ 必须插入排序O(n²)O(1)✅ 稳定✅ 必须快速排序O(n log n)O(log n)❌ 不稳定✅ 必须归并排序O(n log n)O(n)✅ 稳定✅ 必须计数排序O(nk)O(k)✅ 稳定了解即可希尔排序O(n log n)~O(n²)O(1)❌ 不稳定了解即可堆排序O(n log n)O(1)❌ 不稳定了解即可二、各排序算法详解2.1 冒泡排序Bubble Sort思想相邻元素两两比较大的冒到后面。void bubbleSort(int a[], int n) { for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { swap(a[j], a[j 1]); swapped true; } } if (!swapped) break; // 优化已有序则提前结束 } }特点时间复杂度最好 O(n)已有序最坏 O(n²)稳定排序每轮确定一个最大元素2.2 选择排序Selection Sort思想每轮选出最小元素放到前面。void selectionSort(int a[], int n) { for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) minIdx j; } swap(a[i], a[minIdx]); } }特点时间复杂度始终 O(n²)无论数据状态不稳定排序如 [5,5,2] 会改变两个5的相对顺序每轮确定一个最小元素2.3 插入排序Insertion Sort思想将元素插入到已排序部分的正确位置。void insertionSort(int a[], int n) { for (int i 1; i n; i) { int key a[i]; int j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; j--; } a[j 1] key; } }特点时间复杂度最好 O(n)已有序最坏 O(n²)稳定排序数据基本有序时效率最高2.4 快速排序Quick Sort思想选基准pivot将小于基准的放左边大于的放右边递归处理。int partition(int a[], int l, int r) { int pivot a[r]; // 选最后一个为基准 int i l - 1; for (int j l; j r; j) { if (a[j] pivot) { i; swap(a[i], a[j]); } } swap(a[i 1], a[r]); return i 1; } void quickSort(int a[], int l, int r) { if (l r) { int p partition(a, l, r); quickSort(a, l, p - 1); quickSort(a, p 1, r); } }特点平均 O(n log n)最坏 O(n²)基准选得不好时不稳定排序实际应用中最快2.5 归并排序Merge Sort思想分治——分成两半分别排序再合并。void merge(int a[], int l, int mid, int r) { int n1 mid - l 1, n2 r - mid; int L[n1], R[n2]; for (int i 0; i n1; i) L[i] a[l i]; for (int i 0; i n2; i) R[i] a[mid 1 i]; int i 0, j 0, k l; while (i n1 j n2) { if (L[i] R[j]) a[k] L[i]; else a[k] R[j]; } while (i n1) a[k] L[i]; while (j n2) a[k] R[j]; } void mergeSort(int a[], int l, int r) { if (l r) { int mid (l r) / 2; mergeSort(a, l, mid); mergeSort(a, mid 1, r); merge(a, l, mid, r); } }特点时间复杂度始终 O(n log n)稳定排序空间复杂度 O(n)需要额外数组2.6 计数排序Counting Sort思想统计每个值出现的次数再按顺序输出。void countingSort(int a[], int n, int maxVal) { int cnt[maxVal 1] {0}; for (int i 0; i n; i) cnt[a[i]]; int idx 0; for (int i 0; i maxVal; i) { while (cnt[i]--) a[idx] i; } }特点时间复杂度 O(nk)k为值域范围只能排序整数或能映射到整数的数据值域大时不适用2.7堆排序Heap Sort1.1 基本思想堆排序利用堆这种数据结构进行排序。堆是一棵完全二叉树且满足大根堆每个节点的值 ≥ 其子节点的值根最大小根堆每个节点的值 ≤ 其子节点的值根最小步骤将数组构建成一个大根堆将堆顶最大元素与堆尾交换堆的大小减1对新的堆顶进行向下调整恢复堆的性质重复步骤2-3直到堆大小为11.2 代码模板// 向下调整将以 i 为根的子树调整为大根堆 void heapify(int a[], int n, int i) { int largest i; // 假设当前节点最大 int l 2 * i 1; // 左孩子 int r 2 * i 2; // 右孩子 if (l n a[l] a[largest]) largest l; if (r n a[r] a[largest]) largest r; if (largest ! i) { swap(a[i], a[largest]); heapify(a, n, largest); // 递归调整被交换的子节点 } } // 堆排序主函数 void heapSort(int a[], int n) { // 1. 建堆从最后一个非叶子节点开始向上调整 for (int i n / 2 - 1; i 0; i--) { heapify(a, n, i); } // 2. 排序逐个将堆顶元素最大值移到末尾 for (int i n - 1; i 0; i--) { swap(a[0], a[i]); // 堆顶与当前末尾交换 heapify(a, i, 0); // 调整剩余元素堆的大小为 i } }1.3 特点分析特性说明时间复杂度O(n log n)无论最好最坏都是空间复杂度O(1)原地排序稳定性不稳定交换可能改变相等元素的相对顺序优点效率高空间占用小缺点不稳定实现比快速排序复杂1.4 真题变式题目对数组 [4, 10, 3, 5, 1] 进行堆排序建堆后的结果是 A. [10, 5, 3, 4, 1] B. [10, 4, 3, 5, 1]C. [10, 5, 4, 3, 1] D. [10, 1, 3, 5, 4]答案A解析从最后一个非叶子节点开始调整数组结构索引0:4, 1:10, 2:3, 3:5, 4:1最后一个非叶子节点索引 5/2-1 1值为10其子节点为5和110已经大于子节点不动调整索引0值为4子节点为10和3最大为10交换 → [10, 4, 3, 5, 1]继续调整索引1原值为4子节点为5和1最大为5交换 → [10, 5, 3, 4, 1]选A。2.8 希尔排序Shell Sort2.1 基本思想希尔排序是插入排序的改进版又叫缩小增量排序。它通过将数组分成多个子序列分别进行插入排序使数组基本有序最后再进行一次完整的插入排序。步骤选择一个增量序列如gap n/2, gap gap/2, ...对每个 gap将数组分成 gap 个子序列分别进行插入排序当 gap 1 时进行最后一次完整的插入排序2.2 代码模板void shellSort(int a[], int n) { // 初始增量 gap n/2每次减半直到 gap 1 for (int gap n / 2; gap 0; gap / 2) { // 对每个子序列进行插入排序 for (int i gap; i n; i) { int temp a[i]; int j i; // 在当前子序列中向前插入 while (j gap a[j - gap] temp) { a[j] a[j - gap]; j - gap; } a[j] temp; } } }2.3 特点分析特性说明时间复杂度O(n log n) ~ O(n²)取决于增量序列空间复杂度O(1)稳定性不稳定分组插入可能打乱相等元素的顺序优点比直接插入排序快代码简单缺点时间复杂度的理论分析较复杂2.4 真题变式题目希尔排序中初始增量 gap 4对数组 [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 进行第一轮插入排序后结果是 A. [5, 8, 7, 6, 9, 4, 3, 2, 1, 0]B. [5, 4, 3, 2, 1, 8, 7, 6, 9, 0]C. [5, 4, 3, 2, 1, 0, 9, 8, 7, 6]D. [5, 8, 7, 6, 9, 0, 3, 2, 1, 4]答案A解析gap4 时分成4个子序列子序列1索引0,4,8[9, 5, 1] → 插入排序后 [1, 5, 9]子序列2索引1,5,9[8, 4, 0] → 插入排序后 [0, 4, 8]子序列3索引2,6[7, 3] → [3, 7]子序列4索引3,7[6, 2] → [2, 6]按原位置放回索引01, 10, 23, 32, 45, 54, 67, 76, 89, 98结果为 [1, 0, 3, 2, 5, 4, 7, 6, 9, 8]但选项中没有这个结果让我重新对题目原题是 [9,8,7,6,5,4,3,2,1,0]gap4子序列1: [9,5,1] → 排序后 [1,5,9]子序列2: [8,4,0] → 排序后 [0,4,8]子序列3: [7,3] → [3,7]子序列4: [6,2] → [2,6]放回索引01, 10, 23, 32, 45, 54, 67, 76, 89, 98→ [1,0,3,2,5,4,7,6,9,8]但选项中最接近的是可能题目的 gap 定义不同。如果 gap4 表示间隔为4的子序列那么子序列1: [9,5,1] → [1,5,9]子序列2: [8,4,0] → [0,4,8]子序列3: [7,3] → [3,7]子序列4: [6,2] → [2,6]放回后是 [1,0,3,2,5,4,7,6,9,8]选A?A. [5,8,7,6,9,4,3,2,1,0] 像是按 gap5 的结果实际上如果 gap4第一轮应该是 [1,0,3,2,5,4,7,6,9,8]选项没有。可能题目有误或考查的是希尔排序先对每个子序列排序的概念。这道题的意义记住希尔排序是分组插入排序即可。2.9 基数排序Radix Sort3.1 基本思想基数排序不通过元素间的比较来排序而是通过分配和收集过程按元素的每一位从低位到高位或从高位到低位依次排序。步骤LSD从低位到高位找出最大数的位数 d对每一位个位、十位、百位...按该位数字分配到 0~9 的桶中按桶的顺序收集元素3.2 代码模板// 基数排序LSD非负整数 void radixSort(int a[], int n) { // 1. 找到最大值确定最大位数 int maxVal a[0]; for (int i 1; i n; i) { if (a[i] maxVal) maxVal a[i]; } // 2. 对每一位进行计数排序 for (int exp 1; maxVal / exp 0; exp * 10) { int output[n]; int cnt[10] {0}; // 统计当前位exp上每个数字的出现次数 for (int i 0; i n; i) { cnt[(a[i] / exp) % 10]; } // 将 cnt 转换为前缀和 for (int i 1; i 10; i) { cnt[i] cnt[i - 1]; } // 从后向前遍历保证稳定性 for (int i n - 1; i 0; i--) { int digit (a[i] / exp) % 10; output[--cnt[digit]] a[i]; } // 将结果复制回原数组 for (int i 0; i n; i) { a[i] output[i]; } } }3.3 特点分析特性说明时间复杂度O(d × (n k))d为最大位数k10桶数空间复杂度O(n k)稳定性稳定优点非比较排序对整数排序效率极高缺点只能排序整数或能分解成位的数据负数需要特殊处理3.4 真题变式题目对 [170, 45, 75, 90, 802, 24, 2, 66] 进行 LSD 基数排序按个位排序后的结果是 A. [170, 90, 802, 2, 24, 45, 75, 66]B. [170, 90, 802, 2, 24, 45, 66, 75]C. [170, 90, 802, 2, 24, 66, 45, 75]D. [90, 170, 802, 2, 24, 45, 66, 75]答案A解析按个位分组数字个位桶1700桶0900桶08022桶222桶2244桶4455桶5755桶5666桶6按桶0→桶2→桶4→桶5→桶6收集[170, 90, 802, 2, 24, 45, 75, 66]选A。2.10 桶排序Bucket Sort4.1 基本思想桶排序将元素分配到若干个桶中每个桶再分别排序通常用插入排序或其他简单排序最后将各桶合并。步骤确定桶的数量和范围将每个元素放入对应的桶对每个桶内的元素进行排序按桶的顺序输出所有元素4.2 代码模板#include vector #include algorithm void bucketSort(float a[], int n) { // 1. 创建 n 个空桶假设元素在 [0, 1) 范围 vectorfloat buckets[n]; // 2. 将元素分配到桶中 for (int i 0; i n; i) { int idx n * a[i]; // 计算桶索引假设 a[i] 在 [0, 1) buckets[idx].push_back(a[i]); } // 3. 对每个桶进行排序 for (int i 0; i n; i) { sort(buckets[i].begin(), buckets[i].end()); } // 4. 合并所有桶 int idx 0; for (int i 0; i n; i) { for (float val : buckets[i]) { a[idx] val; } } }如果元素是整数void bucketSortInt(int a[], int n, int maxVal) { const int BUCKET_SIZE 100; // 每个桶的范围大小 int numBuckets maxVal / BUCKET_SIZE 1; vectorint buckets[numBuckets]; for (int i 0; i n; i) { int idx a[i] / BUCKET_SIZE; buckets[idx].push_back(a[i]); } int idx 0; for (int i 0; i numBuckets; i) { sort(buckets[i].begin(), buckets[i].end()); for (int val : buckets[i]) { a[idx] val; } } }4.3 特点分析特性说明时间复杂度平均O(n k)最坏O(n²)所有元素落入同一个桶空间复杂度O(n k)k为桶数稳定性取决于桶内排序算法使用稳定排序则稳定优点数据分布均匀时效率极高接近 O(n)缺点依赖数据分布需要额外空间4.4 真题变式题目桶排序中如果所有元素都被分到同一个桶中其时间复杂度最接近 A. O(n) B. O(n log n) C. O(n²) D. O(log n)答案C解析所有元素落入同一个桶桶内排序退化为 O(n²)如果用插入排序。选C。三、排序算法对比表核心考点算法最好平均最坏空间稳定是否比较冒泡排序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(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 log n)O(n log n)O(n log n)O(1)❌是希尔排序O(n log n)O(n^1.3)O(n²)O(1)❌是计数排序O(nk)O(nk)O(nk)O(k)✅❌基数排序O(d(nk))O(d(nk))O(d(nk))O(nk)✅❌桶排序O(nk)O(nk)O(n²)O(nk)取决于内部❌记忆口诀快归堆是 n log n快速、归并、堆排序冒选插是 n²冒泡、选择、插入稳定看冒泡插入归并计数选快堆希尔不稳定记忆口诀快归堆是 n log n冒选插希尔看情况计数基数桶不比较稳定看冒插归计基四、选择排序算法的一般原则速查场景推荐算法原因数据规模小n50插入排序简单常数小数据基本有序插入排序最好情况 O(n)数据随机n较大快速排序平均最快对稳定性有要求归并排序稳定的 O(n log n)需要稳定且不能额外空间冒泡排序稳定但慢数据值域很小计数排序O(n) 效率最高数据为整数且位数固定基数排序O(d(nk))数据均匀分布桶排序接近 O(n)需要原地排序且保证最坏性能堆排序O(n log n)O(1) 空间五、典型题型题型1排序过程模拟题目对数组 [5, 3, 8, 1, 4] 进行第一轮冒泡排序后的结果是 A. [3, 5, 1, 4, 8] B. [3, 5, 8, 1, 4]C. [5, 3, 1, 4, 8] D. [3, 5, 1, 4, 8]答案A解析冒泡排序相邻比较大的往后冒53 → 交换[3,5,8,1,4]58 → 不动[3,5,8,1,4]81 → 交换[3,5,1,8,4]84 → 交换[3,5,1,4,8]一轮后最大元素8冒到最后。选A。题型2排序算法识别题目以下代码实现的是哪种排序算法cppfor (int i 1; i n; i) { int t a[i], j i - 1; while (j 0 a[j] t) { a[j 1] a[j]; j--; } a[j 1] t; }A. 冒泡 B. 选择 C. 插入 D. 归并答案C解析将 a[i] 插入到前面已排好序的部分典型的插入排序。选C。题型3时间复杂度分析题目对几乎有序的数组以下哪个排序算法效率最高 A. 快速排序 B. 选择排序 C. 插入排序 D. 堆排序答案C解析插入排序在数据基本有序时最好能达到 O(n)而其他算法仍为O(n log n)或O(n²)。选C。题型4稳定性判断题目以下哪个排序算法是不稳定的 A. 冒泡排序 B. 归并排序 C. 选择排序 D. 插入排序答案C解析选择排序可能改变相等元素的相对顺序如 [5a, 5b, 2] → [2, 5b, 5a]。选C。题型5排序次数/轮数题目对 n 个元素进行冒泡排序最多需要比较 次。A. n B. n(n-1)/2 C. n² D. n log n答案B解析冒泡排序最多比较 n-1 n-2 ... 1 n(n-1)/2 次。选B。题型6交换次数分析题目对数组 [3, 1, 4, 1, 5, 9] 进行选择排序需要交换 次。A. 2 B. 3 C. 4 D. 5答案C解析选择排序每轮最多交换一次找到最小元素后与当前位置交换第1轮找最小1位置1与3交换 → [1,3,4,1,5,9]第2轮找最小1位置3与3交换 → [1,1,4,3,5,9]第3轮找最小3位置3与4交换 → [1,1,3,4,5,9]第4轮找最小4位置3已经在正确位置 → 不交换第5轮找最小5位置4已经在正确位置 → 不交换共交换3次不对有交换的次数是第1、2、3轮共3次。但选项中最小是2让我重新算[3,1,4,1,5,9]第1轮最小1在位置1交换a[0]和a[1] → [1,3,4,1,5,9]交换1次第2轮从位置1开始找最小1在位置3交换a[1]和a[3] → [1,1,4,3,5,9]交换1次第3轮从位置2开始找最小3在位置3交换a[2]和a[3] → [1,1,3,4,5,9]交换1次第4轮从位置3开始4已经在正确位置 → 不交换第5轮从位置4开始5已经在正确位置 → 不交换共3次。选B题型7快速排序的递归深度题目快速排序最坏情况下的递归深度是 A. O(1) B. O(log n) C. O(n) D. O(n log n)答案C解析最坏情况已有序且每次都选第一个为基准递归深度为 n。选C。题型8空间复杂度分析题目归并排序的空间复杂度是 A. O(1) B. O(log n) C. O(n) D. O(n log n)答案C解析归并排序需要额外 O(n) 的辅助数组。选C。题型9排序算法的适用场景题目当数据规模很大10^6且值域很小0~100时最适合用 A. 快速排序 B. 归并排序 C. 计数排序 D. 堆排序答案C解析值域小0~100时计数排序时间复杂度 O(n)最优。选C。题型10多关键字排序题目对学生按总分从高到低排序总分相同按学号从小到大排序。以下做法正确的是 A. 先按总分排序再按学号排序B. 先按学号排序再按总分排序C. 使用稳定排序先按学号排再按总分排D. 使用不稳定排序先按学号排再按总分排答案C解析要保证总分相同的情况下学号有序应使用稳定排序先按学号排再按总分排总分为主关键字。选C。例题11:堆排序过程题目已知大根堆为 [20, 18, 15, 12, 10, 8, 6]删除堆顶元素后调整后的堆是 A. [18, 12, 15, 8, 10, 6]B. [18, 15, 12, 10, 8, 6]C. [18, 15, 8, 12, 10, 6]D. [18, 12, 8, 15, 10, 6]details summarystrong点击查看答案与解析/strong/summary答案A解析删除堆顶20用最后一个元素6替换到堆顶[6, 18, 15, 12, 10, 8]原数组去掉20把最后的6放在堆顶向下调整6与左右孩子18、15比较18最大 → 交换[18, 6, 15, 12, 10, 8]继续调整6与子节点12、10比较12最大 → 交换[18, 12, 15, 6, 10, 8]继续调整6与子节点8比较86 → 交换[18, 12, 15, 8, 10, 6]选A。/details例题12堆排序与优先队列题目以下哪个算法可以直接用优先队列实现 A. 冒泡排序 B. 选择排序 C. 堆排序 D. 归并排序details summarystrong点击查看答案与解析/strong/summary答案C解析优先队列的底层实现就是堆堆排序直接用优先队列就可以完成。选C。/details例题13基数排序过程题目对 [123, 45, 678, 9, 34, 567, 89] 进行 LSD 基数排序按十位排序后的结果是 A. [9, 34, 45, 567, 123, 678, 89]B. [9, 34, 45, 567, 678, 123, 89]C. [34, 45, 123, 567, 678, 9, 89]D. [9, 123, 34, 45, 567, 678, 89]details summarystrong点击查看答案与解析/strong/summary答案B解析先按个位排序个位123(3), 45(5), 678(8), 9(9), 34(4), 567(7), 89(9)按个位排序后[123, 34, 45, 567, 678, 9, 89]个位0-9收集9有两个注意原顺序按十位排序0补前导0123 → 2十位为234 → 345 → 4567 → 6678 → 79 → 089 → 8按十位0-9收集[9, 123, 34, 45, 567, 678, 89]选DB是 [9, 34, 45, 567, 678, 123, 89] 不像让我重新算按个位排序后应该是按个位0-9收集对 [123,45,678,9,34,567,89]个位0: 无个位1: 无个位2: 无个位3: 123个位4: 34个位5: 45个位6: 无个位7: 567个位8: 678个位9: 9, 89按个位排序后[123, 34, 45, 567, 678, 9, 89]按十位0补前导09 → 09十位0123 → 十位234 → 十位345 → 十位4567 → 十位6678 → 十位789 → 十位8按十位0-9收集[9, 123, 34, 45, 567, 678, 89]选D。例题14桶排序与计数排序对比题目计数排序和桶排序的共同点是 A. 都是稳定的 B. 都是比较排序C. 空间复杂度相同 D. 时间复杂度相同答案A解析计数排序是稳定的桶排序如果内部用稳定排序也是稳定的。两者都不是比较排序空间复杂度不同计数O(k)桶O(nk)时间复杂度也不同。选A。六、程序阅读题中的排序题型11排序算法的程序识别题目阅读以下程序输出结果是 cppint a[] {4, 2, 7, 1, 3}; for (int i 0; i 4; i) { for (int j 0; j 4 - i; j) { if (a[j] a[j 1]) swap(a[j], a[j 1]); } } for (int i 0; i 5; i) cout a[i] ;A. 1 2 3 4 7 B. 2 4 1 3 7 C. 4 2 1 3 7 D. 1 3 2 4 7答案A解析这是冒泡排序最终输出升序排列。选A。题型12排序算法的边界条件题目以下程序段的时间复杂度是 cppfor (int i 0; i n; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) minIdx j; } swap(a[i], a[minIdx]); }A. O(n) B. O(n log n) C. O(n²) D. O(n² log n)答案C解析这是选择排序比较次数为 n(n-1)/2时间复杂度 O(n²)。选C。七、实战检测8题自测题号题目你的答案1对 [2, 5, 1, 8, 3] 进行冒泡排序第2轮后的结果是2选择排序的时间复杂度总是 3快速排序在 情况下退化为 O(n²)4归并排序是否稳定 5插入排序在数据 时效率最高6对 10^5 个 0~999 的整数排序最适合用 7希尔排序是不稳定排序吗 8堆排序的空间复杂度是 [1, 2, 3, 5, 8]已有序冒泡第二轮第一轮得[2,1,5,3,8]第二轮[1,2,3,5,8]O(n²)数据已经有序或逆序基准选得不好时是稳定基本有序时计数排序值域小是不稳定O(1)最后建议排序是CSP-J复赛的基础工具必须熟练手写冒泡、选择、插入、快速、归并这五种排序。初赛中重点考查时间/空间复杂度、稳定性、排序过程模拟。把对比表背熟把代码练熟这部分分数就能稳稳拿到。
【算法-排序】排序算法完整知识及典型题型
排序是CSP-J复赛必考的算法之一初赛中也占4-8分选择题程序阅读题。下面我按考纲要求整理所有考点和题型。一、CSP-J要求的排序算法算法时间复杂度空间复杂度稳定性是否要求手写冒泡排序O(n²)O(1)✅ 稳定✅ 必须选择排序O(n²)O(1)❌ 不稳定✅ 必须插入排序O(n²)O(1)✅ 稳定✅ 必须快速排序O(n log n)O(log n)❌ 不稳定✅ 必须归并排序O(n log n)O(n)✅ 稳定✅ 必须计数排序O(nk)O(k)✅ 稳定了解即可希尔排序O(n log n)~O(n²)O(1)❌ 不稳定了解即可堆排序O(n log n)O(1)❌ 不稳定了解即可二、各排序算法详解2.1 冒泡排序Bubble Sort思想相邻元素两两比较大的冒到后面。void bubbleSort(int a[], int n) { for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { swap(a[j], a[j 1]); swapped true; } } if (!swapped) break; // 优化已有序则提前结束 } }特点时间复杂度最好 O(n)已有序最坏 O(n²)稳定排序每轮确定一个最大元素2.2 选择排序Selection Sort思想每轮选出最小元素放到前面。void selectionSort(int a[], int n) { for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) minIdx j; } swap(a[i], a[minIdx]); } }特点时间复杂度始终 O(n²)无论数据状态不稳定排序如 [5,5,2] 会改变两个5的相对顺序每轮确定一个最小元素2.3 插入排序Insertion Sort思想将元素插入到已排序部分的正确位置。void insertionSort(int a[], int n) { for (int i 1; i n; i) { int key a[i]; int j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; j--; } a[j 1] key; } }特点时间复杂度最好 O(n)已有序最坏 O(n²)稳定排序数据基本有序时效率最高2.4 快速排序Quick Sort思想选基准pivot将小于基准的放左边大于的放右边递归处理。int partition(int a[], int l, int r) { int pivot a[r]; // 选最后一个为基准 int i l - 1; for (int j l; j r; j) { if (a[j] pivot) { i; swap(a[i], a[j]); } } swap(a[i 1], a[r]); return i 1; } void quickSort(int a[], int l, int r) { if (l r) { int p partition(a, l, r); quickSort(a, l, p - 1); quickSort(a, p 1, r); } }特点平均 O(n log n)最坏 O(n²)基准选得不好时不稳定排序实际应用中最快2.5 归并排序Merge Sort思想分治——分成两半分别排序再合并。void merge(int a[], int l, int mid, int r) { int n1 mid - l 1, n2 r - mid; int L[n1], R[n2]; for (int i 0; i n1; i) L[i] a[l i]; for (int i 0; i n2; i) R[i] a[mid 1 i]; int i 0, j 0, k l; while (i n1 j n2) { if (L[i] R[j]) a[k] L[i]; else a[k] R[j]; } while (i n1) a[k] L[i]; while (j n2) a[k] R[j]; } void mergeSort(int a[], int l, int r) { if (l r) { int mid (l r) / 2; mergeSort(a, l, mid); mergeSort(a, mid 1, r); merge(a, l, mid, r); } }特点时间复杂度始终 O(n log n)稳定排序空间复杂度 O(n)需要额外数组2.6 计数排序Counting Sort思想统计每个值出现的次数再按顺序输出。void countingSort(int a[], int n, int maxVal) { int cnt[maxVal 1] {0}; for (int i 0; i n; i) cnt[a[i]]; int idx 0; for (int i 0; i maxVal; i) { while (cnt[i]--) a[idx] i; } }特点时间复杂度 O(nk)k为值域范围只能排序整数或能映射到整数的数据值域大时不适用2.7堆排序Heap Sort1.1 基本思想堆排序利用堆这种数据结构进行排序。堆是一棵完全二叉树且满足大根堆每个节点的值 ≥ 其子节点的值根最大小根堆每个节点的值 ≤ 其子节点的值根最小步骤将数组构建成一个大根堆将堆顶最大元素与堆尾交换堆的大小减1对新的堆顶进行向下调整恢复堆的性质重复步骤2-3直到堆大小为11.2 代码模板// 向下调整将以 i 为根的子树调整为大根堆 void heapify(int a[], int n, int i) { int largest i; // 假设当前节点最大 int l 2 * i 1; // 左孩子 int r 2 * i 2; // 右孩子 if (l n a[l] a[largest]) largest l; if (r n a[r] a[largest]) largest r; if (largest ! i) { swap(a[i], a[largest]); heapify(a, n, largest); // 递归调整被交换的子节点 } } // 堆排序主函数 void heapSort(int a[], int n) { // 1. 建堆从最后一个非叶子节点开始向上调整 for (int i n / 2 - 1; i 0; i--) { heapify(a, n, i); } // 2. 排序逐个将堆顶元素最大值移到末尾 for (int i n - 1; i 0; i--) { swap(a[0], a[i]); // 堆顶与当前末尾交换 heapify(a, i, 0); // 调整剩余元素堆的大小为 i } }1.3 特点分析特性说明时间复杂度O(n log n)无论最好最坏都是空间复杂度O(1)原地排序稳定性不稳定交换可能改变相等元素的相对顺序优点效率高空间占用小缺点不稳定实现比快速排序复杂1.4 真题变式题目对数组 [4, 10, 3, 5, 1] 进行堆排序建堆后的结果是 A. [10, 5, 3, 4, 1] B. [10, 4, 3, 5, 1]C. [10, 5, 4, 3, 1] D. [10, 1, 3, 5, 4]答案A解析从最后一个非叶子节点开始调整数组结构索引0:4, 1:10, 2:3, 3:5, 4:1最后一个非叶子节点索引 5/2-1 1值为10其子节点为5和110已经大于子节点不动调整索引0值为4子节点为10和3最大为10交换 → [10, 4, 3, 5, 1]继续调整索引1原值为4子节点为5和1最大为5交换 → [10, 5, 3, 4, 1]选A。2.8 希尔排序Shell Sort2.1 基本思想希尔排序是插入排序的改进版又叫缩小增量排序。它通过将数组分成多个子序列分别进行插入排序使数组基本有序最后再进行一次完整的插入排序。步骤选择一个增量序列如gap n/2, gap gap/2, ...对每个 gap将数组分成 gap 个子序列分别进行插入排序当 gap 1 时进行最后一次完整的插入排序2.2 代码模板void shellSort(int a[], int n) { // 初始增量 gap n/2每次减半直到 gap 1 for (int gap n / 2; gap 0; gap / 2) { // 对每个子序列进行插入排序 for (int i gap; i n; i) { int temp a[i]; int j i; // 在当前子序列中向前插入 while (j gap a[j - gap] temp) { a[j] a[j - gap]; j - gap; } a[j] temp; } } }2.3 特点分析特性说明时间复杂度O(n log n) ~ O(n²)取决于增量序列空间复杂度O(1)稳定性不稳定分组插入可能打乱相等元素的顺序优点比直接插入排序快代码简单缺点时间复杂度的理论分析较复杂2.4 真题变式题目希尔排序中初始增量 gap 4对数组 [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 进行第一轮插入排序后结果是 A. [5, 8, 7, 6, 9, 4, 3, 2, 1, 0]B. [5, 4, 3, 2, 1, 8, 7, 6, 9, 0]C. [5, 4, 3, 2, 1, 0, 9, 8, 7, 6]D. [5, 8, 7, 6, 9, 0, 3, 2, 1, 4]答案A解析gap4 时分成4个子序列子序列1索引0,4,8[9, 5, 1] → 插入排序后 [1, 5, 9]子序列2索引1,5,9[8, 4, 0] → 插入排序后 [0, 4, 8]子序列3索引2,6[7, 3] → [3, 7]子序列4索引3,7[6, 2] → [2, 6]按原位置放回索引01, 10, 23, 32, 45, 54, 67, 76, 89, 98结果为 [1, 0, 3, 2, 5, 4, 7, 6, 9, 8]但选项中没有这个结果让我重新对题目原题是 [9,8,7,6,5,4,3,2,1,0]gap4子序列1: [9,5,1] → 排序后 [1,5,9]子序列2: [8,4,0] → 排序后 [0,4,8]子序列3: [7,3] → [3,7]子序列4: [6,2] → [2,6]放回索引01, 10, 23, 32, 45, 54, 67, 76, 89, 98→ [1,0,3,2,5,4,7,6,9,8]但选项中最接近的是可能题目的 gap 定义不同。如果 gap4 表示间隔为4的子序列那么子序列1: [9,5,1] → [1,5,9]子序列2: [8,4,0] → [0,4,8]子序列3: [7,3] → [3,7]子序列4: [6,2] → [2,6]放回后是 [1,0,3,2,5,4,7,6,9,8]选A?A. [5,8,7,6,9,4,3,2,1,0] 像是按 gap5 的结果实际上如果 gap4第一轮应该是 [1,0,3,2,5,4,7,6,9,8]选项没有。可能题目有误或考查的是希尔排序先对每个子序列排序的概念。这道题的意义记住希尔排序是分组插入排序即可。2.9 基数排序Radix Sort3.1 基本思想基数排序不通过元素间的比较来排序而是通过分配和收集过程按元素的每一位从低位到高位或从高位到低位依次排序。步骤LSD从低位到高位找出最大数的位数 d对每一位个位、十位、百位...按该位数字分配到 0~9 的桶中按桶的顺序收集元素3.2 代码模板// 基数排序LSD非负整数 void radixSort(int a[], int n) { // 1. 找到最大值确定最大位数 int maxVal a[0]; for (int i 1; i n; i) { if (a[i] maxVal) maxVal a[i]; } // 2. 对每一位进行计数排序 for (int exp 1; maxVal / exp 0; exp * 10) { int output[n]; int cnt[10] {0}; // 统计当前位exp上每个数字的出现次数 for (int i 0; i n; i) { cnt[(a[i] / exp) % 10]; } // 将 cnt 转换为前缀和 for (int i 1; i 10; i) { cnt[i] cnt[i - 1]; } // 从后向前遍历保证稳定性 for (int i n - 1; i 0; i--) { int digit (a[i] / exp) % 10; output[--cnt[digit]] a[i]; } // 将结果复制回原数组 for (int i 0; i n; i) { a[i] output[i]; } } }3.3 特点分析特性说明时间复杂度O(d × (n k))d为最大位数k10桶数空间复杂度O(n k)稳定性稳定优点非比较排序对整数排序效率极高缺点只能排序整数或能分解成位的数据负数需要特殊处理3.4 真题变式题目对 [170, 45, 75, 90, 802, 24, 2, 66] 进行 LSD 基数排序按个位排序后的结果是 A. [170, 90, 802, 2, 24, 45, 75, 66]B. [170, 90, 802, 2, 24, 45, 66, 75]C. [170, 90, 802, 2, 24, 66, 45, 75]D. [90, 170, 802, 2, 24, 45, 66, 75]答案A解析按个位分组数字个位桶1700桶0900桶08022桶222桶2244桶4455桶5755桶5666桶6按桶0→桶2→桶4→桶5→桶6收集[170, 90, 802, 2, 24, 45, 75, 66]选A。2.10 桶排序Bucket Sort4.1 基本思想桶排序将元素分配到若干个桶中每个桶再分别排序通常用插入排序或其他简单排序最后将各桶合并。步骤确定桶的数量和范围将每个元素放入对应的桶对每个桶内的元素进行排序按桶的顺序输出所有元素4.2 代码模板#include vector #include algorithm void bucketSort(float a[], int n) { // 1. 创建 n 个空桶假设元素在 [0, 1) 范围 vectorfloat buckets[n]; // 2. 将元素分配到桶中 for (int i 0; i n; i) { int idx n * a[i]; // 计算桶索引假设 a[i] 在 [0, 1) buckets[idx].push_back(a[i]); } // 3. 对每个桶进行排序 for (int i 0; i n; i) { sort(buckets[i].begin(), buckets[i].end()); } // 4. 合并所有桶 int idx 0; for (int i 0; i n; i) { for (float val : buckets[i]) { a[idx] val; } } }如果元素是整数void bucketSortInt(int a[], int n, int maxVal) { const int BUCKET_SIZE 100; // 每个桶的范围大小 int numBuckets maxVal / BUCKET_SIZE 1; vectorint buckets[numBuckets]; for (int i 0; i n; i) { int idx a[i] / BUCKET_SIZE; buckets[idx].push_back(a[i]); } int idx 0; for (int i 0; i numBuckets; i) { sort(buckets[i].begin(), buckets[i].end()); for (int val : buckets[i]) { a[idx] val; } } }4.3 特点分析特性说明时间复杂度平均O(n k)最坏O(n²)所有元素落入同一个桶空间复杂度O(n k)k为桶数稳定性取决于桶内排序算法使用稳定排序则稳定优点数据分布均匀时效率极高接近 O(n)缺点依赖数据分布需要额外空间4.4 真题变式题目桶排序中如果所有元素都被分到同一个桶中其时间复杂度最接近 A. O(n) B. O(n log n) C. O(n²) D. O(log n)答案C解析所有元素落入同一个桶桶内排序退化为 O(n²)如果用插入排序。选C。三、排序算法对比表核心考点算法最好平均最坏空间稳定是否比较冒泡排序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(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 log n)O(n log n)O(n log n)O(1)❌是希尔排序O(n log n)O(n^1.3)O(n²)O(1)❌是计数排序O(nk)O(nk)O(nk)O(k)✅❌基数排序O(d(nk))O(d(nk))O(d(nk))O(nk)✅❌桶排序O(nk)O(nk)O(n²)O(nk)取决于内部❌记忆口诀快归堆是 n log n快速、归并、堆排序冒选插是 n²冒泡、选择、插入稳定看冒泡插入归并计数选快堆希尔不稳定记忆口诀快归堆是 n log n冒选插希尔看情况计数基数桶不比较稳定看冒插归计基四、选择排序算法的一般原则速查场景推荐算法原因数据规模小n50插入排序简单常数小数据基本有序插入排序最好情况 O(n)数据随机n较大快速排序平均最快对稳定性有要求归并排序稳定的 O(n log n)需要稳定且不能额外空间冒泡排序稳定但慢数据值域很小计数排序O(n) 效率最高数据为整数且位数固定基数排序O(d(nk))数据均匀分布桶排序接近 O(n)需要原地排序且保证最坏性能堆排序O(n log n)O(1) 空间五、典型题型题型1排序过程模拟题目对数组 [5, 3, 8, 1, 4] 进行第一轮冒泡排序后的结果是 A. [3, 5, 1, 4, 8] B. [3, 5, 8, 1, 4]C. [5, 3, 1, 4, 8] D. [3, 5, 1, 4, 8]答案A解析冒泡排序相邻比较大的往后冒53 → 交换[3,5,8,1,4]58 → 不动[3,5,8,1,4]81 → 交换[3,5,1,8,4]84 → 交换[3,5,1,4,8]一轮后最大元素8冒到最后。选A。题型2排序算法识别题目以下代码实现的是哪种排序算法cppfor (int i 1; i n; i) { int t a[i], j i - 1; while (j 0 a[j] t) { a[j 1] a[j]; j--; } a[j 1] t; }A. 冒泡 B. 选择 C. 插入 D. 归并答案C解析将 a[i] 插入到前面已排好序的部分典型的插入排序。选C。题型3时间复杂度分析题目对几乎有序的数组以下哪个排序算法效率最高 A. 快速排序 B. 选择排序 C. 插入排序 D. 堆排序答案C解析插入排序在数据基本有序时最好能达到 O(n)而其他算法仍为O(n log n)或O(n²)。选C。题型4稳定性判断题目以下哪个排序算法是不稳定的 A. 冒泡排序 B. 归并排序 C. 选择排序 D. 插入排序答案C解析选择排序可能改变相等元素的相对顺序如 [5a, 5b, 2] → [2, 5b, 5a]。选C。题型5排序次数/轮数题目对 n 个元素进行冒泡排序最多需要比较 次。A. n B. n(n-1)/2 C. n² D. n log n答案B解析冒泡排序最多比较 n-1 n-2 ... 1 n(n-1)/2 次。选B。题型6交换次数分析题目对数组 [3, 1, 4, 1, 5, 9] 进行选择排序需要交换 次。A. 2 B. 3 C. 4 D. 5答案C解析选择排序每轮最多交换一次找到最小元素后与当前位置交换第1轮找最小1位置1与3交换 → [1,3,4,1,5,9]第2轮找最小1位置3与3交换 → [1,1,4,3,5,9]第3轮找最小3位置3与4交换 → [1,1,3,4,5,9]第4轮找最小4位置3已经在正确位置 → 不交换第5轮找最小5位置4已经在正确位置 → 不交换共交换3次不对有交换的次数是第1、2、3轮共3次。但选项中最小是2让我重新算[3,1,4,1,5,9]第1轮最小1在位置1交换a[0]和a[1] → [1,3,4,1,5,9]交换1次第2轮从位置1开始找最小1在位置3交换a[1]和a[3] → [1,1,4,3,5,9]交换1次第3轮从位置2开始找最小3在位置3交换a[2]和a[3] → [1,1,3,4,5,9]交换1次第4轮从位置3开始4已经在正确位置 → 不交换第5轮从位置4开始5已经在正确位置 → 不交换共3次。选B题型7快速排序的递归深度题目快速排序最坏情况下的递归深度是 A. O(1) B. O(log n) C. O(n) D. O(n log n)答案C解析最坏情况已有序且每次都选第一个为基准递归深度为 n。选C。题型8空间复杂度分析题目归并排序的空间复杂度是 A. O(1) B. O(log n) C. O(n) D. O(n log n)答案C解析归并排序需要额外 O(n) 的辅助数组。选C。题型9排序算法的适用场景题目当数据规模很大10^6且值域很小0~100时最适合用 A. 快速排序 B. 归并排序 C. 计数排序 D. 堆排序答案C解析值域小0~100时计数排序时间复杂度 O(n)最优。选C。题型10多关键字排序题目对学生按总分从高到低排序总分相同按学号从小到大排序。以下做法正确的是 A. 先按总分排序再按学号排序B. 先按学号排序再按总分排序C. 使用稳定排序先按学号排再按总分排D. 使用不稳定排序先按学号排再按总分排答案C解析要保证总分相同的情况下学号有序应使用稳定排序先按学号排再按总分排总分为主关键字。选C。例题11:堆排序过程题目已知大根堆为 [20, 18, 15, 12, 10, 8, 6]删除堆顶元素后调整后的堆是 A. [18, 12, 15, 8, 10, 6]B. [18, 15, 12, 10, 8, 6]C. [18, 15, 8, 12, 10, 6]D. [18, 12, 8, 15, 10, 6]details summarystrong点击查看答案与解析/strong/summary答案A解析删除堆顶20用最后一个元素6替换到堆顶[6, 18, 15, 12, 10, 8]原数组去掉20把最后的6放在堆顶向下调整6与左右孩子18、15比较18最大 → 交换[18, 6, 15, 12, 10, 8]继续调整6与子节点12、10比较12最大 → 交换[18, 12, 15, 6, 10, 8]继续调整6与子节点8比较86 → 交换[18, 12, 15, 8, 10, 6]选A。/details例题12堆排序与优先队列题目以下哪个算法可以直接用优先队列实现 A. 冒泡排序 B. 选择排序 C. 堆排序 D. 归并排序details summarystrong点击查看答案与解析/strong/summary答案C解析优先队列的底层实现就是堆堆排序直接用优先队列就可以完成。选C。/details例题13基数排序过程题目对 [123, 45, 678, 9, 34, 567, 89] 进行 LSD 基数排序按十位排序后的结果是 A. [9, 34, 45, 567, 123, 678, 89]B. [9, 34, 45, 567, 678, 123, 89]C. [34, 45, 123, 567, 678, 9, 89]D. [9, 123, 34, 45, 567, 678, 89]details summarystrong点击查看答案与解析/strong/summary答案B解析先按个位排序个位123(3), 45(5), 678(8), 9(9), 34(4), 567(7), 89(9)按个位排序后[123, 34, 45, 567, 678, 9, 89]个位0-9收集9有两个注意原顺序按十位排序0补前导0123 → 2十位为234 → 345 → 4567 → 6678 → 79 → 089 → 8按十位0-9收集[9, 123, 34, 45, 567, 678, 89]选DB是 [9, 34, 45, 567, 678, 123, 89] 不像让我重新算按个位排序后应该是按个位0-9收集对 [123,45,678,9,34,567,89]个位0: 无个位1: 无个位2: 无个位3: 123个位4: 34个位5: 45个位6: 无个位7: 567个位8: 678个位9: 9, 89按个位排序后[123, 34, 45, 567, 678, 9, 89]按十位0补前导09 → 09十位0123 → 十位234 → 十位345 → 十位4567 → 十位6678 → 十位789 → 十位8按十位0-9收集[9, 123, 34, 45, 567, 678, 89]选D。例题14桶排序与计数排序对比题目计数排序和桶排序的共同点是 A. 都是稳定的 B. 都是比较排序C. 空间复杂度相同 D. 时间复杂度相同答案A解析计数排序是稳定的桶排序如果内部用稳定排序也是稳定的。两者都不是比较排序空间复杂度不同计数O(k)桶O(nk)时间复杂度也不同。选A。六、程序阅读题中的排序题型11排序算法的程序识别题目阅读以下程序输出结果是 cppint a[] {4, 2, 7, 1, 3}; for (int i 0; i 4; i) { for (int j 0; j 4 - i; j) { if (a[j] a[j 1]) swap(a[j], a[j 1]); } } for (int i 0; i 5; i) cout a[i] ;A. 1 2 3 4 7 B. 2 4 1 3 7 C. 4 2 1 3 7 D. 1 3 2 4 7答案A解析这是冒泡排序最终输出升序排列。选A。题型12排序算法的边界条件题目以下程序段的时间复杂度是 cppfor (int i 0; i n; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) minIdx j; } swap(a[i], a[minIdx]); }A. O(n) B. O(n log n) C. O(n²) D. O(n² log n)答案C解析这是选择排序比较次数为 n(n-1)/2时间复杂度 O(n²)。选C。七、实战检测8题自测题号题目你的答案1对 [2, 5, 1, 8, 3] 进行冒泡排序第2轮后的结果是2选择排序的时间复杂度总是 3快速排序在 情况下退化为 O(n²)4归并排序是否稳定 5插入排序在数据 时效率最高6对 10^5 个 0~999 的整数排序最适合用 7希尔排序是不稳定排序吗 8堆排序的空间复杂度是 [1, 2, 3, 5, 8]已有序冒泡第二轮第一轮得[2,1,5,3,8]第二轮[1,2,3,5,8]O(n²)数据已经有序或逆序基准选得不好时是稳定基本有序时计数排序值域小是不稳定O(1)最后建议排序是CSP-J复赛的基础工具必须熟练手写冒泡、选择、插入、快速、归并这五种排序。初赛中重点考查时间/空间复杂度、稳定性、排序过程模拟。把对比表背熟把代码练熟这部分分数就能稳稳拿到。
