1、直接插入排序:把后面未排序部分的首个数插入到前面已排序部分的正确位置上去,直到全部排好顺序。直接插入排序是稳定的,算法时间复杂度O(n^2)。
2、shell排序:将要排序的一组数按某个增量g分成若干组,每组中记录的下标相差g。对每组中全部元素进行直接插入排序,然后缩小增量g,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。shell排序是不稳定的,算法时间复杂度可改进到O(n^1.25)左右。
/* gap初始化为不大小n的序列(1、4、13、40、121、...)中的最小值 */
do (gap=3*gap+1); while(gap<=n);
for(gap/=3;gap>0;gap/=3) /* 缩小增量进采用除3的策略 */
for(i=gap;i<n;++i){ /* 对当前组进行直接插入排序 */
temp=v[i];
/* 在当前组的已排序部分中找到正确的插入位置 */
for(j=i-gap;(j>=0)&&(v[j]>temp);j-=gap)
v[j+gap]=v[j]; /* 元素后移,以空出插入位置 */
v[j+gap]=temp; /* 插入元素 */
}
}
注意一般的shell排序实现都是gap初始化为n/2,并采用除2的缩小增量策略。这里初始化为不大小n的序列(1、4、13、40、121、...)中的最小值,并采用除以3的缩小增量策略,这可使排序加快20%~30%。内循环中的赋值从3次减少到1次。这里增加了register修饰符,使这些变量存储在寄存器中,在有些实现中,register声明可以大大提高性能(有的高达40%)。
3、冒泡排序:对前面未排序部分每相邻的两个数进行比较和调整,让较大的数上浮到后面已排序部分的开头。冒泡排序是稳定的,算法时间复杂度O(n^2)。
这里设置了一个flag,当元素序列本身就是有序时,直接返回,这可以加快排序过程。
4、快速排序:扫描一次元素并不断地交换,使右边部分的各个数都比左边部分大。然后用同样的方法处理这两个子序列(用递归调用)。快速排序是不稳定的,最理想情况算法时间复杂度O(nlgn),最坏为O(n^2),空间复杂度需要O(lgn)。
注意实现时要找一个基准点的数,扫描完一遍后,左边部分都会小于基准点数,右边部分都会大于基准点数。因此开始时要暂存基准点数,扫描完一遍后把基准点插入到中间恰当的位置,这样就分出了左边部分和右边部分,然后递归调用即可。
5、选择排序:在后面未排序的部分中选择最小的数插入到前面已排序部分的末尾。直到倒数第二个数和最后一个数比较为止。选择排序是不稳定的,算法复杂度O(n^2)。
6、堆排序:是对选择排序的改进。把数组看作是二叉树,b[k]的两个子树为元素x[2*k]与x[2*k+1]。堆是一棵树,每个节点的数值不小于其后代节点的数值。初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储顺序,使之成为一个堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面n-1个数重新调整使之成为堆。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。堆排序是不稳定的,算法时间复杂度O(nlgn)。
for (k=n-1; k>=1; k--){
temp=*(x+0); /* 堆顶放到最后 */
*(x+0)=*(x+k);
*(x+k)=temp;
adjust(x,k,0); /* 剩下的数再调整为堆 */
}
}
注意堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成,一是建堆的调整函数,二是反复调用实现排序的函数。
7、归并排序:设两个有序的子序列(相当于输入堆)放在同一向量中相邻的位置上R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中。归并排序是稳定的,算法时间复杂度为O(nlgn),空间复杂度需要O(n)。
for (j=0,k=0,i=flow; i<=high; ++i){
if (j<n1&&k<n2){ /* 从大到小的顺序把两个子序列写入到array中 */
if (temp1[j]>=temp2[k])
array[i]=temp2[k++];
else
array[i]=temp1[j++];
}
else{ /* 一个子序列写入完后,另一个子序列可能还有剩余元素,把剩余元素也写入到array中 */
if(j>=n1&&k<n2)
array[i]=temp2[k++];
if(j<n1&&k>=n2)
array[i]=temp1[j++];
}
}
}
/* 排序函数 */
void merge_sort(int array[],int s,int t){
register int m;
if (s<t) {
m=(s+t)/2; /* 将数组分成两个子序列 */
merge_sort(array,s,m); /* 对左边子序列递归使用归并排序 */
merge_sort(array,m+1,t); /* 对右边子序列也递归使用归并排序 */
merge(array,s,m,t); /* 合并排好序的两个子序列 */
}
}
8、测试代码。
/* 输入测试数据 */
p=a;
input(p,MAX);
/* 测试直接插入排序 */
/*
p=a;
insert_sort(p,MAX);
print(a,MAX);
*/
/* 测试shell排序 */
/*
p=a;
shell_sort(p,MAX);
print(a,MAX);
*/
/* 测试冒泡排序 */
/*
p=a;
insert_sort(p,MAX);
print(a,MAX);
*/
/* 测试快速排序 */
/*
p=a;
quick_sort(p,0,MAX-1);
print(a,MAX);
*/
/* 测试选择排序 */
/*
p=a;
select_sort(a,10);
print(a,MAX);
*/
/* 测试堆排序 */
/*
p=a;
heap_sort(p,MAX);
print(a,MAX);
*/
/* 测试归并排序 */
p=a;
merge_sort(p,0,MAX-1);
print(a,MAX);
return 0;
}