用C随机函数生成n个随机数,然后用归并法排序
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/28 23:23:18
用C随机函数生成n个随机数,然后用归并法排序
用C随机函数生成n个随机数,然后用归并法排序
用C随机函数生成n个随机数,然后用归并法排序
/*
快排么.网上一搜就一堆了.算法只是一种思想或说成一种方法而已,并非就C语言.其它语言也一样
快排也有点像二路归并：从一个无序的序列中随机取出一个值q做为支点,然后把大于q的放到一边,小于q的放到q的另一边,然后再以q为分界点,分别对q的两边
进行排序（快排时直接再对q两边重新取支点,整理,再取支点,...直到支点两旁都有序.也就是支点两旁只有一个数时）
*/
#include <stdio.h>
#include <stdlib.h>
int Qsort(int p[],int beg,int end)
{
if(beg+1>=end)return 0;//退出递归
int low,hight,q;
low=beg;
hight=end;
q=p[low];//q为支点,其实q可以为随机数.但相应以下程序就要改了
while(1){
while(low<hight && p[hight]>q)hight--;
if(low>=hight)break;
p[low++]=p[hight];
while(low<hight && p[low]<q)low++;
p[hight++]=p[low];
}
p[low]=q;
Qsort(p,beg,low-1);
Qsort(p,low+1,end);
}
int main()
{
int i,a[]=;
Qsort(a,0,sizeof(a)/4-1);
for(i=0;i<sizeof(a)/4;i++)printf(" %d ",a[i]);
system("pause");
return 0;
}
快速排序的优势和支点元素的选择有关系.
所选支点元素每次递归后都在最前面或最后面.这样情况就会最差了.
我们知道一般的排序.（如冒泡.）在一个数组p[m,n]中排序.都是确定最大或最小,而确定最大值（最小值）要经过n-m-1次比较.
而整个过程就差不多是(n-m-1)!次比较.
快排中：一次比较可以确定支点元素的位置.若p[m,q,n](q为支点元素）.当然确定第一个元素也是要比较（n-m-1)次.但第二个,第三个（第二层）就是(q-m-1)和(n-q-1)次比较.
明显q的值若为m或n,快排就没有什么优势了