申論題

快速排序（Quicksort）是一種高效的排序演算法，採用分治策略來對一個序列進行排序。下麵是使用C語言實現的快速排序演算法，它通過遞歸的方式實現：

#include <stdio.h>

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int *A, int low, int high) {
    int pivot = A[high];  // 選擇最後一個元素作為基準
    int i = (low - 1);  // i指針初始化指向較小元素的最右位置

    for (int j = low; j <= high - 1; j++) {
        // 如果當前元素小於或等於pivot，則交換位置
        if (A[j] <= pivot) {
            i++;  // 移動較小元素的指針
            swap(&A[i], &A[j]);
        }
    }
    swap(&A[i + 1], &A[high]);
    return (i + 1);  // 返回分區的索引
}

void quickSort(int *A, int low, int high) {
    if (low < high) {
        // pi是partitioning index，A[pi]現在位於正確位置
        int pi = partition(A, low, high);

        // 分別對分割點左右兩側遞歸排序
        quickSort(A, low, pi - 1);
        quickSort(A, pi + 1, high);
    }
}

// 用於列印數組的輔助函數
void printArray(int *A, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", A[i]);
    }
    printf("\n");
}

int main() {
    int A[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(A) / sizeof(A[0]);
    quickSort(A, 0, n - 1);
    printf("Sorted array: \n");
    printArray(A, n);
    return 0;
}
這段代碼中，quickSort函數是快速排序的主體函數，它接受一個數組A和該數組的最低索引low以及最高索引high作為參數。partition函數用於將數組分為兩部分，所有小於某個選定值（pivot）的元素都會被移動到該值的左側，而大於等於它的元素都會被移動到右側，然後返回pivot所在的新位置。quickSort函數通過遞歸調用自己來對pivot左右兩側的子數組進行排序，直到子數組長度為1或0，此時數組已經完全排序。