快速排序是对起泡排序的一种改进：在起泡排序中，记录的比较和移动是在相邻位置进行的，记录每次交换只能后移一个位置，因而总的比较次数和移动次数较多。在快速排序中，记录的比较和移动是从两段向中间进行的，关键码较大的记录一次就能从前面移动到后面，关键码较小的记录一次就能从后面移动到前面，记录移动的距离较远，从而减少了总的比较次数和移动次数。
基本思想：首先选一个轴值（povit，即比较的基准），将待排序记录划分为独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。
//快速排序算法
//一次划分算法
int Partition(int r[], int first, int end)
{
int i = first; //初始化
int j = end; //初始化
while (i < j)
{
while (i < j&&r[i] <= r[j]) //右侧扫描
j--;
if (i < j)
{
int temp = r[i];
r[i] = r[j];
r[j] = temp; //将较小的交换到前面
i++;
}
while (i < j&&r[i] <= r[j])//左侧扫描
i++;
if (i < j) //将较大的交换到后面
{
int temp = r[i];
r[i] = r[j];
r[j] = temp;
j--;
}
}
return i; //i为轴值记录的最终位置
}
void QuickSort(int r[], int first, int end)
{
if (first < end) //区间长度大于1，执行一次划分，否则递归结束
{
int pivot = Partition(r, first, end); //一次划分
QuickSort(r, first, pivot - 1); //递归地对左侧子序列进行快速排序
QuickSort(r, pivot + 1, end); //递归地对右侧子序列进行快速排序
}
}
