原理

快速排序一聽名字就覺得很高端，在實際應(yīng)用當(dāng)中快速排序確實也是表現(xiàn)最好的排序算法?？焖倥判螂m然高端，但其實其思想是來自冒泡排序，冒泡排序是通過相鄰元素的比較和交換把最小的冒泡到最頂端，而快速排序是比較和交換小數(shù)和大數(shù)，這樣一來不僅把小數(shù)冒泡到上面同時也把大數(shù)沉到下面。

舉個栗子：對5,3,8,6,4這個無序序列進行快速排序，思路是右指針找比基準數(shù)小的，左指針找比基準數(shù)大的，交換之。

• 5,3,8,6,4 用5作為比較的基準，最終會把5小的移動到5的左邊，比5大的移動到5的右邊。

• 5,3,8,6,4 首先設(shè)置i,j兩個指針分別指向兩端，j指針先掃描（思考一下為什么？）4比5小停止。然后i掃描，8比5大停止。交換i,j位置。

• 5,3,4,6,8 然后j指針再掃描，這時j掃描4時兩指針相遇。停止。然后交換4和基準數(shù)。 4,3,5,6,8 一次劃分后達到了左邊比5小，右邊比5大的目的。之后對左右子序列遞歸排序，最終得到有序序列。

上面留下來了一個問題為什么一定要j指針先動呢？首先這也不是絕對的，這取決于基準數(shù)的位置，因為在最后兩個指針相遇的時候，要交換基準數(shù)到相遇的位置。一般選取第一個數(shù)作為基準數(shù)，那么就是在左邊，所以最后相遇的數(shù)要和基準數(shù)交換，那么相遇的數(shù)一定要比基準數(shù)小。所以j指針先移動才能先找到比基準數(shù)小的數(shù)。

快速排序是不穩(wěn)定的，其時間平均時間復(fù)雜度是O(nlgn)。

鏈接：http://www.imooc.com/article/8633?from=itblog

算法

//思路是右指針找比基準數(shù)小的，左指針找比基準數(shù)大的，交換之。
int partition(int unsorted[], int left, int right) {
    int pivotKey = unsorted[left];
    while (left < right) {
        while (unsorted[right] > pivotKey) {
            right--;
        }
        while (unsorted[left] < pivotKey) {
            left++;
        }
        int temp = unsorted[left];
        unsorted[left] = unsorted[right];
        unsorted[right] = temp;
    }
    unsorted[left] = pivotKey;
    return left;
}
int quicksort(int unsorted[],int left,int right){
    if (left >= right)
        return 0;
    int pivotPos = partition(unsorted,left,right);
    quicksort(unsorted,left,pivotPos-1);
    quicksort(unsorted,pivotPos+1,right);
}