快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将待排记录分割成独立的两部分其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

假设待排序的序列为{a[l],a[l+1],a[l+2],…,a[r]},首先任意选取一个记录(通常可选中间一个记录作为枢轴或支点),然后重新排列其余记录,将所有关键字小于它的记录都放在左子序列中,所有关键字大于它的记录都放在右子序列中。由此可以将该“支点”记录所在的位置mid作分界线,将序列分割成两个子序列和。这个过程一趟快速排序(或一次划分)。

一趟快速排序的具体做法是:附设两个指针i和j,它们的初始值分别为1和r,设枢轴记录取mid,则首先从j所指位置起向前搜索,找到第一个关键字小于mid的记录,然后从i所指位置起向后搜索,找到第一个关键字大于mid的记录,将他们互相交换,重复这两步直至i>j为止。

代码:

void qsort(int p,int q)
{
if(p>=q) return;
int key=a[p];
int i=p,j=q;
while(i<j)
{
while(a[j]>=key&&i<j) j--;
if(i<j) a[i++]=a[j];
while(a[i]<=key&&i<j) i++;
if(i<j) a[j--]=a[i];
}
a[i]=key;
qsort(p,i-1);
qsort(i+1,q);
}