1 绪论快速排序（quicksort）是分治（divide and conquer）法的一个典型例子。
快速排序（Quicksort）是对冒泡排序的一种改进。
由C. A. R. Hoare在1962 年提出。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序算法具有良好的平均性能，因此它在实际中常常是首选的排序算法。
本次任务主要以快速排序算法实现对任意数字序列的排序，并解决书本P59页2-26问题：O n n 试说明如何修改快速排序算法，使它在最坏情况下的计算时间为(log)所选编程语言为C语言。
2 快速排序算法2.1快速排序算法简介快速排序算法是基于分治策略的排序算法。
即对于输入的子数组a[p:r],按以下三个步骤进行排序。
（1）分解：以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q]和a[q+1:r]，使a[p:q-1]中任何一个元素小于等于a[q]，而a[q+1:r]中任何一个元素大于等于a[q]。
下标q在划分过程中确定。
（2）递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。
（3）合并：由于对a[p:q-1]和a[q+1:r]的排序是就地进行的，所以在a[p:q-1]和a[q+1:r]都已排好的序后，不需要执行任何计算，a[p:r]就已排好序。
2.2图1 快速排序算法流程图开始定义标志位tempi<jtemp=r[i] i!=j j>i&&r[j].key>temp.keyj-- i<j r[i]=r[j];i++ j>i&&r[i].key>temp .key i++ i<jr[j]=r[i];j-- r[i]=temp quicksort(r,I,i-1) quicksort(r,i+1,j)结束 N Y Y N N Y2.3快速排序算法的算法实现第一趟处理整个待排序列，选取其中的一个记录，通常选取第一个记录，以该记录的关键字值为基准，通过一趟快速排序将待排序列分割成独立的两个部分，前一部分记录的关键字比基准记录的关键字小，后一部分记录的关键字比基准记录的关键字大，基准记录得到了它在整个序列中的最终位置并被存放好，这个过程称为一趟快速排序。
第二趟即分别对分割成两部分的子序列再进行快速排序，这样两部分子序列中的基准记录也得到了最终在序列中的位置并被存放好，又分别分割出独立的两个子序列。
这是一个递归的过程，不断进行下去，直至每个待排子序列中都只有一个记录是为止，此时整个待排序列已排好序，排序算法结束。
快速排序的过程：（1）初始化。
取第一个记录作为基准，设置两个整型指针i，j，分别指向将要与基准记录进行比较的左侧记录位置和右侧记录位置。
最开始从右侧比较，当发生交换操作后，再从左侧比较。
（2）用基准记录与右侧记录进行比较。
即与指针j指向的记录进行比较，如果右侧记录的关键字值大，则继续与右侧前一个记录进行比较，即j减1后，再用基准元素与j所指向的记录比较，若右侧的记录小，则将基准记录与j所指向的记录进行交换。
（3）用基准记录与左侧记录进行比较。
即与指针i指向的记录进行比较，如果左侧记录的关键字值小，则继续与左侧后一个记录进行比较，即i加1后，再用基准记录与i指向的记录比较，若左侧的记录大，则将基准记录与i指向的记录比较。
（4）右侧比较与左侧比较交替重复进行，直到指针i与j指向同一位置，即指向基准记录最终的位置。
可实现的快速排序算法如下：void QuickSort(int a[],int p,int r){i f(p<r){int q=Partition(a,p,r);QuickSort(a,p,q-1);Q uickSort(a,q+1,r);}}对含有n个元素的数组a[0;n-1]进行快速排序只要调用QuickSort(a,0,n-1)即可。
上述算法中的函数Partition，以确定的一个基准元素a[p]对子数组a[p:r]进行划分，它是快速排序算法的关键。
int Partition(int a[],int p,int r){i nt i=p,j=r+1;i nt x=a[p];w hile(true){while(a[++i]<x&&i<r);while(a[--j]>x);if(i>=j) break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;return j;}Partition对a[p:r]进行划分时，以元素x=a[p]作为划分的基准，分别从左、右两端开始，扩展两个区域a[p:i]和a[j:r],使a[p:i]中元素小于或等于x，而a[j:r]中元素大于或等于x。
初始时，i=p,且j=r+1。
在while循环体中，下标j逐渐减小，i逐渐增大，，直到a[i]>=x>=a[j]。
此时若i<j，就应该交换a[i]与a[j]的位置，扩展左右两个区域。
while循环重复至i>=j时结束。
这时a[p:r]已被划分成a[p:q-1],a[q]和a[q+1:r],且满足a[p:q-1]中元素不大于a[q+1：r]中元素。
在Partition结束时返回划分点q=j。
3 程序运行运行程序，任意输入一个乱序数组，例如：5 4 18 9 56 11 237 46 14运行得到排序后的结果如下图：图2 程序运行结果4问题解答O n n是很困难的，完全保证使快速排序算法在最坏情况下的计算时间为(log)但可以采用一些办法来消除算法的退化结构，比如课本上的随机选择策略等。
鉴于在平时生活中的数据排序，其数据往往带有规律性。
在中值的选择策略上，我们比较一下第一个，最后一个，以及中间一个的值，以这3个值中位于中间的那个来进行划分，这样就能使快速排序避免了大多数的最坏情况，即使是对于两边小中间大的特殊情况，这个方法也有其作用——在第一遍排序时打乱这个特殊情况。
因此，这个算法在实际运用中是比较好的一种快速排序，修改程序如下：template <class Type>int partition (Type a[],int p,int r){ int i=p,j=r+1;Type x=a[p];while(1){ while(a[++i]<x);while(a[--j]>x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;return j;}int BalancePartion(Type a[],int p,int r){ int i,m;m=(p+r)/2;switch(1){ case(a[p]<=a[m]&&a[p]>=a[r])||(a[p]>=a[m]&&a[p]<=a[r]):i=p;break;case(a[m]<=a[p]&&a[m]>=a[r])||(a[m]>=a[p]&&a[m]<=a[r]):i=m;break;case(a[r]<=a[m]&&a[r]>=a[p])||(a[r]>=a[m]&&a[r]<=a[p]):i=r;break;}Swap(a[i],a[p]);return Partition(a,p,r);}void BalanceQuickSort(Type a[],int p,int r) { if(p<r){ int q=BalancePartition(a,p,r);BalanceQuickSort(a,p,q-1);BalanceQuickSort(a,q+1,r);}}5课程设计总结及心得课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程. 回顾此次快速排序算法演示课程设计，至今我仍感慨颇多，的确，从选题到定稿，从理论到实践，在整整两星期的日子里，可以说得是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。
在做程序的过程中遇到了很多问题，有的是知识存储不足，有的是考虑不够周全，之所以能够顺利实现基本功功能，离不开老师和同学的大力相助。
此外，通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。
快速排序的实现6 参考文献[1] 王晓东．算法设计与分析（第二版）．北京：清华大学出版社，2006.11[2] 霍红卫．算法设计与分析（第二版）．西安电子科技大学出版社，2008.10[3] 张白一．面向对象程序设计——Java（第二版）．西安电子科技大学出版社，2012.07[4] 张铭、王腾蛟、赵海燕．数据结构与算法．高等教育出版社，2003.03[5] 林智扬、范明翔、陈锦辉．深入浅出Java Swing程序设计．中国铁道出版社，2004.0511/ 11。