以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。
B：简单选择排序是稳定的——错误。选择排序每趟将最小元素与未排序区首位交换，交换跨元素，相等元素相对顺序可能改变，不稳定。
某同学用冒泡排序对数组 {} 进行升序排序，请问需要进行多少次元素交换？（ ）
B：6 次。n 个元素冒泡 n-1 趟，每趟比较次数递减；最坏 1+2+...+(n-1)=n(n-1)/2，对 n=4 共 6 次。
冒泡排序算法的伪代码如下：
输入：数组 ，。输出：按非递减顺序排序的 。
算法 BubbleSort：
1 FLAG ← n //标记被交换的最后元素位置 2 while FLAG > 1 do 3 k ← FLAG - 1 4 FLAG ← 1 5 for j = 1 to k do 6 if L(j) > L(j + 1) then do 7 L(j) ↔ L(j + 1) 8 FLAG ← j
对 个数用以上冒泡排序算法进行排序，最少需要比较多少次？（ ）
C：n-1。带 flag 改进冒泡：已有序时第一趟无交换，FLAG 设为 1，外层 while 结束，共 n-1 次比较；最坏情况是逆序 n(n-1)/2，但「最少」问最好情况。
排序算法是稳定的（Stable Sorting），就是指排序算法可以保证，在待排序数据中有两个相等记录的关键字 R 和 S（R 出现在 S 之前），在排序后的列表中 R 也一定在 S 前。下面关于排序稳定性的描述，正确的是（ ）。
C：选择排序不稳定。选择排序交换的是当前未排序区最小元素与位置 i 的元素，二者不一定相邻，相对顺序可能改变；冒泡和插入排序只交换相邻元素，故稳定。
对包含 n 个元素的数组进行冒泡排序，平均时间复杂度一般为（ ）。
C：O(n²)。冒泡排序通过相邻交换冒泡，每趟最多 n-1 次比较，共 n-1 趟，平均/最坏 O(n²)；最好情况（已有序）O(n)。
对 N 个元素的数组执行插入排序算法，通常的时间复杂度是 。
正确。插入排序每趟把元素插入已排序区，最坏/平均比较移动 O(N²)，只有已基本有序时接近 O(N)。
归并排序的时间复杂度是 。
对。归并排序把区间不断二分，递归深度约 log2N 层，每层合并所有元素的总代价为 O(N)，故总时间复杂度为 O(N log N)。
插入排序在最好情况下的时间复杂度是（ ）。
C：O(n)。插入排序最好情况是数组已有序，每趟只需一次比较（共 n-1 次），时间复杂度 O(n)。
对 int a[] = {2,0,2,4,3,1,6}，执行第一趟选择排序处理后 a 中数据变为 {0,2,2,4,3,1,6}。
正确。{2,0,2,4,3,1,6} 第一趟选择排序扫描找最小元素 0（位于 index 1），与首位 2 交换，得 {0,2,2,4,3,1,6}。
如果待排序数据不能都装进内存，需要使用外排序算法。
正确。待排序数据无法全部装入内存时需使用外排序（典型如归并排序），分块排序再合并。
关于直接插入排序，下列说法错误的是（ ）。
D：空间复杂度 O(n)。插入排序是就地排序，只用常数级额外空间（当前元素、循环变量），空间复杂度 O(1) 而非 O(n)。
下列程序横线处，应该输入的是（ ）。
01#include<iostream> 02using namespace std; 03int n,a[10001]; 04void swap(int &a,int &b) 05{ 06 int t=a; 07 a=b; 08 b=t; 09} 10int main() 11{ 12 cin>>n; 13 for(int i=1;i<=n;i++) 14 cin>>a[i]; 15 for(int i=n;i>1;i--) 16 for(int j=1;j<i;j++) 17 if(a[j]>a[j+1]) 18 ____________; 19 for(int i=1;i<=n;i++) 20 cout<<a[i]<<" "; 21 cout<<endl; 22 return 0; 23}
A：swap(a[j],a[j+1])。swap 函数接受两个 int& 引用，调用 swap(a[j],a[j+1]) 即可交换两元素（B/D 下标错，C 跨度错）。
关于几种排序算法的说法，下面说法错误的是（ ）。
B：冒泡排序算法不是一种稳定的排序算法——错误。冒泡排序只交换相邻元素，相等元素的相对顺序不变，是稳定排序。
插入排序算法中，平均时间复杂度是 ，最坏的情况逆序情况下，达到最大时间复杂度。
正确。插入排序平均时间复杂度 O(n²)，最坏情况（逆序）达到上界，需要最多比较和移动次数。
在排序算法中，稳定性指的是（ ）。
B：排序后相同元素的相对顺序保持不变。这是排序算法稳定性的定义；A/C/D 都是对「稳定」一词的误解。
下面代码实现了冒泡排序函数，则横线上应填写（ ）。
01//交换数组arr的第i个元素和第j个元素 02void swap(vector<int> &arr, int i, int j) { 03 int tmp = arr[i]; 04 arr[i] = arr[j]; 05 arr[j] = tmp; 06} 07 08int bubble_sort(vector<int> &arr) { 09 for (int i = arr.size() - 1; i > 0; i--) { 10 bool flag = false; // 标志位 11 ____________{ // 在此处填入代码 12 if(arr[j] > arr[j + 1]) { 13 swap(arr, i, j); 14 flag = true; 15 } 16 } 17 if(!flag) 18 break; // 此轮"冒泡"未交换任何元素 19 } 20} 21
C：for (int j = 0; j < i; j++)。冒泡排序外层 i 控制当前未排序区右端，内层 j 从 0 到 i-1（不含 i）相邻比较交换；A 范围错，B 逆序错，D 条件永假。
冒泡排序算法在最坏情况下的时间复杂度为（ ）。
A：O(n²)。冒泡排序无论最坏/平均都要 n-1 趟、每趟最多 n-1 次比较，总 O(n²)；最好情况（已有序）O(n)。
选择排序是稳定的排序算法。
错。选择排序每趟将最小元素与未排序区首位交换，交换的元素不一定相邻，相等元素的相对顺序可能被改变，是不稳定排序。
插入排序的时间复杂度总是比冒泡排序低。
错。插入排序与冒泡排序平均都是 O(n²)，复杂度相当，没有「插入总比冒泡快」的说法；具体常数因子和实际数据有关。
下面关于排序算法（冒泡排序、插入排序和选择排序）的描述中，不正确的是（ ）。
C：冒泡排序在任何情况下的时间复杂度都为 O(n²)——错误。冒泡加标志优化后，最优情况（已有序）只一趟 O(n)；只有最坏和平均才是 O(n²)。
冒泡排序的第一轮操作是从左到右遍历数组，通过两两比较相邻元素，将当前最大的元素移动到末尾。给定数组 arr[]={4, 1, 3, 1, 5, 2}，执行第一轮冒泡排序后数组 arr 中的内容为（ ）。
B：1,3,1,4,2,5。{4,1,3,1,5,2} 第一趟从左到右相邻比较交换：4>1 换 {1,4,3,1,5,2}；4>3 换 {1,3,4,1,5,2}；4>1 换 {1,3,1,4,5,2}；4<5 不换；5>2 换 {1,3,1,4,2,5}，最大 5 沉底。
下面代码实现了插入排序函数，则横线上应填写（ ）。
01void insertion_sort(vector<int> &nums) { 02 for (int i = 1; i < nums.size(); i++) { 03 ____________ { // 在此处填入代码 04 while (j >= 0 && nums[j] > base) 05 nums[j + 1] = nums[j]; 06 j--; 07 } 08 nums[j + 1] = base; 09 } 10}
A：int base = nums[i], j = i - 1;。插入排序把当前 nums[i] 作为 base 保存，j 从 i-1 向前扫描已排序部分找插入位置。
冒泡排序的平均时间复杂度为 ，但最优情况下为 。
正确。冒泡排序平均 O(n²)；若加标志优化（提前结束），最优情况（已有序）只一趟 O(n) 比较无交换。
冒泡排序和插入排序都是稳定的排序算法。
正确。冒泡和插入排序都只交换/移动相邻元素，相等元素的相对顺序不会改变，都是稳定排序。
下面关于排序稳定性的描述，正确的是（ ）。
B：稳定排序保证相同元素的相对顺序不变。这是排序稳定性的标准定义；A 错（稳定性与时间复杂度无关），C 错（选择排序不稳定），D 错（插入排序稳定）。
对数组 arr[]={5, 3, 8, 1} 进行升序排序，执行第一轮冒泡排序后数组 arr 中的内容为（ ）。
A：3,5,1,8。{5,3,8,1} 第一趟冒泡：5>3 换 {3,5,8,1}；5<8 不换；8>1 换 {3,5,1,8}，最大 8 沉底。
插入排序在最好情况（已有序）下的时间复杂度是 。
错。插入排序最好情况（数组已有序）每趟只需 1 次比较，共 n-1 次比较，时间复杂度 O(n)，不是 O(n²)。
以下哪种情况是使用插入排序的合适场景?
C：数据几乎有序，只需少量调整。插入排序对近有序数据表现极佳（接近 O(n)），适合此类场景；A 大数据乱序用快排/归并，B 稳定可用归并，D 交换次数最少用选择排序。
无论初始数组是否有序,选择排序都执行 次比较。
正确。选择排序每趟都要扫描未排序区找最小，不管是否有序都要 O(n²) 次比较（仅交换次数可优化）。
关于排序算法的稳定性，以下说法错误的是（ ）。
C：选择排序是稳定的排序算法——错误。选择排序把最小元素与首位交换，交换元素不一定相邻，相等元素相对顺序可能改变，不稳定。
下面代码试图实现选择排序，使其能对数组 nums 排序为升序，则横线上应分别填写（ ）。
01void selectionSort(vector<int>& nums) { 02 int n = nums.size(); 03 for (int i = 0; i < n - 1; ++i) { 04 int minIndex = i; 05 for (int j = i + 1; j < n; ++j) { 06 if ( ____________ ) { // 在此处填入代码 07 minIndex = j; 08 } 09 } 10 ____________; // 在此处填入代码 11 } 12}
A：nums[j] < nums[minIndex]; swap(nums[i], nums[minIndex])。选择排序升序：若 nums[j] 比当前最小 nums[minIndex] 还小就更新 minIndex；每趟结束后把 nums[i] 与 nums[minIndex] 交换。
关于插入排序的时间复杂度，下列说法正确的是（ ）。
B：最好情况是 O(n)，最坏情况是 O(n²)。插入排序最好（已有序）只需 n-1 次比较 O(n)；最坏（逆序）O(n²)。
虽然插入排序的时间复杂度为 ，但由于单元操作相对较少，因此在小数据量的排序任务中非常受欢迎。
正确。插入排序虽然 O(n²)，但单元操作少（赋值优于交换）、对近有序数据高效、实现简单，小数据量排序表现良好。
对如下 个扑克牌进行排序，
01struct Card { 02 int value; 03 char suit; // 花色 04}; 05 06Card cards[4] = {{5,'A'}, {3,'B'}, {5,'C'}, {3,'D'}};
使用某排序算法按 value 排序后，结果为：{3,'D'}，{3,'B'}，{5,'A'}，{5,'C'}，则这个排序算法是稳定的吗？
B：不稳定。原始顺序 value=3 的 'D' 在 'B' 前，排序后 'D'(3) 在 'B'(3) 前；但题目结果中 value=3 的 'D' 在 'B' 前 → 这其实保持原顺序。让我重读：cards[4] = {{5,'A'}, {3,'B'}, {5,'C'}, {3,'D'}}，原始 3,'B' 在 3,'D' 前；排序后 {3,'D'},{3,'B'},... 'D' 跑到 'B' 前，相对顺序改变 → 不稳定。
小杨在对“能量晶石”按亮度进行排序。如果两块晶石亮度相同，他希望保持它们在原始序列中的相对顺序。下列关于排序算法稳定性的说法，错误的是（ ）。
C：选择排序是稳定的——错误。选择排序交换最小元素到前面，交换可能跨多个元素，相等元素相对顺序可能改变，是不稳定排序。