参考《数据结构与算法分析-c语言描述》一书。
1、插入排序
对于N个元素的数组，使用插入排序的需要N-1趟，在第P趟，数组将0到P位置的元素顺序排好，第P+1趟时，在0-P之间寻找合适的插入位置即可，插入排序的过程如下图所示：
代码实现：
#include <stdio.h>
void InsertionSort(int list[],int N)
{
int P,j,tmp;
for(P=1;P<N;P++)
{
tmp = list[P];
for(j=P;j>0 && list[j-1]>tmp;j--)
{
list[j] = list[j-1];
}
list[j] = tmp;
}
}
int main()
{
int list[6] = {34,8,64,51,32,21};
int i,N=6;
InsertionSort(list,6);
for(i=0;i<N;i++)
{
printf("%4d",list[i]);
}
}
算法分析：可以看到，在最好的情况下，所有的元素都已经是排好序的，那么直接插入排序的时间复杂度时O（N），在最坏的情况下，即数组元素的顺序与想要的顺序完全相反的时候，时间复杂度是O（N^2），空间复杂度是O（1），因为只需要一个哨兵即可。可以看到，在排序的时候移动元素的条件是大于，而不是大于等于，所以直接插入排序是稳定的算法（这里的稳定指的是数值相同的两个元素，在排序后保持原有的相对位置顺序不变）。
2、希尔排序
希尔排序是直接插入排序的一种变形。其基本的思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
代码实现：
#include <stdio.h>
void InsertionSort(int list[],int N)
{
int i,j,tmp,increment;
for(increment = N/2;increment>0;increment/=2)
{
for(i=increment;i<N;i++)
{
tmp = list[i];
for(j=i;j>=increment && list[j-increment]>tmp;j=j-increment)
{
list[j] = list[j-increment];
}
list[j]=tmp;
}
}
}
int main()
{
int list[6] = {34,8,64,51,32,21};
int i,N=6;
InsertionSort(list,6);
for(i=0;i<N;i++)
{
printf("%4d",list[i]);
}
}
算法分析：可以看到，在最好的情况下，所有的元素都已经是排好序的，那么直接插入排序的时间复杂度时O（N），在最坏的情况下，即数组元素的顺序与想要的顺序完全相反的时候，时间复杂度是O（N^2），空间复杂度是O（1），因为只需要一个哨兵即可。同时，希尔排序是不稳定的，比如9，8，8，4。我们使用增量为2时，index为2的8会到index=0的位置，而index=1的8会到index=3的位置，所以是不稳定的。
3、归并排序
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
二路归并排序代码如下：
#include <stdio.h>
#include <stdlib.h>
void merge(int list[],int tmpArray[],int left,int mid,int right)
{
int i = left;
int j = mid;
int t = left;
while (i<mid && j<=right)
{
if (list[i] <= list[j])
{
tmpArray[t++] = list[i++];
}
else
{
tmpArray[t++] = list[j++];
}
}
while(i<mid)
tmpArray[t++] = list[i++];
while(j<=right)
tmpArray[t++] = list[j++];
for(i=left;i<=right;i++)
list[i] = tmpArray[i];
}
void msort(int list[],int tmpArray[],int left,int right)
{
if (left < right){
int mid = (right - left) / 2 + left;
msort(list,tmpArray,left,mid);
msort(list,tmpArray,mid+1,right);
merge(list,tmpArray,left,mid+1,right);
}
}
int main()
{
int list[6] = {34,8,64,51,32,21};
int N = 6,i;
int * tmpArray;
tmpArray = (int *) malloc(N * sizeof(int));
msort(list,tmpArray,0,N-1);
free(tmpArray);
for (i = 0;i< N ;i++)
{
printf("%3d",list[i]);
}
}
归并排序的时间复杂度是O（nlogn），由于需要一个额外的等长的临时数组，所以归并排序的空间复杂度是O（N），最后，由于合并两个数组时使用的是小于等于的关系，当两个相同的数值存在于左右两个数组中时，仍然按照原来顺序进入排序后的数组，所以归并排序是稳定的
如果你喜欢我写的文章，可以帮忙给小编点个赞或者加个关注，我一定会互粉的！
如果大家对数据结构感兴趣，欢迎跟小编进行交流，小编微信为sxw2251，加我要写好备注哟！：
