文档介绍：2021年快速排序实验报告
2021年快速排序实验报告
1 / 12
2021年快速排序实验报告
南京邮电大学通达学院
试验汇报
试验名称: 快速排序算法
课程名称: 微型计算机原理与接口技术
姓名 班级学号: 钱煜中
142501
14250120
试验时间: .
2021年快速排序实验报告
2021年快速排序实验报告
2 / 12
2021年快速排序实验报告
快速排序原理
试验原理:
快速排序算法quick sort关键是利用分治递归思想进行排序方法。它原理是首先从待排序原始序列a[p,…,r]中选择一个元素a[q]作为分界点（pivot）, 然后将序列分为两个子序列, 左边子序列a[p,…,q-1]元素值都小于分界点m, 右边子序列a[q+1,…,r]元素值都大于分界点值, 此时得到序列命名为a’, 而a[q]应该处于其排好序后正确位置。然后利用递归思想, 对左右两个子序列a[p,…,q-1]和a[q+1,…,r]再分别进行排序, 直到子序列长度为1结束, 序列有序。
其中, 选择a中基准分界点方法有多个, 或者选择序列首元素a[p], 或者选择序列尾元素a[r], 或者选择序列中间位置元素a[(p+r)/2], 或者取这三个元素根据大小排序后中间值。
例子:
a = [38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72], 取[(left+right)/2]处元素作为分界点（pivot）值。具体第一次分区过程以下:
2021年快速排序实验报告
2021年快速排序实验报告
3 / 12
2021年快速排序实验报告
所以, 第一次分区, 以69为分界点, 结果为:
a’= [14, 58, 22, 48, 13, 38, 45, 69, 93, 81, 79, 72]。
试验代码
#include <>
int fast_sort(int *a,int i,int j,int *p,int **b)
{
int k,temp,f,g;
g=*p;
g=(12*g)-12;
//intf("成功进入快速排序 g=%d\n",g);
2021年快速排序实验报告
2021年快速排序实验报告
5 / 12
2021年快速排序实验报告
k=i;
i++;
for(;i<j;)
{
for(;a[j]>a[k]&&i<j;)
{
j--;
}
for(;a[i]<a[k]&&i<j;)
{
i++;
}
//intf("i=%d\n",i);
if(i==j)
break;
if(i<j);
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
2021年快速排序实验报告
2021年快速排序实验报告
6 / 12
2021年快速排序实验报告
}
if(a[k]>a[j])
{
temp=a[k];
a[k]=a[j];
a[j]=temp;
}
//r(f=0;f<12;f++)
//
//intf("%3d",a[f]);
//
//printf("排序成功 \n");
for(f=0;f<12;f++)
{
*(b+g+f)=a[f];
}
return j;
}
void digui(int *a,int i,int j,int *p,int **b,int *z)
{
int k;
2021年快速排序实验报告
2021年快速排序实验报告
7 / 12
2021年快速排序实验报告
if(i<j)
{
//intf("成功进入递归 p=%d\n",*p);
*p=*p+1;
k=fast_sort(a,i,j,p,b);
digui(a,i,k-1,p,b,z);
digui(a,k+1,j,p,b,z);
if(*p>*z)
*z=*p;
//printf("z=%d\np=%d",*z,*p);
*p=*p-1;
}
}
void main()
{
int a[]={38, 81, 22, 48, 13, 69, 9