已知序列(10,18,4,3,6,12,1,9,8)请用快速排序写出每一趟排序的结果.
发布网友
发布时间：2022-05-15 01:43
共1个回答
热心网友
时间：2023-11-21 14:49
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef struct{
int r[MAXSIZE+1];
int length;
}Sqlist;
typedef int RcdType;
void InsertSort(Sqlist &L)//直接插入排序
{
int i,j;
for(i=2;i<=L.length;i++)
if(L.r[i]<L.r[i-1])
{
L.r[0]=L.r[i];
L.r[i]=L.r[i-1];
for(j=i-2;L.r[0]<L.r[j];j--)
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0];
}
}
/*SR原表
TR归并排序后的表
功能将有序的SR[i..m]和SR[m+1..n]归并成有序的TR[i..n]
*/
void Merge(RcdType *SR,RcdType *TR,int i,int m,int n)//归并排序
{
int k,j;
for(j = m+1,k = i;i <= m && j <= n;k++)
{
if(SR[i] < SR[j])
TR[k] = SR[i++];
else
TR[k] = SR[j++];
}
if(i<=m)
{
for(;i<=m;i++,k++)
TR[k] = SR[i];
}
if(j<=n)
for(;j<=n;j++,k++)
TR[k]=SR[j];
}
void MSort(RcdType *SR,RcdType *TR1,int s,int t)
//将SR[s..t]归并排序为TR1[s..t].
{
RcdType TR2[MAXSIZE];
int i;
int m;
if(s==t) TR1[s]=SR[s];
else
{
m=(s+t)/2;//将SR[s..t]平分为SR[s..m]和SR[m+1..t]
MSort(SR,TR2,s,m);//递归地将SR[s..m]归并为有序的TR2[s..m]
MSort(SR,TR2,m+1,t);//递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
Merge(TR2,TR1,s,m,t);//将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
for(i=s;i<=t;i++)
printf("%d ",TR1[i]);
printf("\n");
}
}
void MergeSort(Sqlist &L)
{
//对顺序表进行归并排序
printf("归并排序过程为:\n");
MSort(L.r,L.r,1,L.length);
printf("归并排序的结果为:\n");
}
void main()
{
int i;
Sqlist L,L1;
printf("输入学生记录个数：\n");
scanf("%d",&L.length);
printf("输入学生成绩:(格式为整数：a,b,c,d)\n");
for(i=1;i<=L.length;i++)
{
if(i!=L.length)
scanf("%d,",&L.r[i]);
else
scanf("%d",&L.r[i]);
}
for(i=1;i<=L.length;i++)
L1.r[i]=L.r[i];
L1.length=L.length;
printf("直接插入排序的结果:\n");
InsertSort(L);
for(i=1;i<=L.length;i++)
printf("%3d ",L.r[i]);
printf("\n");
printf("归并排序的结果为:\n");
MergeSort(L1);
for(i=1;i<=L1.length;i++)
printf("%3d ",L1.r[i]);
printf("\n");
}
测试结果
输入学生记录个数：
0
输入学生成绩:(格式为整数：a,b,c,d)
0,80,50,85,86,91,70,60,80,65
直接插入排序的结果:
50 60 65 70 80 80 85 86 90 91
归并排序的结果为:
归并排序过程为:
0 90
0 80 90
5 86
0 80 85 86 90
0 91
0 70 91
5 80
0 65 70 80 91
0 60 65 70 80 80 85 86 90 91
归并排序的结果为:
50 60 65 70 80 80 85 86 90 91
ress any key to continue
