⚡ 快速排序法完整教學

程式碼、原理與運作演示

← 回到排序法選單

📌 基本概念

快速排序法（Quick Sort）是一種分治法的排序演算法。其基本思想是：選擇一個「基準值」（pivot），將序列分成小於基準值和大於基準值的兩部分，分別遞迴排序，最後合併。

快速排序法的平均時間複雜度為 O(n log n)，但最壞情況下為 O(n²)。它通常比合併排序法快，且不需要額外的記憶體空間（原地排序）。

⚙️ 操作原理與動畫演示

快速排序法（Quick Sort）是一種分治法排序演算法。其基本思想是：
  • 選擇一個「基準值」（pivot），
  • 將序列分成小於基準值和大於基準值的兩部分，
  • 分別遞迴排序，最後合併。
（可自訂數列，逗號分隔）

📝 演算法偽代碼

選擇 1 為基準值，分割：[ ]，[1]，[5, 2, 8]
選擇 8 為基準值，分割：[5, 2]，[8]
選擇 2 為基準值，分割：[ ]，[2]，[5]
合併結果：[1, 2, 5, 8, 9]

💻 C語言完整程式碼

#include <stdio.h> void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } int partition(int arr[], int left, int right) { int pivot = arr[right]; int i = left - 1; for (int j = left; j < right; j++) { if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[right]); return i + 1; } void quickSort(int arr[], int left, int right) { if (left < right) { int pi = partition(arr, left, right); quickSort(arr, left, pi - 1); quickSort(arr, pi + 1, right); } } int main() { int numbers[] = {5, 2, 8, 1, 9}; int n = sizeof(numbers)/sizeof(numbers[0]); printf("原始數列: "); for (int i = 0; i < n; i++) { printf("%d ", numbers[i]); } printf("\n\n"); quickSort(numbers, 0, n-1); printf("排序後的數列: "); for (int i = 0; i < n; i++) { printf("%d ", numbers[i]); } printf("\n"); return 0; }

⏳ 時間與空間複雜度

平均時間複雜度O(n log n)
最壞時間複雜度O(n²)
空間複雜度O(log n)
排序穩定性不穩定
優點： 缺點：
← 回到排序法選單