C語言中文網 目錄

快速排序算法,C語言快速排序算法詳解

本節介紹一個非常優秀且最常用的排序算法,快速排序算法。這個算法極其重要,初學者一定要掌握。

快速排序尤其適用于對大數據的排序,它的高速和高效無愧于“快速”兩個字。雖然說它是“最常用”的,可對于初學者而言,用它的人卻非常少。因為雖然很快,但它也是邏輯最復雜、最難理解的算法,因為快速排序要用到遞歸和函數調用。

快速排序所采用的思想是分治的思想。所謂分治,就是指以一個數為基準,將序列中的其他數往它兩邊“扔”。以從小到大排序為例,比它小的都“扔”到它的左邊,比它大的都“扔”到它的右邊,然后左右兩邊再分別重復這個操作,不停地分,直至分到每一個分區的基準數的左邊或者右邊都只剩一個數為止。這時排序也就完成了。

所以快速排序的核心思想就是將小的往左“扔”,將大的往右“扔”,只要能實現這個,就與快速排序的思想吻合。從初學者的角度,“小的往左扔大的往右扔”首先能想到的往往是小的往前插,大的往后插。這確實是一個思路,但我們知道,數組是不擅長插入的。這種思路雖然能吻合快速排序的思想,但實現起來就不是“快速”排序,而是“慢速”排序了。所以這種方法是不可行的。于是就有了下面的“舞動算法”。

“舞動算法”的思想是用交換取代插入,大大提高了排序的速度。下面首先詳細地講解一下數組快速排序的過程。

假設序列中有 n 個數,將這 n 個數放到數組 A 中。“舞動算法”中一趟快速排序的算法是:
  1. 設置兩個變量 i、j,排序開始的時候:i=0,j=n–1。
  2. 以數組第一個元素為關鍵數據,賦給變量 key,即 key=A[0]。
  3. 從 j 開始向前搜索,即由后開始向前搜索(j--),找到第一個小于 key 的值 A[j],將 A[j] 和 A[i] 互換。
  4. 然后再從 i 開始向后搜索,即由前開始向后搜索(++i),找到第一個大于 key 的 A[i],將 A[i] 和 A[j] 互換。
  5. 重復第 3、4 步,直到 i=j。此時就能確保序列中所有元素都與 key 比較過了,且 key 的左邊全部是比 key 小的,key 的右邊全部是比 key 大的。

第一輪比較后序列就以 key 為中心分成了左右兩部分,然后分別對左右兩部分分別遞歸執行上面幾個步驟,直到排序結束。

下面列舉一個簡單的例子,比如對如下數組 a 中的元素使用快速排序實現從小到大排序:

35  12  37  -58  54  76  22

1) 首先分別定義 low 和 high 用于存儲數組第一個元素的下標和最后一個元素的下標,即 low=0,high=6。

2) 然后定義 key 用于存放基準數,理論上該基準數可以取序列中的任何一個數。此處就取數組的第一個元素,即把 a[low] 賦給 key。

3) 然后 key 和 a[high] 比較,即 35 和 22 比較,35>22,則它們互換位置:

22  12  37  -58  54  76  35

4) 然后 low++==1,key 和 a[low] 比較,即 35 和 12 比較,12<35,則不用互換位置;繼續 low++==2,然后 key 和 a[low] 比較,即 35 和 37 比較,37>35,則它們互換位置:

22  12  35  -58  54  76  37

5) 然后 high--==5,key 和 a[high] 比較,即 35 和 76 比較,35<76,則不用互換位置;繼續 high--==4,然后 key 和 a[high] 比較,即 35 和 54 比較,35<54,則不用互換位置;繼續 high--==3,然后 key 和 a[high] 比較,即 35 和 -58 比較,35>–58,則它們互換位置:

22  12  -58  35  54  76  37

6) 然后 low++==3,此時 low==high,第一輪比較結束。從最后得到的序列可以看出,35 左邊的都比 35 小,35 右邊的都比 35 大。這樣就以 35 為中心,把原序列分成了左右兩個部分。接下來只需要分別對左右兩個部分分別重復上述操作就行了。

