快速排序是對起泡排序的一種改進：在起泡排序中辫红，記錄的比較和移動是在相鄰位置進行的锐帜，記錄每次交換只能后移一個位置，因而總的比較次數和移動次數較多拍冠。在快速排序中尿这，記錄的比較和移動是從兩段向中間進行的，關鍵碼較大的記錄一次就能從前面移動到后面庆杜，關鍵碼較小的記錄一次就能從后面移動到前面射众，記錄移動的距離較遠，從而減少了總的比較次數和移動次數晃财。
基本思想：首先選一個軸值（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) //區(qū)間長度大于1，執(zhí)行一次劃分厢洞，否則遞歸結束
{
int pivot = Partition(r, first, end); //一次劃分
QuickSort(r, first, pivot - 1); //遞歸地對左側子序列進行快速排序
QuickSort(r, pivot + 1, end); //遞歸地對右側子序列進行快速排序
}
}
