一、直接插入排序

 

基本思想：我们平时玩扑克牌时，摸牌阶段的排序就用到了插入排序的思想

 

1、当插入第n个元素时，前面的n-1个数已经有序

 

2、用这第n个数与前面的n-1个数比较，找到要插入的位置，将其插入（原来位置上的数不会被覆盖，因为提前保存了）

 

3、原来位置上的数据，依次后移

 

 具体实现：

 

①单趟的实现（将x插入到 [0,end] 的有序区间）

 

即一般情况下的插入，我们随机列举了一些数字，待插入的数字分为两种情况

 

（1）待插入的数字是在前面有序数字的中间数，直接比较将x赋值给end+1位置

 

（2）x是最小的一个数，end就会到达-1的位置，最后直接将x赋值给end+1位置

 

 ②整个数组排序的实现 

 

我们一开始并不知道数组是不是有序的，所以我们控制下标，end从0开始，将end+1位置的值始终保存到x中，循环进行单趟排序即可，最后结束时end=n-2，n-1位置的数字保存到x中

 

 总体代码：

 

void InsertSort（int* a, int n）

 

{

 

assert（a）;

 

for （int i = 0; i < n - 1; ++i）

 

{

 

int end = i;

 

int x=a[end+1];//将end后面的值保存到x里面了

 

//将x插入到[0，end]的有序区间

 

while （end >= 0）

 

{

 

if （a[end] > x）

 

{

 

a[end + 1] = a[end];  //往后挪动一位

 

--end;

 

}

 

else

 

{

 

break;

 

}

 

}

 

a[end + 1] = x;      //x放的位置都是end的后一个位置

 

}

 

}

 

直接插入排序总结：

 

①元素越接近有序，直接插入排序的效率越高 

 

②时间复杂度：O（N^2）

 

最坏的情况下，每次插入一个数字，前面的数字都要挪动一下，一共需要挪动1+2+3+……+n=n（n+1）/2 

 

③空间复杂度：O（1）

 

没有借助额外的空间，只用到常数个变量