希尔排序法
希尔排序又称为缩小增量排序，也属于插入排序类的算法，是对直接插入排序的一种改进。
基本思想就是：将需要排序的序列划分为若干个较小的序列，对这些序列进行直接插入排序，通过这样的操作可使用需要排序的数列基本有序，最后再使用一次直接插入排序。这样，首先对数量较小的序列进行直接插入排序可提高效率，最后对基本有序的序列进行直拦插入排序，也可提高效率，从而使整个排序过程的效率得到提升。
程序实现：
public class ShellSorter
{
public void Sort(int[] list)
{
int inc;
for (inc = 1; inc <= list.Length/9; inc = 3*inc + 1) ;
for (; inc > 0; inc /= 3)
{
for (int i = inc + 1; i <= list.Length; i += inc)
{
int t = list[i - 1];
int j = i;
while ((j > inc) && (list[j - inc - 1] > t))
{
list[j - 1] = list[j - inc - 1];
j -= inc;
}
list[j - 1] = t;
}
}
}
} public class MainClass
{
public static void Main()
{
int[] iArrary = new int[] {1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47};
ShellSorter sh = new ShellSorter();
sh.Sort(iArrary);
for (int m = 0; m <= 13; m++)
Console.WriteLine("{0}", iArrary[m]);
Console.ReadKey();
}
}
合并排序法
合并排序（Merge Sort）就是将两个或多个有序表合并成一个有序表。
void MergeStep(int a[],int r[],int s,int m,int n) //相邻有序段合并
{
int i,j,k;
k=s;
i=s;
j=m+1;
while(i<=m && j<=n) //当两个有序表都未结束时，循环比较
{
if(a[i]<=a[j]) //当较小的元素复制到R中
r[k++]=a[i++];
else
r[k++]=a[j++];
}
while(i<=m) //将未合并的部分复制到R中
r[k++]=a[i++];
while(j<=n)
r[k++]=a[j++]; //将未合并的部分复制到R中
}
void MergePass(int a[],int r[],int n,int len) //完成一遍合并的函数
{
int s,e;
s=0;
while(s+len<n) //至少有两个有序段
{
e=s+2*len-1;
if(e>=n) //最后一段可能少于len个结点
e=n-1;
MergeStep(a,r,s,s+len-1,e); //相邻有序段合并
s=e+1; //下一对有序段中左段的开始下标
}
if(s<n) //还剩一个有序段，将其从A中复制到R中
for(;s<n;s++)
r[s]=a[s];
}
void MergeSort(int a[],int n)
{
int *p;
int len=1; //有序序列的长度
int f=0; //变量f作标志
if(!(p=(int *)malloc(sizeof(int)*n))) //分配内存空间，保存临时数据
{
printf("分配临时内存失败!\n");
exit(0);
}
while(len<n)
{
if(f) //交替地在A和P之间来回合并
MergePass(p,a,n,len); //调用MergePass，对p合并到a
else
MergePass(a,p,n,len); //调用MergePass，对a合并到p
len*=2; //增加有序序列长度
f=1-f; //使f值在0和1之间切换
}
if(f) //若进行了排序
for(f=0;f<n;f++) //将数组p中的数据复制到数组a
a[f]=p[f];
free(p); //释放分配的内存
}