快速排序是对冒泡排序的一种改进。它所采用的方法是通过一轮排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别再进行快速排序，以此达到整个数据变成有序序列。

快速排序的算法过程可以使用递归方法进行。

快速排序的基本思想方法是：设要排序的数组是a[0]……a[n-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面。

例如：定义待排序的数组int a[]={49，38，65，97，76，13，27}；取初始关键数据x=49，即x=a[0]；初始状态为{49386597761327}。

进行一次快速排序之后，划分为两个子序列：{273813}49{769765}。

之后再分别对前后两个子序列进行快速排序。

子序列{273813}，以第1个数27为关键数据，排序后变成{132738}，完成排序。

子序列{769765}，以第1个数76为关键数据，排序后变成{657697}，完成排序。

程序实现过程，可以是这样的：

1）设置两个变量low和high作为子序列的左右边界，第1轮排序开始的时候low=0，high=n-1；其中n为数组元素个数。

2）以第0个数组元素作为关键数据，赋值给x，即x=a[0]。

3）从high位置开始由后开始向前搜索（high--），找到第1个小于x的值，让该值与x交换。

4）从low开始向后搜索（low++），找到第1个大于x的值，让该值与x交换。

5）重复第3）、4）步，直到low==high。

下面对以上过程进行分解说明。

设数组：int a[]={49，38，65，97，76，13，27}；

这时有：a.length=7；low=0；high=6；x=a[0]=47；

按照算法步骤3），从后面high=6开始找小于x的数，这时有a[6]=27，交换。交换后结果为：

27 38 65 97 76 13 49(www.daowen.com)

按照算法步骤4），从前面low=0开始找大于x的值，这时有a[2]=65，交换。交换后结果为

27 38 49 97 76 13 65

按照算法步骤3），从后面high=5开始找小于x的数，这时有a[5]=13，交换。交换后结果为

27 38 13 97 76 49 65

按照算法步骤4），从前面low=1开始找大于x的值，这时有a[3]=97，交换。交换后结果为

27 38 13 49 76 97 65

同样，以high =4及low=2，继续再次查找交换。当high==low时第1轮结束。结果为

27 38 13 49 76 97 65

这时所有大于49的数全部在49的后面，所有小于49的数全部在49的前面。

其后可以使用递归的方法，将前后两个子序列继续完成排序，直到子序列到最小。

【例9-24】 使用快速排序法进行排序。

程序思路：

1)设置两个变量i、j，排序开始的时候：i=0，j=n-1。

2)以第1个数组元素作为关键数据，赋值给x，即x=a[0]。

3)从j开始向前搜索，即南后开始向前搜索（j--），找到第1个小于x的值，让该值与x交换。

4)从i开始向后搜索，即由前开始向后搜索(i++)，找到第1个大于x的值，让该值与x交换。

5)重复第3）、4）步，直到i==j。

程序运行结果：（略，结果同例9-19）