插入排序
插入排序
掌握排序算法中的插入排序的算法思想、排序步骤及代码实现。
插入排序维护左侧已有序区间，每次取下一个元素，从右向左找到合适位置插入。像整理手牌：新牌一张一张插到已排序部分的正确位置。实现上常用 while 后移空位再填入。
四级卷面常问：第 i 趟结束后前几个元素是否已有序、比较次数与初始顺序的关系（近乎有序时较快）、稳定性。最坏仍 O(n²)，但代码短、小数据实用。
void insertion(int a[], int n) {
for (int i = 1; i < n; ++i) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j+1] = a[j]; --j; }
a[j+1] = key;
}
}
trace 时把数组划成「已排序 | 待插入」两段，不容易跟丢下标。最好拿 4～5 个元素的例子手推一遍，对照代码里 i 与 j 的变化，考场上就不怕问「第 k 趟结束后数组长什么样」。
每次比较a[j]和key， 决定谁应该放在a[j+1]位置。 如果key赢了， 这一轮就不用继续走了。
理解代码
- 为了帮助理解， 可以想象内层其实就是一个循环， 一直比较a[j]和key，找到“适合放在a[j+1]位置的。
#include<iostream>
using namespace std;
int main(){
int a[]={12,2,344,2, 12, 5, 4};
int n=7;
// insertion sort
for(int i=1; i<n; i++){ // [0, i)是已排序范围
cout << "i:"<<i<<endl;
int key = a[i]; // 先把大小记下来， 叫做key。具体插在哪里， 以后再说。
int j=i-1;
// while(j>=0 && a[j]>key){
// a[j+1]=a[j];
// j--;
// }
// a[j+1]=key;
while(true){
if (a[j]>key){
a[j+1]=a[j];
}else{
a[j+1]=key;
break;
}
j--;
if (j<0){
a[j+1]=key;
break;
}
}
for(int k=0; k<n; k++)cout << a[k]<<". " ;
cout << endl;
}
for(int i=0; i<n; i++){
cout << a[i] << " ";
}
}
下面代码实现了插入排序函数，则横线上应填写（ ）。
void insertion_sort(vector<int> &nums) {
for (int i = 1; i < nums.size(); i++) {
________________________________ { // 在此处填入代码
while (j >= 0 && nums[j] > base)
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = base;
}
}
原文保真说明：原卷印刷错误 1 处（照原卷保留，未作修改）
原卷印刷如此多余符号题干 · 第 4 行
原卷作
________________________________ { // 在此处填入代码原卷填空行末尾多印一个左花括号「{」，加之第 3、5、7 行为空行、while 语句体花括号配对与缩进异常，全部照原卷版式转写。
插入排序在最好情况（已有序）下的时间复杂度是 $ O(n^2) $。
小杨在整理一副扑克牌的所有红心扑克牌，使其从小到大排列。他的做法是：最开始抓到第 1 张扑克牌被认为已经排好序；然后抓第 2 张扑克牌，将其插入至有序部分的正确位置；不断循环步骤，每次将新抓到扑克牌插入至有序部分，直至抓完所有扑克牌，这样抓牌结束时就完成了扑克牌的排序。小杨这种整理扑克牌的方式与（ ）排序的方式最接近。
以下哪种情况是使用插入排序的合适场景？
下面程序实现插入排序（升序排序），则横线上应分别填写（ ）。
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while ( j >= 0 && ____________________ ) { // 在此处填入代码
arr[j + 1] = arr[j];
j--;
}
____________________; // 在此处填入代码
}
}
A.
arr[j] > key
arr[j + 1] = key
B.
arr[j] < key
arr[j + 1] = key
C.
arr[j] > key
arr[j] = key
D.
arr[j] < key
arr[j] = key
虽然插入排序的时间复杂度为 O(n2)，但由于单元操作相对较少，因此在小数据量的排序任务中非常受欢迎。
某游戏的排行榜系统需要实时更新玩家分数。每次只有一个玩家的分数发生变化，排行榜已经是按分数降序排列的。现在需要将更新后的玩家调整到正确位置。下面的函数 updateRanking() 要实现上述功能，则两处横线上应分别填写（ ）。
struct Player {
string name;
int score;
};
// 玩家索引 playerIdx 的分数刚刚更新，需要调整位置
void updateRanking(Player players[], int size, int playerIdx) {
Player updatedPlayer = players[playerIdx];
if (playerIdx > 0 && updatedPlayer.score > players[playerIdx - 1].score) {
int i = playerIdx;
while (____________________) { // 在此处填入代码
players[i] = players[i - 1];
i--;
}
players[i] = updatedPlayer;
}
else if (playerIdx < size - 1 && updatedPlayer.score < players[playerIdx + 1].score) {
int i = playerIdx;
while (____________________) { // 在此处填入代码
players[i] = players[i + 1];
i++;
}
players[i] = updatedPlayer;
}
}
A.
i > 0 && updatedPlayer.score > players[i - 1].score
i < size - 1 && updatedPlayer.score < players[i + 1].score
B.
i < size - 1 && updatedPlayer.score < players[i + 1].score
i > 0 && updatedPlayer.score > players[i - 1].score
C.
i > 0 && updatedPlayer.score < players[i - 1].score
i < size - 1 && updatedPlayer.score < players[i + 1].score
D.
i > 0 && updatedPlayer.score < players[i - 1].score
i < size - 1 && updatedPlayer.score > players[i + 1].score
下面这段代码实现了选择排序算法。
void sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int x = a[i];
int j = i - 1;
while (j >= 0 && a[j] > x) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = x;
}
}
下面代码试图把数组按升序进行“插入排序”，横线处应填写（ ）。
void ins(int a[], int n){
for(int i = 1; i < n; i++){
int key = a[i];
int j = i-1;
while(j >= 0 && __________){
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
}
下列函数实现排行榜中单个元素的位置调整（类似插入排序的相邻搬移）。当某玩家分数增加，需将其向前移动时， while 循环的条件应为（ ）。
struct Player{ int score; };
void up(Player players[], int n, int idx){
Player cur = players[idx];
int i = idx;
while( ____________________ ){
players[i] = players[i-1];
i--;
}
players[i] = cur;
}