對于人類而言,這個過程確實比前面的排序算法復雜。但對于計算機而言,這個過程卻沒那么復雜。下面來寫一個程序:
# include <stdio.h>
void Swap(int *, int *);  //函數聲明, 交換兩個變量的值
void QuickSort(int *, int, int);  //函數聲明, 快速排序
int main(void)
{
    int i;  //循環變量
    int a[] = {900, 2, -58, 3, 34, 5, 76, 7, 32, 4, 43, 9, 1, 56, 8,-70, 635, -234, 532, 543, 2500};
    QuickSort(a, 0, 20);  /*引用起來很簡單, 0為第一個元素的下標, 20為最后一個元素的下標*/
    printf("最終排序結果為:\n");
    for (i=0; i<21; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}
void Swap(int *p, int *q)
{
    int buf;
    buf = *p;
    *p = *q;
    *q = buf;
    return;
}
void QuickSort(int *a, int low, int high)
{
    int i = low;
    int j = high;
    int key = a[low];
    if (low >= high)  //如果low >= high說明排序結束了
    {
        return ;
    }
    while (low < high)  //該while循環結束一次表示比較了一輪
    {
        while (low < high && key <= a[high])
        {
            --high;  //向前尋找
        }
        if (key > a[high])
        {
            Swap(&a[low], &a[high]);
            ++low;
        }
        while (low < high && key >= a[low])
        {
            ++low;  //向后尋找
        }
        if (key < a[low])
        {
            Swap(&a[low], &a[high]);
            --high;
        }
    }
    QuickSort(a, i, low-1);  //用同樣的方式對分出來的左邊的部分進行同上的做法
    QuickSort(a, low+1, j);  //用同樣的方式對分出來的右邊的部分進行同上的做法
}
輸出結果是:
最終排序結果為:
-234 -70 -58 1 2 3 4 5 7 8 9 32 34 43 56 76 532 543 635 900 2500

這個程序就是按上面講的過程寫的。實際上還可以對這個程序進行優化。在快速排序算法中,每輪比較有且僅有一個 key 值,但是 key 值的位置是不斷變化的,只有比較完一輪后 key 值的位置才固定。上面這個程序中每次執行 swap 時實際上交換的是 key 和 a[low] 或 key 和 a[high],而 key 的位置每次都是不一樣的。所以既然 key 的位置是“動來動去”的,所以就不必將它賦到數組中了,等最后一輪比較結束后,它的位置“不動”了,再將它賦到數組中。

比如,數組 a 中元素為:3142。如果按從小到大排序,那么 key=3,按上面這個程序就是 3 和 2 互換。2 賦給 a[0] 是必需的,但 key 就沒有必要賦給 a[3] 了。但你可以想象 key 是在 a[3] 這個位置,這個很重要。即此時序列變成 2142(key)。

然后 key 和 1 比較,不用換;key 和 4 比較,將 4 賦給 a[3],然后想象 key 在 4 的位置,即此時序列變成 214(key)4。此時 key 左邊全是比 key 小的,key 的右邊全是比 key 大的。這時 key 的位置就固定了,再將它賦到數組中,即 2134。
# include <stdio.h>
void QuickSort(int *, int, int);  /*現在只需要定義一個函數, 不用交換還省了一個函數, 減少了代碼量*/
int main(void)
{
    int i;  //循環變量
    int a[] = {900, 2, -58, 3, 34, 5, 76, 7, 32, 4, 43, 9, 1, 56, 8,-70, 635, -234, 532, 543, 2500};
    QuickSort(a, 0, 20);  /*引用起來很簡單, 0為第一個元素的下標, 20為最后一個元素的下標*/
    printf("最終排序結果為:\n");
    for (i=0; i<21; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}
void QuickSort(int *a, int low, int high)
{
    int i = low;
    int j = high;
    int key = a[low];
    if (low >= high)  //如果low >= high說明排序結束了
    {
        return ;
    }
    while (low < high)  //該while循環結束一次表示比較了一輪
    {
        while (low < high && key <= a[high])
        {
            --high;  //向前尋找
        }
        if (key > a[high])
        {
            a[low] = a[high];  //直接賦值, 不用交換
            ++low;
        }
        while (low < high && key >= a[low])
        {
            ++low;  //向后尋找
        }
        if (key < a[low])
        {
            a[high] = a[low];  //直接賦值, 不用交換
            --high;
        }
    }
    a[low] = key;  //查找完一輪后key值歸位, 不用比較一次就互換一次。此時key值將序列分成左右兩部分
    QuickSort(a, i, low-1);  //用同樣的方式對分出來的左邊的部分進行同上的做法
    QuickSort(a, low+1, j);  //用同樣的方式對分出來的右邊的部分進行同上的做法
}
輸出結果是:
最終排序結果為:
-234 -70 -58 1 2 3 4 5 7 8 9 32 34 43 56 76 532 543 635 900 2500

總結

快速排序的基本思想是通過一趟快速排序,將要排序的數據分割成獨立的兩部分,其中一部分的所有數據比另外一部分的所有數據都要小,然后再按此方法遞歸地對這兩部分數據分別進行快速排序。如此一直進行下去,直到排序完成。

快速排序實際上是冒泡排序的一種改進,是冒泡排序的升級版。這種改進就體現在根據分割序列的基準數,跨越式地進行交換。正是由于這種跨越式,使得元素每次移動的間距變大了,而不像冒泡排序那樣一格一格地“爬”。快速排序是一次跨多格,所以總的移動次數就比冒泡排序少很多。

但是快速排序也有一個問題,就是遞歸深度的問題。調用函數要消耗資源,遞歸需要系統堆棧,所以遞歸的空間消耗要比非遞歸的空間消耗大很多。而且如果遞歸太深的話會導致堆棧溢出,系統會“撐”不住。快速排序遞歸的深度取決于基準數的選擇,比如下面這個序列:

5  1  9  3  7  4  8  6  2

5 正好處于 1~9 的中間,選擇 5 作基準數可以平衡兩邊的遞歸深度。可如果是:

1  5  9  3  7  4  8  6  2

選擇 1 作為基準數,那么遞歸深度就全部都加到右邊了。如果右邊有幾萬個數的話則系統直接就崩潰了。所以需要對遞歸深度進行優化。怎么優化呢?就是任意取三個數,一般是取序列的第一個數、中間數和最后一個數,然后選擇這三個數中大小排在中間的那個數作為基準數,這樣起碼能確保獲取的基準數不是兩個極端。

前面講過,快速排序一般用于大數據排序,即數據的個數很多的時候(不是指數的值很大)。如果是小規模的排序,就用前面講的幾種簡單排序方式就行了,不必使用快速排序。

四種排序算法的比較

冒泡排序是最慢的排序算法。在實際運用中它是效率最低的算法。它通過一趟又一趟地比較數組中的每一個元素,使較大的數據下沉,較小的數據上升。

插入排序通過將序列中的值插入一個已經排好序的序列中,直到該序列結束。插入排序是對冒泡排序的改進。它比冒泡排序快兩倍。一般不用在數據的值大于 1000 的場合,或數據的個數超過 200 的序列。

選擇排序在實際應用中處于與冒泡排序基本相同的地位。它們只是排序算法發展的初級階段,在實際中使用較少。但是它們最好理解。

快速排序是大規模遞歸的算法,它比大部分排序算法都要快。一般用于數據個數比較多的情況。盡管可以在某些特殊的情況下寫出比快速排序快的算法,但是就通常情況而言,沒有比它更快的了。快速排序是遞歸的,對于內存非常有限的機器來說,它不是一個好的選擇。


 
穩定性:假定在待排序的序列中存在多個相同的值,若經過排序后,這些值的相對次序保持不變,即在原序列中 ri=rj,且 ri 在 rj 之前,而在排序后的序列中 ri 仍在 rj 之前,則稱這種排序算法是穩定的,否則稱為不穩定的。

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo