快速排序（雙指針法）

一、快速排序的思想是什麼？

從數組中選取一個元素作為基準值，将待排序的數組分成左右兩部分，左邊的部分小于基準值，右邊的部分大于基準值。左右兩部分繼續如此遞歸下去，不斷分裂，直到待排序數組的元素為1，此時遞歸條件結束。

是以，我們重點關心的就是，在一段待排序數組中選一個基準值（一般選擇待排序數組的第一個元素）；使用左右兩個指針向中間移動，左邊的指針在比基準值大的下标時停下，右邊的指針在比基準小的下标時停下，雙方交換數組元素，繼續向左、向右移動。

這一輪的移動到什麼地方停止呢？那就是在左右指針下标值相等的時候，将這個下标值的元素與基準值元素交換。一輪下來，這個基準值位置确定，就不會再發生改變了。以它為分界線，分成左右兩部分，剩下的排序它都不用參與了。

分開了左右兩段之後，我們把左右段看成各自獨立的待排序數組就好，做法與上面一緻，隻不過此時的待排序數組比較短了。使用遞歸實作就非常友善。

在不斷的分裂過後，待排序數組隻為一個元素的時候，排序就結束了。

二、為什麼要使用快速排序？

從時間複雜度分析，排序一輪的執行次數與冒泡排序類似，一個長度為n的數組執行次數都是n；差别在排序的輪數；假設一個長度為8的數組，冒泡排序不管情況是好還是壞，都是執行7輪（n*n）；對于快速排序，最差的情況才是7輪，一般為3輪（n * 

）.

三、代碼（c語言）

下面是c語言實作代碼，可以參考一下

#include <stdio.h> 

/*
  快速排序，雙指針、遞歸實作 ；固定一個自定義變量，作為資料調換的中轉空間。
*/
/*

int partion(int * num, int startindex, int endindex)
{
    
    int temp, left, right;
    int pivot = num[startindex];
    left = startindex;
    right = endindex;
    while(left != right){
        //從右邊向左邊周遊，大于基準值向左移動，小于基準值停下
        while(left < right && num[right] > pivot){
            right--;
        }
        //從左邊向右邊周遊，小于基準值向右移動，大于于基準值停下
        while(left < right && num[left] <= pivot){
            left++;
        } 
        
        //交換左右指針的值
        if(left < right)
        {
            temp = num[left];
            num[left] = num[right];
            num[right] = temp;    
        }
        
    }
    temp = num[left];
    num[left] = num[startindex];
    num[startindex] = temp;
    return left;
}
*/

/* 挖坑法
   左右指針數值吊換的時候，坑不斷移動
 */ 
int partion(int * num, int startindex, int endindex)
{
    
    int temp, left, right, index;
    int pivot = num[startindex];
    index = startindex;
    left = startindex;
    right = endindex;
    while(left != right){
        while(left < right && num[right] > pivot){
            right--;
        }
        num[index] = num[right];
        index = right;
        
        while(left < right && num[left] <= pivot){
            left++;
        } 
        num[index] = num[left];
        index = left;    
    }
    num[left] = pivot;
    return left;
}

void quicksort(int * num, int startindex, int endindex)
{
    if(startindex >= endindex){
        return ;
    }
    int pivot_index = partion(num, startindex, endindex);
    quicksort(num, startindex, pivot_index - 1);
    quicksort(num, pivot_index+1, endindex);
}

int main()
{
    int num1[] = {6, 1, 2, 7, 9, 3, 4 ,5, 10};
    quicksort(num1,0, 8);
    for(int i = 0; i < 9; i++)
        printf("%d ", num1[i]);
}