快速排序的總結(jié)

快速排序的思想是分而治之，利用遞歸達(dá)到快速排序的效果

首先要選定一個基準(zhǔn)數(shù)，一般選擇最左邊的數(shù)為基準(zhǔn)數(shù)，排序的目標(biāo)就是讓這個基準(zhǔn)數(shù)的左邊全小于這個基準(zhǔn)數(shù)，右邊全大于這個基準(zhǔn)數(shù)。然后以這個基準(zhǔn)數(shù)為分隔線，在左右兩側(cè)再次調(diào)用這個排序的函數(shù)，直到全部有序。簡述過程：

以  8 9 4 7 2 6 首選

1. 選擇兩個哨兵 i，j 分別指向8,6,基準(zhǔn)數(shù)為8

2.從j哨兵開始，因為j指向的6小于基準(zhǔn)數(shù)8，不符合j指向的數(shù)都要大于8的要求，所以將j指向的數(shù)覆蓋i指向的數(shù)，同時i指向的數(shù)變成9

6 9 4 7 2 6

3.此時i指向9大于基準(zhǔn)數(shù)8，不符合基準(zhǔn)數(shù)左邊的都要小于基準(zhǔn)數(shù)，右邊的都要大于基準(zhǔn)數(shù)，所以i指向的數(shù)覆蓋j指向的數(shù)，同時j--,j指向7

6 9 4 7 2 9

重復(fù)以上步驟，直到 哨兵i 和 哨兵j相遇

4.最后一步將基準(zhǔn)值放到中間 

代碼實(shí)現(xiàn)：

void QuickSort(int a[], int low, int high)

{

int i = low, j = high;//每次i,j都指向最低一個元素，和最高一個元素

int temp = a[low];//每次選擇最左邊的數(shù)為基準(zhǔn)數(shù)

while(i < j)//每次循環(huán)結(jié)束的條件是 i == j

{

while(i < j && a[j] >= temp) j--;//先從左邊開始，找到小于基準(zhǔn)數(shù)的數(shù)

if(i < j){

a[i] = a[j];

i++;

}//和i指向的數(shù)交換

while(i < j && a[i] <= temp) i++;//找到基準(zhǔn)數(shù)左邊大于基準(zhǔn)數(shù)的數(shù)

if(i < j){

a[j] = a[i];

j--;

}//換到基準(zhǔn)數(shù)右邊去

}//以上執(zhí)行完后，將基準(zhǔn)數(shù)放到中間

a[i] = temp;

if(low < i)//如果是基準(zhǔn)數(shù)左邊的話

     QuickSort(a, low, i-1);//將最高位i-1

if(i < high)//如果是基準(zhǔn)數(shù)右邊的話

QuickSort(a, j+1, high);//最低位為基準(zhǔn)位+1

}