《大话数据结构》第9章 排序 9.9 快速排序（上）
9.9.1 快速排序介绍
终于我们的高手要登场了，如果将来你工作后，你的老板要让你写个排序算法，而你会的算法中竟然没有快速排序，我想你还是不要声张，偷偷去把快速排序算法找来敲进电脑，这样至少你不至于被大伙儿取笑。
事实上，不论是C++ STL、Java SDK或者.NET FrameWork SDK等开发工具包中的源代码里都能找到它的某种实现版本。
快速排序算法最早由图灵奖获得者Tony Hoare设计出来的，他在形式化方法理论，以及ALGOL60 编程语言的发明都有卓越的贡献，是上世纪最伟大的计算机科学家之一。而这快速排序算法只是他众多贡献中的一个小发明而已。
更牛的是，我们现在要学习的这个快速排序算法，被列为20世纪10大算法之一。我们这些玩编程的人还有什么理由不去学习它呢？
html" target=_blank>希尔排序相当于直接插入排序的升级，它们同属于插入排序类，堆排序相当于简单选择排序的升级，它们同属于选择排序类。而快速排序其实就是我们前面认为最慢的冒泡排序的升级，它们都属于交换排序类。即它也是通过不断的比较和移动交换来实现排序的，只不过它的实现，增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动交换次数。
9.9.2 快速排序算法
快速排序（Quick Sort）的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
从字面上感觉不出它的好处来。假设现在要对数组{50,10,90,30,70,40,80,60,20}进行排序。我们通过代码的讲解来学习快速排序的精妙。
我们来看代码。/* 对顺序表L作快速排序 */
void QuickSort(SqList *L)
{
QSort(L,1,L->length);
}又是一句代码，和归并排序一样，由于需要递归调用，因此我们外封装了一个函数。现在我们来看QSort的实现。
/* 对顺序表L中的子序列L->r[low..high]作快速排序 */
void QSort(SqList *L,int low,int high)
{
int pivot;
if(low<high)
{
pivot=Partition(L,low,high); /* 将L->r[low..high]一分为二，算出枢轴值pivot */
QSort(L,low,pivot-1); /* 对低子表递归排序 */
QSort(L,pivot+1,high); /* 对高子表递归排序 */
}
}从这里，你应该能理解前面代码“QSort(L,1,L->length);”中1和L->length代码的意思了，它就是当前待排序的序列最小下标值low和最大下标值high。
这一段代码的核心是“pivot=Partition(L,low,high);”在执行它之前，L.r的数组值为{50,10,90,30,70,40,80,60,20}。Partition函数要做的，就是先选取当中的一个关键字，比如选择第一个关键字50，然后想尽办法将它放到一个位置，使得它左边的值都比它小，右边的值比它大。我们将这样的关键字称为枢轴（pivot）。
在经过Partition(L,1,9)的执行之后，数组变成{20,10,40,30,50,70,80,60,90}，并返回值5给pivot，数字5表明50放置在数组下标为5的位置。此时，计算机把原来的数组变成了两个位于50左和右小数组{20,10,40,30}和{70,80,60,90}，而后的递归调用“QSort(L,1,5-1);”和“QSort(L,5+1,9);”语句，其实就是在对{20,10,40,30}和{70,80,60,90}分别进行同样的Partition操作，直到顺序全部正确为止。
到了这里，应该说理解起来还不算困难。下面我们就来看看快速排序最关键的Partition函数实现是怎么样的。/* 交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置 */
/* 此时在它之前(后)的记录均不大(小)于它。 */
1 int Partition(SqList *L,int low,int high)
2 {
3 int pivotkey;
4 pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */补充：综合编程 , 其他综合 ,
