（1）快速排序的基本思想

冒泡排序算法经一趟冒泡只能使一个记录排序到位，快速排序（Quick Sort）是对冒泡法的改进，算法中经一趟操作后，不仅使某个记录排序到位，同时以该记录的关键字为划分标准（称它为划分记录），把记录序列划分为两个子序列。所有关键字比划分记录小的排放到它的前面，大的排放到它的后面。在原序列中除去划分记录后的两个子序列可以分别进行相同的操作，把每个序列再分成两个更小的子序列，直到序列的长度为1，完成排序。整个排序过程可以通过递归来实现。

（2）冒泡排序的步骤

设待排序的记录序列存放在a数组中，一趟快速排序的步骤如下：

1.选取划分记录，通常设定序列中第一个为划分记录，用变量mid暂存划分记录。另外设置序列的起、止下标，不妨设为start和end。

2.设置两个指示记录下标的变量i、j，初值分别指向序列的起、止位置。

3.j从当前位置开始，从后向前扫描，直到a[j].key<mid.key,然后使a[j] 置于a[i]的位置，使i增1，后移一个位置。

4.i 从当前位置开始从前向后扫描，直到a[i].key>=mid.key , 然后使a[i]置于a[j]的位置，使j减1，前移一个位置。

5.重复步骤3、4，直到i和j 相等，然后把划分记录置于a[i]中，这样划分记录排序到位，且把原序列划分为要求的两个子序列。称上述过程为一次划分。

例如，一组记录的关键字序列为{ 40，35，60，38，30，90 }，一趟划分的过程如图9‑1所示，其中划分关键字mid=40。

一趟划分的过程

图中方框内表示其中数据已移走，可以被其他数据覆盖。

（3）快速排序的算法实现

快速排序算法

	void quicksort(NODE a[],int start,int end)
	/*对a[start]到a[end]的记录按关键字进行快速排序*/
	{
	 int i,j;
	 NODE mid;
	 if(start>=end)
	 return;
	 i=start;
	 j=end;
	 mid=a[i];
	 while(i<j) /*一次划分直到i等于j*/
	 {
	 while(i<j &&a[j].key>mid.key)
	 j--;
	 if(i<j)
	 {
	 a[i]=a[j]; /*把a[j]置于a[i]的位置*/
	 i++; /*后移一个位置*/
	 }
	 while(i<j&&a[i].key<=mid.key)
	 i++; /*从前向后扫描，等于划分关键字的记录也跳过*/
	 if(i<j)
	 {
	 a[j]=a[i]; /*把a[i]置于a[j]的位置*/
	 j--; /*前移一个位置*/
	 }
	 }
	 a[i]=mid; /*划分记录到位,一次划分结束*/
	 quicksort(a,start,i-1); /*递归调用对前一子序列划分*/
	 quicksort(a,i+1,end); /*递归调用对后一子序列划分*/
	}

快速排序的时间复杂度取决于所选划分记录，最坏情况是每次划分记录的关键字正好是记录序列中的最大值或最小值，此时它类似于冒泡法,时间复杂度为O(n²)，在平均情况下快速排序时间复杂度为O(nlog₂n)，是目前认为较好的一种内部排序方法。快速排序是不稳定的排序。