while(A[h]>=t)h--;
if(h>l)
{
temp=A[l];
A[l]=A[h];
A[h]=temp;
}
}
Quick_Sort(A,low,l-1);
Quick_Sort(A,l+1,high);
}
}
==================================
四.归并排序
归并排序是将两个或两个以上的有序子表合并成一个新的有序表。
初始时,把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成,将它们依次两两归并得到长度为2的若干有序子表,再对它们两两合并。
直到得到长度为n的有序表,排序结束。
归并排序是一种稳定的排序,可用顺序存储结构,也易于在链表上实现,对长度为n的文件,需进行log2n趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。
归并排序需要一个辅助向量来暂存两个有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序。
代码略...
=================================
五.基数排序
设单关键字的每个分量的取值范围均是C0<=Kj<=Crd-1(0<=j<=rd),可能的取值个数rd称为基数.基数的选择和关键字的分解因关键字的类型而异.
(1).若关键字是十进制整数,则按个、十等位进行分解,基数rd=10,C0=0,C9=9,d为最长整数的位数.
(2).若关键字是小写的英文字符串,则rd=26,C0='a',C25='z',d为最长字符串的长度.
基数排序的基本思想是:
从低位到高位依次对待排序的关键码进行分配和收集,经过d趟分配和收集,就可以得到一个有序序列.
===================================
总结总结!
按平均时间将排序分为四类:
(1)平方阶(O(n2))排序
一般称为简单排序,例如直接插入、直接选择和冒泡排序;
(2)线性对数阶(O(nlgn))排序
如快速、堆和归并排序;
(3)O(n1+£)阶排序
£是介于0和1之间的常数,即0<£<1,如希尔排序;
(4)线性阶(O(n))排序
如基数排序。
各种排序方法比较
简单排序中直接插入最好,快速排序最快,当文件为正序时,直接插入和冒泡均最佳。
影响排序效果的因素
因为不同的排序方法适应不同的应用环境和要求,所以选择合适的排序方法应综合考虑下列因素:
①待排序的记录数目n;
②记录的大小(规模);
③关键字的结构及其初始状态;
④对稳定性的要求;
⑤语言工具的条件;
⑥存储结构;
⑦时间和辅助空间复杂度等。
不同条件下,排序方法的选择
(1)若n较小(如n≤50),可采用直接插入或直接选择排序。
当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜;
(3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:
快速排序、堆排序或
归并排序。
快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。
这两种排序都是不稳定的。
若要求排序稳定,则可选用归并排序。
但从单个记录起进行两两归并的 排序算法并不值得提倡,通常可以将它和直接插入排序结合在一起使用。
先利用直接插入排序求得较长的有序子文件,然后再两两归并之。
因为直接插入排序是稳定的,所以改进后的归并排序仍是稳定的。
=======================================
=========另一版=========================
=======================================
选择排序
在要排序的一组数中,选出最小的一个数与第一个位置的数交换;
然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环
到倒数第二个数和最后一个数比较为止。
选择排序是不稳定的。
算法复杂度O(n2)--[n的平方]
voidselect_sort(int*x,intn)
{
inti,j,min,t;
for(i=0;i0~n-2共n-1次*/
{
min=i;/*假设当前下标为i的数最小,比较后再调整*/
for(j=i+1;j {
if(*(x+j)<*(x+min))
{
min=j;/*如果后面的数比前面的小,则记下它的下标*/
}
}
if(min!
=i)/*如果min在循环中改变了,就需要交换数据*/
{
t=*(x+i);
*(x+i)=*(x+min);
*(x+min)=t;
}
}
}
直接插入排序
在要排序的一组数中,假设前面(n-1)[n>=2]个数已经是排
好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数
也是排好顺序的。
如此反复循环,直到全部排好顺序。
直接插入排序是稳定的。
算法时间复杂度O(n2)--[n的平方]
voidinsert_sort(int*x,intn)
{
inti,j,t;
for(i=1;i1~n-1共n-1次*/
{
/*
暂存下标为i的数。
注意:
下标从1开始,原因就是开始时
第一个数即下标为0的数,前面没有任何数,单单一个,认为
它是排好顺序的。
*/
t=*(x+i);
for(j=i-1;j>=0&&t<*(x+j);j--)/*注意:
j=i-1,j--,这里就是下标为i的数,在它前面有序列中找插入位置。
*/
{
*(x+j+1)=*(x+j);/*如果满足条件就往后挪。
最坏的情况就是t比下标为0的数都小,它要放在最前面,j==-1,退出循环*/
}
*(x+j+1)=t;/*找到下标为i的数的放置位置*/
}
}
冒泡排序
在要排序的一组数中,对当前还未排好序的范围内的全部数,自上
而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较
小的往上冒。
即:
每当两相邻的数比较后发现它们的排序与排序要
求相反时,就将它们互换。
下面是一种改进的冒泡算法,它记录了每一遍扫描后最后下沉数的
位置k,这样可以减少外层循环扫描的次数。
冒泡排序是稳定的。
算法时间复杂度O(n2)--[n的平方]
voidbubble_sort(int*x,intn)
{
intj,k,h,t;
for(h=n-1;h>0;h=k)/*循环到没有比较范围*/
{
for(j=0,k=0;j {
if(*(x+j)>*(x+j+1))/*大的放在后面,小的放到前面*/
{
t=*(x+j);
*(x+j)=*(x+j+1);
*(x+j+1)=t;/*完成交换*/
k=j;/*保存最后下沉的位置。
这样k后面的都是排序排好了的。
*/
}
}
}
}
希尔排序
在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,
并且对插入下一个数没有提供任何帮助。
如果比较相隔较远距离(称为
增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除
多个元素交换。
D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想。
算法先将要排序的一组数按某个增量d分成若干组,每组中
记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量
对它进行,在每组中再进行排序。
当增量减到1时,整个要排序的数被分成
一组,排序完成。
下面的函数是一个希尔排序算法的一个实现,初次取序列的一半为增量,
以后每次减半,直到增量为1。
希尔排序是不稳定的。
voidshell_sort(int*x,intn)
{
inth,j,k,t;
for(h=n/2;h>0;h=h/2)/*控制增量*/
{
for(j=h;j {
t=*(x+j);
for(k=j-h;(k>=0&&t<*(x+k));k-=h)
{
*(x+k+h)=*(x+k);
}
*(x+k+h)=t;
}
}
}
快速排序
快速排序是对冒泡排序的一种本质改进。
它的基本思想是通过一趟
扫描后,使得排序序列的长度能大幅度地减少。
在冒泡排序中,一次
扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只
减少1。
快速排序通过一趟扫描,就能确保某个数(以它为基准点吧)
的左边各数都比它小,右边各数都比它大。
然后又用同样的方法处理
它左右两边的数,直到基准点的左右只有一个元素为止。
它是由
C.A.R.Hoare于1962年提出的。
显然快速排序可以用递归实现,当然也可以用栈化解递归实现。
下面的
函数是用递归实现的,有兴趣的朋友可以改成非递归的。
快速排序是不稳定的。
最理想情况算法时间复杂度O(nlog2n),最坏O(n2)
voidquick_sort(int*x,intlow,inthigh)