快速排序实验报告
- 格式:doc
- 大小:157.50 KB
- 文档页数:10
南京邮电大学通达学院
实验报告
实验名称:快速排序算法
课程名称:微型计算机原理与接口技术
姓名班级学号:钱煜中
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
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++;