用c语言写的归并法改进快速排序

来源：百度知道 编辑：UC知道 时间：2024/05/17 02:38:49
Proc qkSort (VAR Data : List ; Start , Final : Integer) ; if Start > = Final then return ; k : = qkPass (Data , Start , Final) ; FirstSize : = k - Start ; SecondSize : = Final - k ; if FirstSize > SecondSize then ratio : = FirstSize / SecondSize else ratio : = SecondSize / FirstSize ; if ratio > M then / / M 是预先确定的一个值 , 用于判断这是否是个畸形划分 , 【 if FirstSize > SecondSize then 【 mid : = (k - 1 - Start) / 2 + Start ; / / 对较长的子序列 , 先分割成均匀的两部分 qkSort (Data , Start ,mid) ; / / 分别进行排序 qkSort (Data ,mid + 1 ,k - 1) ; Merge (Data ,Start ,mid ,k - 1) ; 】 / / 再归并 else 【 mid : = (Final - (k + 1) ) / 2 + (k + 1) ; qkSort (Data ,k + 1 ,mid) ; qkSort (Data ,mid + 1 ,Final) ; Merge (Data ,k + 1 ,mid ,Final) ; 】 else / / 如果是非畸形划分 , 则可以直接递归调用本排序算法 【 qkPass (Data ,Start ,k - 1) ; qkPass (Data ,k + 1 ,Final) ; 】 ENDP.

# include <stdio.h>
# define N 100
struct redtype
{
int key;
};

int num,i,j,s,t;
int NO;
struct redtype r[N];

void out(struct redtype r[])
{
int i;
printf("第%d次调用qkpass的快速排序结果:\n",(NO+1));
for(i=s;i<=t;i++)
{
if(i%11==0)
printf("\n");
printf("%6d",r[i].key);
}
printf("\n");
}/* out */
void qksort(struct redtype r[],int s,int t)
{
int j,x;
i=s; j=t;
if(s<t)
{
x=r[s].key;
while(i<j)
{
while((j>i)&&(r[j].key>=x)) --j;
if(i<j)
{
r[i]=r[j];i++;
}
while((i<j)&&(r[i].key<=x)) ++i;
if(i<j)
{