快速排序，實(shí)際上，確實(shí)需要兩個(gè)變量，指向數(shù)組的首段和尾段，也確實(shí)需要一個(gè)基準(zhǔn)來(lái)進(jìn)行比較，結(jié)果就是，讓比基準(zhǔn)大的，都在基準(zhǔn)的右邊，比基準(zhǔn)小的都在基準(zhǔn)的左邊，這樣再分別對(duì)基準(zhǔn)左右兩端的數(shù)組進(jìn)行快速排序。直到只剩下一個(gè)數(shù)據(jù)。

廢話不多說(shuō)，上例子。

60 80 55 40 42 85

i 指向 最左端，j 指向最右端?；鶞?zhǔn)為60 如下

60   80  55   40   42  85  
i                       j

j 從 右向左，查找第一個(gè)比60小的數(shù)。查找結(jié)果是42, 42去 i 指向的位置。如下

42   80  55   40   null  85  
i                    j

i 從左向右，查找第一個(gè)比60大的數(shù)。查找結(jié)果是80,80去 j 指向的位置。如下

42   null  55   40   80  85  
      i               j

j 繼續(xù)查找比60小的數(shù)。查找結(jié)果是40， 40 ，去 i 指向的位置。如下

42   40  55   null   80  85  
      i         j

i 繼續(xù)查找比60大的數(shù)，直到與 j 遇見(jiàn)，都沒(méi)有找到，因此 將基準(zhǔn)60放入 i 和 j共同指向的位置。第一趟結(jié)束。如下

42   40  55   60   80  85  
              ij

再一次對(duì) 42 40 55 進(jìn)行如上的操作，對(duì) 80 85 也進(jìn)行如上的操作。如此循環(huán)，直至，操作的數(shù)組中只有一個(gè)元素。

code如下：

int Partition(int arr[],int left,int right){
    int i = left;               //left指向最左邊 
    int j = right;          //right指向最右邊 
    int key = arr[left];            //基準(zhǔn) 為數(shù)組第一個(gè)元素 
    int temp;
    while(i<j){         // left只能小于right，不可能大于right 
        while(i<j&&arr[j]>key){ //我們需要找比key小的數(shù)，所以，只有當(dāng)比key大的時(shí)候，j才移動(dòng)。 
            j--;
        }
        printf("%d,%d\n",i,j);
        if(i<j)
            arr[i++] = arr[j];
        while(i<j&&arr[i]<key){ //我們需要找比key大的數(shù)，所以，只有當(dāng)比key小的時(shí)候，j才移動(dòng)。
            i++;
        } 
        if(i<j)
            arr[j--] = arr[i];
    }
    arr[i] = key;
    return i;
}
void QuickSort(int arr[],int left,int right){
    if(left<right){
        int pivotloc;
        pivotloc = Partition(arr,left,right);
        QuickSort(arr,left,pivotloc-1);
        QuickSort(arr,pivotloc+1,right);
    }
    
}