C語言導航員～系統開發的最強資源～

C語言 qsort 函式教學：快速排序原理與實用範例解析

標準函式庫
目次

1. qsort 函式概述

C語言標準函式庫中提供的 qsort 函式，是用來對陣列元素進行排序的強大工具。qsort 採用快速排序（Quick Sort）演算法，能夠高速地重新排列資料，效率極高。本節將說明 qsort 的基本運作方式，以及為何這個函式如此重要。

什麼是 qsort？

qsort 是一個通用排序函式，可以根據使用者自訂的比較函式，對陣列或列表等資料進行排序。這是 C 語言的標準函式之一，廣泛應用於各種開發場景。例如，可以有效地對整數陣列、字串陣列，甚至包含結構體的資料進行排序。

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int values[] = {40, 10, 100, 90, 20, 25};
    size_t values_len = sizeof(values)/sizeof(values[0]);

    qsort(values, values_len, sizeof(int), compare);

    for(int i = 0; i < values_len; i++) {
        printf("%d ", values[i]);
    }
    return 0;
}

上述程式碼是利用 qsort 排序整數陣列的基本範例。這裡透過比較函式判斷大小，進行陣列排序。

2. qsort 的參數與用法

qsort 的原型如下：

void qsort(void *base, size_t num, size_t size, int (*compar)(const void *, const void *));

參數說明

  1. base：要排序的陣列起始指標。
  2. num：陣列元素數量。
  3. size：每個元素的大小（以位元組為單位）。
  4. compar：指向比較函式的指標。

此函式根據比較函式 compar 來排序元素。compar 需傳回一個整數，根據兩個元素的大小關係決定順序。這樣就可以靈活地對各種資料型態進行排序。

比較函式的撰寫

比較函式是 qsort 運作的關鍵。以下範例說明如何定義元素間比較的函式：

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

這個函式會比較 a 與 b 的值，a 小於 b 時傳回負數，相等時傳回 0，大於時傳回正數。如此一來，qsort 就能將陣列按升序排列。

侍エンジニア塾

3. qsort 的內部運作：快速排序演算法

qsort 內部採用快速排序（Quick Sort）演算法。這是一種分治法（Divide and Conquer）的排序演算法，流程如下：

  1. 選擇樞紐（pivot）：通常選擇陣列中間或最後一個元素作為基準。
  2. 分割：將小於 pivot 的元素移至左側，大於 pivot 的移至右側。
  3. 遞迴排序：對每個子陣列重複上述操作。

透過不斷分割與合併，能高效地完成排序。平均時間複雜度為 O(n log n)，比多數其他排序演算法都要快速。但在最壞情況（例如資料已排序）下，時間複雜度會變成 O(n^2)，需特別留意。

4. 比較函式的實作方式

qsort 的強大之處在於可以為不同資料型態自訂比較函式。以下舉例說明：

整數比較函式

int compare_int(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

字串比較函式

int compare_str(const void *a, const void *b) {
    return strcmp(*(const char**)a, *(const char**)b);
}

結構體比較函式

struct Person {
    int id;
    const char* name;
};

int compare_person(const void *a, const void *b) {
    return ((struct Person*)a)->id - ((struct Person*)b)->id;
}

如上所示，透過自訂比較函式，qsort 能依據內容靈活排序各種資料。

5. 使用 qsort 排序結構體陣列

當需要對包含結構體的陣列進行排序時，qsort 也非常實用。例如，以下是以 id 欄位對 Person 結構體陣列排序的範例：

struct Person people[] = {
    {1, "Alice"},
    {3, "Charlie"},
    {2, "Bob"}
};

qsort(people, 3, sizeof(struct Person), compare_person);

利用 compare_person 函式排序後，陣列內容會變成 Alice、Bob、Charlie 的順序。

6. 效能最佳化與與其他演算法的比較

快速排序效能

快速排序對於隨機資料表現極佳，平均時間複雜度為 O(n log n)。但若資料本身已排序，最壞情況下會降至 O(n^2)。因此，對於不同資料狀況需評估最適合的排序法。

與堆積排序比較

堆積排序（Heap Sort）即使在最壞情況下也能保持 O(n log n) 的效率，比快速排序更穩定。不過，一般來說，對隨機資料快速排序速度仍較快，因此多數情境仍推薦使用快速排序。

與合併排序比較

合併排序（Merge Sort）同樣為 O(n log n) 時間複雜度，且屬於穩定排序，適合需要保持相同值原有順序的情境。快速排序則不保證穩定性，但多數應用場景下差異不大。

7. 總結

qsort 是 C 語言中功能強大的排序函式，靈活且高效。利用自訂比較函式，可針對多種資料型態和結構體陣列進行排序，實用價值極高。

深入理解快速排序演算法後，更能發揮 qsort 的效益。依據不同資料特性，也可以與堆積排序、合併排序等其他演算法比較，選擇最合適的方案，提升程式效能。

未來在實際開發專案中，請善用 qsort，挑戰更高效的程式設計。