文档介绍：: .
快速排序实验报告
南京邮电大学通达学院
实验报告
实验名称：快速排序算法课程名称：微型计: .
快速排序实验报告
南京邮电大学通达学院
实验报告
实验名称：快速排序算法课程名称：微型计算机原理与接口技
姓名班级学号：钱煜中14250114250120实验时间：
一、实验原理：
快速排序算法quicksort主要是利用分治递归的思想进行排序的方法。它的原理是首先从待排序的原始序列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)的值。具体第一次分区过程如下：
leftJefHl
j
rightI
|38|81
|22|
48
113
69|
93
14
45
|58|
79
72
tj
hi■hi■一曲
to
[69(al*
22
48
13
38
93
14
45
58"
79'
72*
Id-_fti
[69|58
22"
48*
13*
»n■
38
93,
14|45‘
81
|79
72
lo
[69158
22
48
13
38
45
1广|93・
91
79
72
TT
hi
\1458
22
48
13
38
45
69|93
81i
79
72
因此，第一次分区，以69为分界点，结果为：
a'=[14,58,22,48,13,38,45,69,93,81,79,72]二、实验代码#include<>intfast_sort(int*a,inti,intj,int*p,int**b)(
intk,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)bre