排序之简单插入排序（数组）

简单插入排序： 构建一个有序序列，将未排序的数据，在已排序序列中从后往前扫描，找到相应的位置插入。（动图）

 就像整理扑克牌一样，随便抓了5张牌之后，要从左到右，将牌按照从小到大的顺序排列。因此，首先从第二张牌（目标牌）开始，与它之前的牌比较大小，若第一张牌比此牌大，那么将第一张牌往后移动一个位置，并将目标牌放在第一位；紧接着，目标牌换为第三张牌，以目标牌从后往前扫描。。。。。。

时间复杂度：最差（逆序）：O（n2）

最好（正序）：O(n)

总的：O(n2)

是稳定的。由于冒泡和选择排序。

#include<iostream> using namespace std; #define L 6 void InsertionSort(int *a,int length) { int i,j,key; for(i=1;i<length;i++) { key=a[i]; j = i-1; while(j>=0&&a[j]>key) { a[j+1] = a[j]; j--; } a[j+1] = key; } } int main () { int r[L]; for (int i=0;i<L;i++) { cin>>r[i]; } for (int i=0;i<L;i++) { cout<<r[i]; } cout<<endl; InsertionSort(r,L); for (int i=0;i<L;i++) { cout<<r[i]; } return 0; }