快速排序实验报告.doc

南京邮电大学通达学院
实验报告

实验名称： 快速排序算法

课程名称：微型计算机原理与接口技术

姓名 班级学号： 钱煜中
142501
14250120

实验时间： 2016.12.2
快速排序原理

一、 实验原理：
快速排序算法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）的值。具体第一次分区过程如下：

因此，第一次分区，以69为分界点，结果为:
a’= [14, 58, 22, 48, 13, 38, 45, 69, 93, 81, 79, 72]。
二、 实验代码
#include <stdio.h>

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);
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;
}
}
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;
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, 93, 14, 45, 58, 79, 72};
int b[10][12];
int y=0,k,x=0,z=0;
printf(" 初始序列为 ");
for(k=0;k<12;k++)
{
printf("%3d",a[k] );
}
printf("\n");
digui(a,0,11,&x,b,&z);
for(y=1;y<z+1;y++)
{
printf("第%2d次后的数组为",y);
for(k=0;k<12;k++)
printf("%3d",b[y-1][k]);
printf("\n");
}

}

三、 实验数据（给出实验结果）
对序列a = [38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72]
38 81 22 48 13 69 93 14 45 58 79 72
38 14 22 48 13 69 93 81 45 58 79 72
38 14 22 13 48 69 93 81 45 58 79 72
进行快速排序，其中，以序列的首元素作为排序的分界点。输出结果要求：输出每一次分区后的结果以及最终排序结果。

四、 实验总结（问题、解决方法、心得体会等）
这次实验我做了很久，重新编写了算法很多次。最开始我对算法的理解不够深，在递归自调用的时候没有想通上下界其实在递归下一层的时候下一层是知道上一层的上下界的，只要排序算法里返还一个最好作为比较值的位置就可以了。一开始排序算法写完就把每次数输出出来，知道后来和同学讨论正确答案是排序了多少次，才想想到我是把每个区排完后的情况，而其实我想输出的是每次排序后数组情况。可是一开始进入的就是左半区的左半区的左半区。。。反正一次是无法输出全部的，因为右半区还没有算。思考了很久，我决定建立一个二维数组，第一行是第一次后的数组，第二行是第二次后的数组。可是如何确定现在是第几次？我建立了一个指针，每次进入递归一层就会+1，每次出递归就会-1，这样就知道这次排序后的数是放在第几次也就是第几层。但是输出的时候还是不知道到底有几行被写入了数，于是又建立了一个指针，储存递归层数最多的时候是几，最后终于完成了算法。