插入排序（直接插入排序）

是一种基于“插入”的排序

思路

它的核心思想是把数组分成两部分：一部分是有序区，另一部分是乱序区也就是待排序区。
每次从未排序部分“取出”一个元素，插入到前半部分合适的位置，使得前半部分仍然有序。重复直到所有元素都被插入，排序完成。
举一个例子：
假设数组是：
A = [3, 1, 2, 8, 7]
第 1 步：只有第一个元素 3，它本身就是有序的。
有序区：[3] | 未排序区：[1, 2, 8, 7]
第 2 步：取出 1，插入到前面有序区 [3] 里。
比较 1 和 3，发现 1 < 3，于是把 1 插到 3 前面。
结果：[1, 3] | [2, 8, 7]
第 3 步：取出 2，插入到 [1, 3] 中。
比较 2 和 3，发现 2 < 3，把 3 向后挪，再把 2 插入。
结果：[1, 2, 3] | [8, 7]
第 4 步：取出 8，插入到 [1, 2, 3] 中。
发现 8 比 3 大，直接放到最后。
结果：[1, 2, 3, 8] | [7]
第 5 步：取出 7，插入到 [1, 2, 3, 8] 中。
比较 7 和 8，发现 7 < 8，于是 8 往后挪，把 7 插进去。
结果：[1, 2, 3, 7, 8]
我们很容易就可以发现这个插入排序的过程实际上就像打扑克时，让手中的牌排好的过程。
也很容易发现：
第i趟排序，插入第i个数x，即在有序区中找到x的位置，把该位置空出来，把x插入。
就是把每一个数放到它该处在的有序区的位置，其中第一个数是不用排的，直接从第二个数开始排即可。

代码

思路很简单，重点在于代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <limits.h>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;int main()
{//ios::sync_with_stdio(0),cin.tie(0),cout.tie(int n;int a[105];//初始序列 cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}//插入排序 for(int i=2;i<=n;i++){//第一个位置不用排，从第二个位置排即可。int k=0;int x=a[i];for(int j=1;j<=i-1;j++){if(a[j]>=a[i]){k=j;break;}} if(k!=0){for(int j=i-1;j>=k;j--){a[j+1]=a[j];}a[k]=x;}}//输出排序后的序列 for(int i=1;i<=n;i++){cout<<a[i]<<" ";} return 0;}

这里我们是严格的按照：
第i趟排序，插入第i个数x，即
1.在有序区中找到x的位置，
2.把该位置空出来，
3.把x插入。
一步步的写的，实际上我们可以边比较边移动

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <limits.h>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;int main()
{//ios::sync_with_stdio(0),cin.tie(0),cout.tie(int n;int a[105];//初始序列 cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}//插入排序 for(int i=2;i<=n;i++){//第一个位置不用排，从第二个位置排即可。int k=0;int x=a[i];int j;for(j=i;j>1;j--){if(a[j-1]>x){a[j]=a[j-1];}else{break;}} a[j]=x;}//输出排序后的序列 for(int i=1;i<=n;i++){cout<<a[i]<<" ";} return 0;}

用vector+从0下标开始更合适

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <limits.h>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
vector<int> a(105);
int main()
{//ios::sync_with_stdio(0),cin.tie(0),cout.tie(int n;//初始序列 cin>>n;for(int i=0;i<n;i++){cin>>a[i];}//插入排序 for(int i=1;i<n;i++){//第一个位置不用排，从第二个位置排即可。int k=0;int x=a[i];int j;for(j=i;j>0;j--){if(a[j-1]>x){a[j]=a[j-1];}else{break;}} a[j]=x;}//输出排序后的序列 for(int i=0;i<n;i++){cout<<a[i]<<" ";} return 0;
}

时间复杂度

由代码很容易看出来，时间复杂是O(n^2)
插入排序不适合对大量数据进行排序应用，但排序数量级小于千时插入排序的效率还不错，可以考虑使用。插入排序在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

就地性

因为只用一个数组，所以是就地排序

稳定性

稳定性是指不改变数组数值的相对位置

        if(a[j-1]>x){a[j]=a[j-1];}else{break;}

只有在>x的时候才移动插入，可以保证稳定性。
因此插入排序是稳定的

内部排序

因为所有待排序记录可以⼀次载⼊内存时，因此它是内部排序。
只有归并排序是外部排序。

优化

插入排序的时间复杂度是O（n^2)是不高的，为了提升性能，有下面几类优化

折半插入排序

在普通的插入排序中，我们从后往前一位一位的比较，找到插入的位置，需要进行O（n）次比较。
但前半部分也就是有序区是有序的，因此我们可以在这里采用一个二分查找来实现比较，而折半插入排序就是这样的。
思路：
第 i 次插入时，在 [0…i-1] 的有序区里，用二分查找找到 key 的插入位置。
然后再把比 key 大的元素整体往后挪一位。
因为采用了二分比较次数由O（n）变到了O（logn）
但是总体的移动次数还是不变的是O（n）
因此总体的时间复杂度还是O(n^2)
原来是O（n）（O（n）+O(n））
现在是O（n）（O（logn）+O（n））
性能提升有限，只有在比较比移动大的多的时候才有优势
尽管性能有限，但我们也要理解这种思路，对我们的以后学习有启发。

二路插入排序（基于循环数组的优化）

二路插入排序是在折半插入排序的基础上进行改进的。
它对折半插入排序的移动次数无法优化的问题进行了改进。
二路插入排序利用一个循环数组来存放排序好的序列，
插入时如果 key 比当前有序序列的最小值还小，就往前插。
如果 key 比最大值还大，就往后插。这样移动的元素不超过一半。
这就比之前移动所以的元素要更快。
原来的折半插入是：
查找插入位置：O(log n) （二分）
移动元素：是 O(n)
现在二路插入排序把移动元素：O(n) → O(n/2)
时间复杂度即变成O（n）*（O（logn）+O（n/2））
变得更快了，但它仍是O（n^2)的数量级。
重点在于思路掌握。