8642 快速排序：分區過程可視化與實現

8642 快速排序：分區過程可視化與實現

實現快速排序並輸出每次分區後的數組狀態。經典單向掃描分區法 (Hoare 分區)。

分區算法 (Hoare 版)

int Partition(int a[], int low, int high) {
    int pivot = a[low]; // 基準值
    while (low < high) {
        while (low < high && a[high] >= pivot) high--;
        swap(a[low], a[high]);
        while (low < high && a[low] <= pivot) low++;
        swap(a[low], a[high]);
    }
    return low; // 基準最終位置
}

遞歸快排 + 輸出

void QuickSort(int a[], int low, int high) {
    if (low < high) {
        int pivot = Partition(a, low, high);
        print_array(a, n); // 每次分區後輸出
        QuickSort(a, low, pivot - 1);
        QuickSort(a, pivot + 1, high);
    }
}

完整程序 (順序表結構)

#include <stdio.h>
#include <malloc.h>

#define OK 1
#define ERROR 0
typedef int ElemType;

typedef struct {
    ElemType *elem;
    int length, listsize;
} SqList;

int InitList(SqList &L, int m) {
    L.elem = (ElemType*)malloc(m * sizeof(ElemType));
    if (!L.elem) return ERROR;
    L.length = 0; L.listsize = m;
    return OK;
}

void PrintList(SqList &L) {
    for (int i = 0; i < L.length; ++i)
        printf("%d ", L.elem[i]);
    printf("\n");
}

int Partition(SqList &L, int low, int high) {
    ElemType pivot = L.elem[low];
    while (low < high) {
        while (low < high && L.elem[high] >= pivot) high--;
        swap(L.elem[low], L.elem[high]);
        while (low < high && L.elem[low] <= pivot) low++;
        swap(L.elem[low], L.elem[high]);
    }
    return low;
}

void QSort(SqList &L, int low, int high) {
    if (low < high) {
        int pivot = Partition(L, low, high);
        PrintList(L);
        QSort(L, low, pivot - 1);
        QSort(L, pivot + 1, high);
    }
}

int main() {
    SqList L;
    int n, x;
    scanf("%d", &n);
    if (InitList(L, n)) {
        for (int i = 0; i < n; ++i) {
            scanf("%d", &x);
            L.elem[i] = x;
        }
        L.length = n;
        QSort(L, 0, n - 1);
    }
    return 0;
}

樣例執行過程

Input: 10
5 4 8 0 9 3 2 6 7 1

分區過程輸出:
1 4 2 0 3 5 9 6 7 8  (pivot=5 歸位)
0 1 2 4 3 5 9 6 7 8  (左半部 pivot=1 歸位)
0 1 2 4 3 5 9 6 7 8  (左半部已有序)
0 1 2 3 4 5 9 6 7 8  (左半部 pivot=4 歸位)
0 1 2 3 4 5 8 6 7 9  (右半部 pivot=9 歸位)
0 1 2 3 4 5 7 6 8 9  (右半部 pivot=8 歸位)
0 1 2 3 4 5 6 7 8 9  (右半部 pivot=7 歸位，完成)

關鍵點總結

1. 基準選擇：首元素 (易退化)，可改為三數取中
2. 分區邏輯：雙向掃描交換，基準最終歸位
3. 遞歸邊界：`low >= high` 返回
4. 輸出時機：每次 `Partition` 返回後，即基準歸位後
5. 空間複雜度：遞歸棧 O(log n) 平均，O(n) 最壞

優化方向

• 三數取中基準：避免有序數組 O(n²)
• 小區間插入排序：長度 ≤ 16 切換
• 尾遞歸優化：手動模擬棧或迭代大分區
• 三路分區：處理大量重複元素

快速排序是面試必考、工程常用的排序算法，掌握其分區邏輯、遞歸結構、優化技巧是基本功核心。