插入排序
插入排序（Insertion Sort）
如何对扑克牌进行排序呢？例如现在手上有红桃6, 7, 9, 10这四张牌，已经处于升序排序状态。这时候抓到了一张红桃8，如何让手上的五张牌重新变成升序呢？
使用冒泡排序？选择排序？恐怕正常人打牌的时候都不会那么做。最自然最简单的方式，是在已经有序的四张牌中找到红桃8应该插入的位置，也就是7和9之间，把红桃8插入进去。
例如一个有8个数字组成的无序序列，进行升序排序。
互动实验
普通插入排序：暂存、比较、逐格右移
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
算法分析
插入排序要进行n - 1轮，每一轮在最坏情况下的比较复制次数分别是1次、2次、3次、4次...一直到n - 1次，所以最坏时间复杂度是。
至于空间复杂度，由于插入排序是在原地进行排序，并没有引入额外的数据结构，所以空间复杂度是。
| 时间复杂度 | 空间复杂度 | 稳定性 | 设计思想 |
|---|---|---|---|
| 稳定 | 减治法 |
插入排序
C
#include <stdio.h>
typedef int T;
/**
* Insertion Sort (original v1.0)
*/
T *insertion_sort(T *arr, int n) {
for (int i = 1; i < n; i++) {
T temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
return arr;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
insertion_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}折半插入排序（Binary Insertion Sort）
折半插入排序是对插入排序的改进，其过程就是不断依次将元素插入前面已经排好序的序列中，在寻找插入点时采用了折半查找。
折半插入排序
互动实验
折半插入排序：查找位置，再逐格右移
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
C
#include <stdio.h>
typedef int T;
/**
* Insertion Sort (original v1.0)
*/
T *insertion_sort(T *arr, int n) {
for (int i = 1; i < n; i++) {
T temp = arr[i];
int left = 0;
int right = i - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (temp < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = temp;
}
return arr;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
insertion_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}知识测验
题目
暂存8后，要把它插入[6,7,9,10]，先右移谁？
知识测验
题目
折半插入排序减少了比较次数，为什么最坏总时间仍为O(n²)？
动手练习
记录temp与每次右移
对[6,2,4,3]执行直接插入排序。逐轮写出temp、比较结果、每次右移与最终写回位置。再说明用二分查找插入点能减少什么、不能省略什么。