插入排序
1. 插入排序
插入排序的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。
2. 直接插入排序
假设待排序的记录存放在数组R[0 .. n-1]中，排序过程的某一中间时刻，R被划分成两个子区间R[0 … i-1]和R[i … n-1]，其中已排好序的有序区，当前未排序的部分称其为无序区。
图1-直接插入排序
直接插入排序的基本操作是将当前无序区的第1个记录R[i]插入到有序区R[0 … i-1]中适当的位置上，使R[0 … i]变为新的有序区。直接插入排序每次使有序区增加1个记录，又称为增量法。
3. 直接插入排序过程
现在有一组待排序的初始关键字序列为{49 , 38 , 15 , 17 , 16 , 13 , 27 , 49}，直接插入排序过程如下：
图2-第一趟
首先将这个关键字序列的第一个关键字49放入有序区，其他关键字则全部都放在无序区中，在进行插入排序的时候，直接把无序区中的第一个关键字38提取出来，跟有序区中的关键字比较，由于38小于49，那么把关键字49往后移动一个位置，并把38插在49前面的位置。
图3-第二趟
第二趟同理，提取无序区中的第一个关键字15，跟有序区中的关键字比较，由于无序区中的关键字15比有序区中的关键字49小，那么15再跟38比较，由于15比38要小，因此直接把15插在38前面的位置。
图4-第三趟和第四趟
第三趟的时候同理，提取关键字17跟有序区中的关键字依次比较，在进行比较时发现关键字17比关键字49要小，把49往后移动，然后关键字再跟38比较，17比38小，继续把38往后移动，17再跟15比较，17比15大，把17插入在15后面的位置。第四趟的时候同理，提取关键字16依次跟有序区中的关键字进行比较，经过一番比较后，16比15小，因此把16插入在15后面的位置。
图5-第五趟
第五趟时，提取无序区中的第一个关键字13，然后跟有序区中的关键字按从后往前的顺序依次进行比较，13比97关键字要小，于是把97往后移动一个位置；13再跟76比较还是小，于是再把76往后移动一个位置，13继续跟65比较还是小，继续把65往后移动，13继续跟49比较还是小，继续把49往后移动，当13跟38比较还是小，把38往后移动，由于38已经是最后一个关键字了，当13跟38比较完后，13就插在当前这个位置。
从这个过程我们发现，在插入关键字13时，把有序区中的所有关键字都往后移动了一个位置。
图6-第六趟和第七趟
第六趟时同理，提取关键字27进行比较，把有序区中的所有比关键字27大的关键字都往后移动一个位置，由于17比27小，因此把27插在17后面的位置。
第七趟时从无序区中提取关键字49，经过比较后，49和49一样大，不需要移动位置，于是把关键字49插入在当前的位置，到此整个直接插入排序的过程基本上就结束了。
注意，在关键字序列中有两个都是49的关键字，在图中用了黑色和红色两种不同的颜色来区分。在排序前，黑色的关键字49在红色的关键字49的前面，在排序后，黑色的关键字49仍然在红色的关键字49的前面，由此可知，直接插入排序是一个稳定的排序。
同时我们还可以发现，直接插入排序在进行比较，查找插入位置的时候是一个顺序查找的过程，每一趟的插入都是有序的。
好了，相信你对直接插入排序算法的的过程已经有了基本了解，那么接下来我们来看一下直接插入排序算法的动画演示：
图7-直接插入排序算法演示
4. 直接插入排序算法
直接插入排序算法代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 8
typedef int KeyType; //定义关键字类型
typedef int InfoType; //其他数据项类型
typedef struct //记录类型
{
KeyType key; //关键字项
InfoType data; //其他数据项的类型InfoType
} RecType; //排序的记录类型定义
/*
直接插入排序
参数说明：
arr:传入要排序的数组
n：数组的大小
*/
void InsertSort(RecType R[] , int n)
{
int i;
int j;
RecType temp;
//R[O]默认为有序区，无序区从R[1]开始
for(i = 1; i < n; i++)
{
//外层for循环每次提取无序区的第一个关键字
temp = R[i];
/*
R[j-1].key > temp.key：有序区中的关键字是否比无序区的第一个关键字大
j--：从后往前，依次比较有序区中的每一个关键字
*/
for(j = i; j > 0 && R[j-1].key > temp.key; j--)
{
//把有序区中的关键字依次往后移动
R[j] = R[j-1];
}
/*
如果无序区中的第一个关键字比有序区中的关键字大，
那么无序区中的第一个关键字的位置插入到有序区中该关键字后面的位置
*/
R[j].key = temp.key;
}
}
int main(void)
{
RecType R[MAXSIZE] = {0};
int arr[] = {49,38,65,97,76,13,27,49};
int i;
printf("--------排序前--------\n");
for(i = 0; i < MAXSIZE; i++)
{
R[i].key = arr[i];
printf("R[%d].key = %d\n" , i , R[i].key);
}
//插入排序
InsertSort(R, MAXSIZE);
printf("--------排序后--------\n");
for(i = 0; i < MAXSIZE; i++)
{
printf("R[%d].key = %d\n" , i , R[i].key);
}
return 0;
}测试结果：
5. 直接插入排序的性能分析
现在我们来分析一下直接插入排序的性能，从空间复杂度来讲，直接插入排序只用了一个辅助空间变量，因此在这里我们重点关心时间复杂度。
最好的情况就是待排关键字序列是有序的，如图8所示：
图8-有序的关键字序列
最好情况的动画演示：
图9-最好的情况
1. 从图9来看，最好的情况就是，待排关键字序列的顺序本身就是有序的（即从小到大的方式排列），这样的话，在排序进行比较的时候每次只比较一次就行了，那么总的“比较”次数为：
在直接插入排序算法中每次都需要提取无序区中的关键字，即tmp=R[i]；同时还需要把关键字插入到有序区中合适的位置，即R[j].key = temp.key 。那么总的移动次数为：因此在最好的情况下，直接插入排序算法的时间复杂度是:
最坏的情况就是待排关键字序列是逆序的，如图10所示：
图10-逆序的关键字序列
最坏的情况动画演示：
图11-最坏的情况
2. 对于最坏的情况就是，我们的需求是按从小到大的方式排序，但是关键字序列中的顺序是逆序的（即从大到小的方式排列），在这种情况下，每次都要把有序区中的所有关键字都比较一次，总的比较次数为：
在最坏的情况下，每次都要把关键字插入最前面的位置（即每次都要把有序区中所有关键字往后移动），那么总的移动次数为：
因此在最坏的情况下，直接插入排序算法的时间复杂度是
总的平均比较和移动次数大概是：
也就是说，直接插入排序算法的平均时间复杂度还是
6 . 折半插入排序
再来看一个直接插入排序的改进版——折半插入排序，折半插入排序就是采用折半查找方法，称为二分插入排序或折半插入排序。
图9-折半插入排序
折半插入排序算法代码如下：
void InsertSort(RecType R[] , int n)
{
RecType temp;
int i;
int j;
int min;
int high;
int mid;
for(i = 1; i < n; i++)
{
//提取无序区的关键字
temp.key = R[i].key;
//在有序区进行折半查找要插入的位置
min = 0;
high = i - 1;
while(min <= high)
{
mid = (min + high)/2;
if(temp.key > R[mid].key)
{
min = mid + 1;
}
else
{
//无序区关键字比有序区关键字小
high = mid - 1;
}
}
//找high的位置，当找到要插入的位置时，从当前位置开始依次往后移
//第一趟的时候由于high = mid - 1，high的值为负数，所以high要+1
for(j = i; j > high+1; j--)
{
R[j] = R[j-1];
}
R[high+1].key = temp.key;
}
}7. 折半插入排序的性能分析
折半插入排序：在R[0] … R[i-1]中查找插入R[i]的位置，折半查找的平均关键字比较次数为
由于折半插入排序是采用折半查找进行比较，查找效率有所提高，但元素移动次数不变，仅仅将分散移动改为集合移动，而不是一边比较一边移动关键字的位置。
虽然平均时间复杂度仍然是折半插入排序是一种非稳定排序。
这里可能有同学会不解，直接插入排序和折半插入排序的性能都是
学过查找算法的同学知道，折半查找的效率要高于顺序查找，而直接插入排序算法在查找比较的过程中采用的是顺序查找；折半插入排序算法在查找比较的过程中是采用折半查找的，因此折半插入排序的性能略高一些。