快速排序是對冒泡法排序的一種改進。
快速排序算法 的基本思想是：將所要進行排序的數分為左右兩個部分，其中一部分的所有數據都比另外一 部分的數據小，然後將所分得的兩部分數據進行同樣的劃分，重復執行以上的劃分操作，直 到所有要進行排序的數據變為有序為止。
可能僅根據基本思想對快速排序的認識並不深，接下來以對n個無序數列A[0], A[1]…, A[n-1]采用快速排序方法進行升序排列為例進行講解。
(1)定義兩個變量low和high，將low、high分別設置為要進行排序的序列的起始元素和最後一個元素的下標。第一次，low和high的取值分別為0和n-1，接下來的每次取值由劃分得到的序列起始元素和最後一個元素的下標來決定。
(2)定義一個變量key，接下來以key的取值為基准將數組A劃分為左右兩個部分，通 常，key值為要進行排序序列的第一個元素值。第一次的取值為A[0]，以後毎次取值由要劃 分序列的起始元素決定。
(3)從high所指向的數組元素開始向左掃描，掃描的同時將下標為high的數組元素依次與劃分基准值key進行比較操作，直到high不大於low或找到第一個小於基准值key的數組元素，然後將該值賦值給low所指向的數組元素，同時將low右移一個位置。
(4)如果low依然小於high，那麼由low所指向的數組元素開始向右掃描，掃描的同時將下標為low的數組元素值依次與劃分的基准值key進行比較操作，直到low不小於high或找到第一個大於基准值key的數組元素，然後將該值賦給high所指向的數組元素，同時將high左移一個位置。
(5)重復步驟(3) (4)，直到low的植不小於high為止，這時成功劃分後得到的左右兩部分分別為A[low……pos-1]和A[pos+1……high]，其中，pos下標所對應的數組元素的值就是進行劃分的基准值key，所以在劃分結束時還要將下標為pos的數組元素賦值 為 key。
(6)將劃分得到的左右兩部分A[low……pos-1]和A[pos+1……high]繼續采用以上操作步驟進行劃分，直到得到有序序列為止。
為了能夠加深讀者的理解，接下來通過一段代碼來了解快速排序的具體實現方法。
#include <stdio.h>
#include <stdlib.h>
#define N 6
int partition(int arr[], int low, int high){
int key;
key = arr[low];
while(low<high){
while(low <high && arr[high]>= key )
high--;
if(low<high)
arr[low++] = arr[high];
while( low<high && arr[low]<=key )
low++;
if(low<high)
arr[high--] = arr[low];
}
arr[low] = key;
return low;
}
void quick_sort(int arr[], int start, int end){
int pos;
if (start<end){
pos = partition(arr, start, end);
quick_sort(arr,start,pos-1);
quick_sort(arr,pos+1,end);
}
return;
}
int main(void){
int i;
int arr[N]={32,12,7, 78, 23,45};
printf("排序前 \n");
for(i=0;i<N;i++)
printf("%d\t",arr[i]);
quick_sort(arr,0,N-1);
printf("\n 排序後 \n");
for(i=0; i<N; i++)
printf("%d\t", arr[i]);
printf ("\n");
system("pause");
return 0;
}
運行結果：
排序前
32 12 7 78 23 45
排序後
7 12 23 32 45 78
在上面的代碼中，根據前面介紹的步驟一步步實現了快速排序算法。接下來通過示意圖來演示第一次劃分操作。
在第一次劃分操作中，先進行初始設置，key的值是進行劃分的基准，其值為要劃分數 組的第一個元素值，在上面的排序序列中為第一個元素值32，同時將low設置為要排序數組中第一個元素的下標，第一次排序操作時其值為0，將high設置為要排序序列最後一個 元素的下標，在上面的排序序列中其第一次取值為5。先將下標為high的數組元素與key進行比較，由於該元素值大於key，因此high向左移動一個位置繼續掃描。由於接下來的值為 23，小於key的值，因此將23賦值給下標為low所指向的數組元素。接下來將low右移一 個位置，將low所指向的數組元素的值與key進行比較，由干接下來的12、7都小於key， 因此low繼續右移掃描，直至下標low所指向的數組元素的值為78即大於key為止，將78賦值給下標為high所指向的數組元素，同時將high左移一個位置。接下來由於low不再小於high，劃分結束。需要注意的是，在進行劃分的過程中，都是將掃描的值與key的值進行對比，如果小於key，那麼將該值賦值給數組中的另外一個元素，而該元素的值並沒有改變。 從圖中可以看出這一點，所以需要在劃分的最後將作為劃分基准的key值賦值給下標為 pos的數組元素，這個元素不再參與接下來的劃分操作。
第一次劃分操作
第一輪劃分結束後，得到了左右兩部分序列A[0]、A[1]、A[2]和A[4]、A[5]，繼續進 行劃分，即對毎輪劃分後得到的兩部分序列繼續劃分，直至得到有序序列為止。
