1. 直接插入排序（Straight Insertion Sort）
1.1 基本排序
void insertSort(int *arr, int len) {
for (int i = 1; i < len; ++i) { // 从第2个元素开始插入，原始单个元素视为有序
int x = arr[i]; // 要插入的元素设为哨兵
// 在要插入序列已经有序的情况下，插入x
int j = 0;
while (x > arr[j]) j++;
// 跳出循环时，x <= arr[j]，x的插入位置为arr[j]，原始的从arr[j]开始的元素都后移，i对应着有序序列的长度
// 插入x之后序列长度为i+1，所以从arr[i]开始平移到arr[j+1]
for (int k = i; k > j; --k) arr[k] = arr[k - 1];
// for循环的最后一个操作：arr[j+1] = arr[j]，而新的arr[j]=哨兵x，原有的0..j-1的有序序列不受影响
arr[j] = x;
}
}
注意：
- 其实可以再寻找 j 的过程中，完成数据后移
- 要判断是否需要平移有序对，不需要的不用处理，因为顺序已正序
void insertSort(int *arr, int len) {
for (int i = 1; i < len; ++i) { // 从第2个元素开始插入，原始单个元素视为有序
if (arr[i] < arr[i - 1]) {
int x = arr[i];
int j = i - 1; // 原始序列的最后一个
while (x < arr[j] && j >= 0) {
arr[j + 1] = arr[j];
j--;
}
// 跳出时，x >= arr[j]
arr[j + 1] = x;
}
}
}
1.2 处理NaN情况
NaN数据定义
#include <cmath>
#define NaN (int)sqrt(-1.0) // 具体数据为多少不重要，只要在比较的时候跳过即可
将NaN类型的数据跳过，要注意：
- 最外层for循环从0开始而不是从1，因为可能出现数列一开始就是NaN
- x是要插入的数据，要跳过NaN
- 在寻找x插入位置时，j 遍历有序数列时要跳过NaN
- 在找到x插入位置之后，后边数列的后移也要跳过NaN
- 最关键的一点，在寻找arr[k-1]时，要跳过NaN，tmp在向左寻找非NaN时，边界为>=j，对应一般情况下，for的最后一步：arr[j+1] = arr[j]
前一种
// 处理 NaN
void insertSort(int *arr, int len) {
for (int i = 0; i < len; ++i) { // 1.因为可能出现一开始NaN的情况，所以i从0开始
if (arr[i] == NaN) continue; // 2.要插入的元素为NaN，直接跳过
int x = arr[i];
//3.在寻找x插入位置时，j遍历有序数列时要跳过NaN
int j = 0;
while (arr[j] == NaN) j++; // j=0也要一层while因为序列一开始也可能是NaN
while (x > arr[j]) {
j++;
if (arr[j] == NaN) j++; // 跳过
}
// cout << "插入" << x << " 位置" << j << " 有序长度" << i + 1 << endl;
//4.在找到x插入位置之后，后边数列的后移也要跳过NaN
for (int k = i; k > j; --k) {
if (arr[k] == NaN) continue; // 跳过
// arr[k] != NaN 时，寻找前一个交换值
int tmp = k - 1; // 千万不要直接k--，这样就影响了循环中的k
while (arr[tmp] == NaN && tmp >= j) tmp--; // 5.注意细节，tmp可以为j
if (tmp >= j) arr[k] = arr[tmp]; // 找到了可以交换的非NaN值
}
arr[j] = x;
// printArr(arr, len);
}
}
后一种
// 处理 NaN
void insertSort(int *arr, int len) {
for (int i = 0; i < len; ++i) { // 从第2个元素开始插入，原始单个元素视为有序
if (arr[i] == NaN) continue;
int tmp = i - 1;
while (arr[tmp] == NaN && tmp >= 0) tmp--; // 倒着寻找前一个非NaN数
// 找到情况下
if (tmp >= 0) {
// 需要平移
if (arr[i] < arr[tmp]) {
int x = arr[i]; // 哨兵
int pos1 = tmp; // 前1个数
int pos2 = i; // 后1个数
while (x < arr[pos1] && pos1 >= 0) {
arr[pos2] = arr[pos1];
pos2 = pos1; // 继承前1个数的位置，作为下一次平移的后1个数
pos1--;
while (arr[pos1] == NaN && pos1 >= 0) pos1--; // 寻找下一次平移的前1个数
}
// 跳出时，x >= arr[pos1]，pos2始终合理
arr[pos2] = x;
}
}
}
}
随机生成数据
int main() {
int len = 10; // 数列长度
int nan_num = 3; // NaN个数
auto *arr = new int[len];
srand((unsigned int) time(nullptr)); // 随机数种子
// 随机产生nan_num个位置放置NaN
for (int i = 0; i < nan_num; ++i) {
int pos = (int) random() % len;
arr[pos] = NaN;
}
// 剩下位置赋随机值
for (int i = 0; i < len; ++i) {
if (arr[i] != NaN) arr[i] = (int) random() % 100;
}
printArr(arr, len);
insertSort(arr, len);
printArr(arr, len);
}
15 93 35 NaN 86 92 NaN NaN 49 21
15 21 35 NaN 49 86 NaN NaN 92 93
另一组数据
int main() {
int arr[10] = {NaN, 86, 92, NaN, 48, NaN, NaN, NaN, 21, 62};
int len = 10;
printArr(arr, len);
insertSort(arr, len);
printArr(arr, len);
}
NaN 86 92 NaN 48 NaN NaN NaN 21 62
NaN 21 48 NaN 62 NaN NaN NaN 86 92
// 每一次for循环的排序过程
插入86 位置1 有序长度2
NaN 86 92 NaN 48 NaN NaN NaN 21 62
插入92 位置2 有序长度3
NaN 86 92 NaN 48 NaN NaN NaN 21 62
插入48 位置1 有序长度5
NaN 48 86 NaN 92 NaN NaN NaN 21 62
插入21 位置1 有序长度9
NaN 21 48 NaN 86 NaN NaN NaN 92 62
插入62 位置4 有序长度10
NaN 21 48 NaN 62 NaN NaN NaN 86 92
2. 折半（二分）插入排序
在寻找哨兵的插入位置时采用二分查找，因为插入的序列是有序的。其实也不必要，因为如果直接插入排序采用后一种方式，就不需要查找这个位置了。
折半插入排序是建立在前一种直排的基础上。
注意：不是插入具体的数，而是插入这个数的插入位置。
void insertSort(int *arr, int len) {
for (int i = 1; i < len; ++i) { // 从第2个元素开始插入，原始单个元素视为有序
int x = arr[i]; // 要插入的元素设为哨兵
// 二分查找插入位置
int left = 0, right = i - 1;
int j = 0;
while (left <= right) { // 跳出循环时j就是要插入的位置
j = (left + right) / 2;
if (x < arr[j]) right = j - 1;
else left = j + 1;
}
// 插入x之后序列长度为i+1，所以从arr[i]开始平移到arr[j+1]
for (int k = i; k > j; --k) arr[k] = arr[k - 1];
// for循环的最后一个操作：arr[j+1] = arr[j]，而新的arr[j]=哨兵x，原有的0..j-1的有序序列不受影响
arr[j] = x;
}
}
