[每日C] QuickSort 演算法速覽

 使用 QuickSort 排序

接下來就是重頭戲了，第一步，我們要先做出可以一直把陣列切成一半的函式（function），像這樣的動作，小獅覺得用遞迴（recursive）是一個簡單又有效的方法！，所以我們寫了一個函式（function）叫 quickStep（quick sort step 的縮寫），然後讓他不斷呼叫自己，做出切割的效果

void quickStep(int* array, int start, int stop)
{
    int middle = (stop - start)/2+start;
    quickStep(array, start, middle);
    quickStep(array, middle+1, stop);
}

注意到了嗎？光是這樣的話會停不下來的！因為它會在 quickStep(array, 0, 0) 不斷重複，所以我們要加入停止條件，就像所有其他的迴圈一樣！

而我們的條件就是在執行到一個區塊只有一個元素（start 和 stop相等）時停下，再加上一個 printf() 印出來看看效果！

void quickStep(int* array, int start, int stop)
{
    if (stop-start > 0)
    {
        printf("  quickStep(array, %d, %d)\n", start, stop);
        int middle = (stop - start)/2+start;
        quickStep(array, start, middle);
        quickStep(array, middle+1, stop);
    }
}

結果：

  quickStep(array, 0, 9)
  quickStep(array, 0, 4)
  quickStep(array, 0, 2)
  quickStep(array, 0, 1)
  quickStep(array, 3, 4)
  quickStep(array, 5, 9)
  quickStep(array, 5, 7)
  quickStep(array, 5, 6)
  quickStep(array, 8, 9)

看起來成功了，接下來我們要做的是把一個一個區塊的東西排好，較大的放在前面，較小的放在後面，這次為了美觀，小獅把這部分獨立出來寫！

void quickSortElement(int* array, int start, int stop)

▲ 一樣傳入 陣列指標（int* array）、起始位置索引（int start） 和 結束位置索引（int stop）

在這裡，中間點（pivot）的選擇是個有趣的課題，因為這關係到整個 QuickSort 的效率，試想，若是我們給它一個由大到小的陣列，它豈不是幾乎每個元素都要跑過一次嗎？（因為是以排序後的 pivot 位置做切割）

所以，為了避免這個問題，一般會建議使用陣列的中間作為 pivot，畢竟 pivot 指的可是中間”數值”而不是”位置”

int middle = (stop - start)/2+start;

▲ 一樣的方法算出中間點

讓我們把問題簡化，我們要做的是把比中間點大的放在前面，比中間點小的放在後面，所以我們就用一個 for 迴圈從頭看到尾，看到比中間點（pivot）小的就放到前面，從陣列的第一個格子開始放起。

int middle = (stop - start)/2+start;
int pivotValue = array[middle];

int storeIntex = start;
for (int i=start; i<=stop; i++)
{
    if (array[i] > pivotValue)
    {
        printf("\tYes [%d<=>%d]\n", array[i], array[storeIntex]);
        swapNode(array, i, storeIntex);
        storeIntex++;
    }
}

同時，為了確保中間點（pivot）一定緊接在後面，我們在一開始就先把它放在最後面，並將比較條件改為”比中間點大 或 一樣大的放在前面”

int middle = (stop - start)/2+start;
int pivotValue = array[middle];

swapNode(array, middle, stop);
// move pivot point to end

int storeIntex = start;
for (int i=start; i<=stop; i++)
{
    if (array[i] >= pivotValue)
    {
        printf("\tYes [%d<=>%d]\n", array[i], array[storeIntex]);
        swapNode(array, i, storeIntex);
        storeIntex++;
    }
}

等等，各位發現了嗎？我們有一個地方忘記改，我們沒有把 piovt 的最後位置告訴負責切割的 quickStep()！

所以我們把它改成

int quickSortElement(int* array, int start, int stop)
{
    /* 剛才那一串 */
    return storeIntex-1;
}

然後 quickStep() 改成

void quickStep(int* array, int start, int stop)
{
    if (stop-start > 0)
    {
        printf("  quickStep(array, %d, %d)\n", start, stop);
        int middle = quickSortElement(array, start, stop);
        quickStep(array, start, middle-1);
        quickStep(array, middle+1, stop);
    }
}

▲ 用 pivot 的最後位置作為切割時的基準！

但是這樣實在是太難用了，哪有人呼叫 QuickSort 的時候還要指定開始跟結束索引（index）的啦~，當然是排序整個啊！所以我們在 QuickStep() 外面再包一層（這也是為什麼我一開始不叫他 QuickSort 的原因，埋梗埋好久）

void quickSort(int* array, int size)
{
    quickStep(array, 0, size-1);
}

馬上來測試一下，在主程式加入以下呼叫

quickSort(arrayToSort, SIZE);
printf("After Sort:\n");
printArray(arrayToSort, SIZE);

完成~ Ya~！

（後面還有原始碼和執行結果）