如何進行C語言數據結構與算法中的排序總結

# 如何進行C語言數據結構與算法中的排序總結

## 引言

排序算法是計算機科學中最基礎且重要的研究領域之一。在C語言中實現各類排序算法，不僅能夠幫助我們深入理解數據結構的組織方式，還能提升對算法時間/空間復雜度的分析能力。本文將系統性地總結常見的排序算法實現原理、C語言實現代碼、性能對比以及實際應用場景。

---

## 一、排序算法基礎概念

### 1.1 排序的定義與分類
排序是將一組**無序的數據元素**按照特定規則（如大小、字母序等）重新排列為**有序序列**的過程。根據實現方式可分為：

- **比較排序**：通過元素間的比較決定順序（如快速排序、歸并排序）
- **非比較排序**：不依賴元素比較（如計數排序、基數排序）
- **穩定排序**：相等元素的相對位置不變（如冒泡排序）
- **不穩定排序**：相等元素可能交換位置（如堆排序）

### 1.2 評價指標
- **時間復雜度**：最好/最壞/平均情況
- **空間復雜度**：是否使用額外空間（原地排序/非原地排序）
- **穩定性**：如上文定義
- **適應性**：對部分有序數據的處理效率

---

## 二、常見排序算法及C語言實現

### 2.1 基礎排序算法

#### 冒泡排序（Bubble Sort）
```c
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交換相鄰元素
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

特點： - 時間復雜度：O(n2)（最優情況可優化至O(n)） - 空間復雜度：O(1) - 穩定排序

選擇排序（Selection Sort）

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) 
                min_idx = j;
        }
        // 交換當前元素與最小值
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

特點： - 時間復雜度：O(n2) - 空間復雜度：O(1) - 不穩定排序

2.2 高效排序算法

快速排序（Quick Sort）

// 分區函數
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high-1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i+1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

特點： - 平均時間復雜度：O(n log n) - 最壞情況（已排序數組）：O(n2) - 空間復雜度：O(log n)（遞歸棧） - 不穩定排序

歸并排序（Merge Sort）

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

特點： - 時間復雜度：O(n log n) - 空間復雜度：O(n)（臨時數組） - 穩定排序

2.3 特殊場景排序算法

計數排序（Counting Sort）

void countingSort(int arr[], int n, int range) {
    int output[n];
    int count[range + 1];
    memset(count, 0, sizeof(count));
    
    for (int i = 0; i < n; i++) 
        count[arr[i]]++;
    
    for (int i = 1; i <= range; i++)
        count[i] += count[i-1];
    
    for (int i = n-1; i >= 0; i--) {
        output[count[arr[i]]-1] = arr[i];
        count[arr[i]]--;
    }
    
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

適用場景： - 數據范圍已知且較?。ㄈ?-100的整數） - 時間復雜度：O(n + k)（k為數據范圍）

三、性能對比與選型建議

3.1 時間復雜度對比

3.2 實際應用建議

• 小規模數據：選擇插入排序（代碼簡單，常數因子?。?/li>
• 通用場景：快速排序（綜合性能最優）
• 穩定性要求：歸并排序
• 數據范圍有限：計數排序/桶排序

四、C語言實現中的優化技巧

4.1 快速排序優化

• 三數取中法選擇基準點

int mid = l + (r - l)/2;
if (arr[mid] < arr[l]) swap(&arr[l], &arr[mid]);
if (arr[r] < arr[l]) swap(&arr[l], &arr[r]);
if (arr[r] < arr[mid]) swap(&arr[mid], &arr[r]);

4.2 避免遞歸棧溢出

• 使用尾遞歸優化或迭代實現

// 迭代版快速排序
void quickSortIterative(int arr[], int l, int h) {
    int stack[h - l + 1];
    int top = -1;
    stack[++top] = l;
    stack[++top] = h;
    while (top >= 0) {
        h = stack[top--];
        l = stack[top--];
        int p = partition(arr, l, h);
        if (p - 1 > l) {
            stack[++top] = l;
            stack[++top] = p - 1;
        }
        if (p + 1 < h) {
            stack[++top] = p + 1;
            stack[++top] = h;
        }
    }
}

五、總結與延伸學習

掌握排序算法的核心在于理解其分治策略與數據移動方式。建議通過以下方式深化理解： 1. 可視化工具觀察排序過程（如VisuAlgo） 2. 對比不同數據規模下的實際運行時間 3. 閱讀標準庫實現（如glibc的qsort源碼）

“優秀的程序員應該了解至少六種排序算法，就像木匠必須熟悉多種鋸子一樣。” —— 《編程珠璣》

附錄：完整測試代碼示例見GitHub倉庫鏈接 “`

（注：實際完整文章包含更多算法的實現細節、復雜度數學推導和測試案例，此處為精簡版框架）