主要内容 #
- 算法讲解
- 例程
- 复杂度分析
1. 算法讲解 #
插入排序(InsertionSort)，一般也被称为直接插入排序。
对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
1.1 计算步骤 #
一般来说，具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
1.2过程模拟 #
原始数据 [ 49 ] 38 65 97 76 13 27 49 第1次排序 ["38" 49 ] 65 97 76 13 27 49 第2次排序 [ 38 49 "65"] 97 76 13 27 49 第3次排序 [ 38 49 65 "97"] 76 13 27 49 第4次排序 [ 38 49 65 "76" 97 ] 13 27 49 第5次排序 ["13" 38 49 65 76 97 ] 27 49 第6次排序 [ 13 "27" 38 49 65 76 97 ] 49 第7次排序 [ 13 27 38 "49" 49 65 76 97 ] 结束排序
动画演示如下图所示：
2. 例程 #
示例程序：
#include < iostream >
using namespace std;
int main()
{
// 依次从右边取出数，然后插入到它左边排序好的数组中
int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
int n = sizeof(a) / sizeof(int);
for (int i = 1; i < n; ++i) // i表示取出顺序，比如取 97，i=3
{
int j = 0; // j表示a[i]左边，已经排好序的数组的序号
for (j = i - 1; j >= 0; --j) // 从a[i]左边开始，从后往前，依次和a[i]比较大小
if (a[j] < a[i]) // 按照升序排列的规则，a[i]要放在a[j]的后面，注意，a[j]是从a[i]往左数，第一个小于a[i]的数
break;// 找到了a[i]应该排的位置
// j<=i-1，永远成立
// 当 j == i - 1，表示a[j]正好是a[i]左边第一个，这时候不需要调整位置
// 当 j < i - 1，需要移动一部分数组，然后才能插入a[i]
if (j < i - 1)
{
// 进入这里有两种情况：
// 1. 上面break出来，此时，0 <= j < i-1
// 2. 上面的for执行结束，此时，-1 = j
int temp = a[i]; // 暂存 a[i] 的值
int k = 0;
for (k = i - 1; k > j; --k)
a[k + 1] = a[k]; // 将从j+1到i的数据，往后移动一位。注意移动顺序，必须是从后往前
a[k + 1] = temp; // 将暂存 a[i] 的值，放在a[j]的“后面”（j为-1的情况也可以理解为“后面”）
}
}
// 输出
for (int i = 0; i < n; ++i)
cout << a[i] << " ";
return 0;
}
3. 复杂度分析 #
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。
最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需 n-1次即可。
最坏情况就是，序列是降序排列，那么此时需要进行的比较共有1/2n(n-1)次。插入排序的赋值操作是比较操作的次数减去 n-1次，（因为 n-1次循环中，每一次循环的比较都比赋值多一个，多在最后那一次比较并不带来赋值）。
平均来说插入排序算法复杂度为O(n^2)。因而，插入排序不适合对于数据量比较大的排序应用。
但是，如果需要排序的数据量很小，例如，量级小于千；或者若已知输入元素大致上按照顺序排列，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。
习题 #
请背诵并默写上述代码。
