插入排序
插入排序包括：直接插入排序，折半插入排序，希尔排序。
1.直接插入排序
思想：
直接插入排序（Straight Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
把a[i]插入到a[0]，a[1]，...,a[i-1]之中的具体实施过程为:先把a[i]赋值给变量t,然后将t依次与a[i-1],a[i-2],...进行比较,将比t大的元素右移一个位置,直到发现某个j(0<=j<=i-1),使得a[j]<=t或j为(-1),把t赋值给a[j+1].
把a[i]插入到a[0]，a[1]，...,a[i-1]之中的具体实施过程为:先把a[i]赋值给变量t,然后将t依次与a[i-1],a[i-2],...进行比较,将比t大的元素右移一个位置,直到发现某个j(0<=j<=i-1),使得a[j]<=t或j为(-1),把t赋值给a[j+1].
void InsertSort(int *arr,int len)
{
int i,j;
for(i=1;i<len;i++)
for(j=i-1;j>=0 && arr[j]>arr[j+1];j--)
{
//交换元素数值
//由于arr[j]不等于arr[j+1]，
//因此可以安全地用该交换方法
arr[j]^=arr[j+1];
arr[j+1]^=arr[j];
arr[j]^=arr[j+1];
}
}
时间复杂度O(N^2)
二、折半插入排序
直接插入排序的基本操作是在有序表中进行查找和插入，而在有序表中查找插入位置，可以通过折半查找的方法实现，由此进行的插入排序称之为折半插入排序。折半查找的过程是以处于有序表中间位置记录的关键字和Ki比较，经过一次比较，便可排除一半记录，把可插入的区间缩小一半，故称为折半。折半插入排序仅减少了关键字间的比较次数，但记录的移动次数不变。因此折半插入排序的时间复杂度仍为O(n2)。折半插入排序的空间复杂度与直接插入排序相同。折半插入排序也是一个稳定的排序方法。
void BInsert_Sort(int *arr,int len)
{
int i;
//从第1个元素开始循环执行插入排序
for(i=1;i<len;i++)
{
int low =0;
int high = i-1;
int key = arr[i];
//循环至要插入的两个点之间
while(low<=high)
{
int mid = (low+high)/2;
if(key<arr[mid])
high = mid-1;
else
low = mid+1;
}
//循环结束后low=high+1，并且low位置即为key要插入的位置
//从low到i的元素依次后移一位
int j;
for(j=i;j>low;j--)
arr[j] = arr[j-1];
//将key插入到low位置处
arr[low] = key;
}
}
三、希尔排序
希尔排序（shell’s sort）又称缩小增量排序(Diminishing
Increment Sort)。它是希尔（D.L.Shell）于1959年提出的插入排序的改进算法。如前所述，直接插入排序算法的时间性能取决于数据的初始特性，一般情况下，它的时间复杂度为O(n2)。但是当待排序列为正序或基本有序时，时间复杂度则为O(n)。因此，若能在一次排序前将排序序列调整为基本有序，则排序的效率就会大大提高。正是基于这样的考虑，希尔提出了改进的插入排序方法。
希尔排序的基本思想是：先将整个待排记录序列分割成若干小组（子序列），分别在组内进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。分割方法：选定一个记录的间隔值d，将所有间隔d的记录作为一组。在组内进行直接插入排序。然后缩小间隔，重新分组，再进行组内重新排序，直到间隔为1为止。
void Shell_Insert3(int *arr,int len,int ader)
{
int i,j,k;
//循环对ader个子序列各自进行插入排序
for(k=0;k<ader;k++)
for(i=ader+k;i<len;i+=ader)
for(j=i-ader;j>=k && arr[j]>arr[j+ader];j-=ader)
{
//交换元素数值
arr[j]^=arr[j+ader];
arr[j+ader]^=arr[j];
arr[j]^=arr[j+ader];
}
}
void Shell_Sort(int *arr,int len,int *add,int num)
{
int i;
//共进行nun趟不同增量的插入排序
for(i=0;i<num;i++)
Shell_Insert3(arr, len,add[i]); //一趟增量为add[i]的插入排序