一 选择排序
最简单的排序算法，过程如下：选出数组中最小的元素，将它与数组中第一个元素交换。然后找出次小的元素，将它与数组中第二个元素交换，一直持续下去，直到整个数组排序结束。之所叫选择排序，是因为它不断选出剩余元素中的最小元素来实现。
实现代码如下：
void selection(Item a[],int l,int r)
{
int i,j;
for(i=l;i<r;i++)
{
intmin=i;//最小元素索引
for(j=j+1;j<=r;j++)
{
if(less(a[j]),a[min])
{
min=j;//更新最小元素的索引值
}
}
exch(a[i],a[min]);//交换
}
}
选择排序的执行时间由比较操作的数目决定，所使用的次数大概是
：比较操作次数N*N/2,交换操作次数是 N次。而且选择排序的时间消耗与当前序列的排序状态无关。
二 插入排序
在计算机应用中，为了插入新数据，先将较大的数据一个一个向右移动，然后将新数据插入在空位中。原理如下：首先将数组中最小的元素放在第一位，这个元素可以当做观察哨，然后当前索引左边的元素都是排好序的，但是并不在最终的位置上，以后还需要移动来为更小的数据腾出空间，当索引到达最右边的时候排序完成。
实现代码如下：
void insertion(int a[],int l,int r)
{
int i;
for(i=r;i>l;i--)
{
if(a[i]<a[i-1])
{
inttemp=a[i];
a[i]=a[i-1];
a[i-1]=temp;
}
}//将最小元素移到最左边
for(i=l+2;i<=r;i++)
{
intj=i;
intv=a[i];
while(less(v,a[j-1]))
{
a[j]=a[j-1];
j--;
}
a[j]=v;
}
}
和选择排序不同的是：插入排序的运行时间和输入文件数据的原始排列顺序密切相关。
三 冒泡排序
冒泡排序很简单：遍历文件，如果紧邻的两个元素顺序不对，就将两者交换，重复这个操作，直到整个序列排好序。对于l~r-1的i值，内部循环j通过从右到左遍历元素，对连续的元素执行比较—交换操作，实现将a[i],…a[r]中最小的元素放大a[i]中。在所有的比较操作中，最小的元素都要移动，冒到最前端。
void maopao(Item a[],int l,int r)
{
inti,j;
for(i=l;i<r;i++)
{
for(j=r;j>i;j--)
{
if(less(a[j],a[j-1]))
{
Itemtemp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
}
}
在最坏情况和平均情况下，冒泡排序执行大约N*N/2次比较操作和N*N/2次交换操作。
四 希尔排序
希尔排序时插入排序的扩展，他通过允许非相邻的元素进行交换来提高执行效率。希尔排序的本质：h-排序，是每第h个元素产生一个排序好的文件。h-排序的文件时h个独立的已排序好的文件，相互交叉在一起。对h值较大的h排序文件，可以移动相距较远的元素，比较容易的使h值较小时进行h排序，通过直到1的h值的排序，产生有序文件。
void hell(int *data,int left,int right)
{
intlen=right-left+1;
intd=len;
while(d>1)
{
d=(d+1)/2;
for(int i=left;i<right+1-d;i++)
{
if(data[i+d]<data[i])
{
inttmp=data[i+d];
data[i+d]=data[i];
data[i]=tmp;
}
}
}
}
希尔排序要选择一个比较好的步长序列。