⑴ 遞迴實現快速排序（Quicksort）：
快速排序是一種高效的排序演算法，由C.A.R. Hoare在1960年提出。它的基本思想是分治法（Divide and Conquer）。以下是快速排序使用遞迴方式的基本步驟：
選擇基準點（Pivot）：
從數列中選擇一個元素作為基準點。
分割（Partition）：
重新排列數列，所有比基準點小的元素放基準點前面，所有比基準點大的元素放在基準點後面。在這個分割結束之後，對基準點的排序就已經完成。
遞迴排序子序列：
遞迴地將小於基準點的子序列和大於基準點的子序列排序。
快速排序的遞迴過程可以終止於子序列的大小減至1，這意味著該元素已經被排序。
示例代碼（C語言）：
c
Copy code
#include <stdio.h>
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1); // 對基準點左側遞迴排序
quickSort(arr, pivot + 1, high); // 對基準點右側遞迴排序
}
}
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 swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
⑵ 優點和缺點：
優點：
高效：在大多數情況下，快速排序的平均時間複雜度為O(n log n)。
就地排序：不需要額外的存儲空間。
缺點：
最壞情況性能差：如果數據已經是有序的或者幾乎有序的，快速排序的時間複雜度會退化到O(n^2)。這可以通過隨機選擇基準點來優化。
不穩定排序：相等的元素可能會因排序而改變順序。
快速排序在處理大數據集時表現良好，但在數據集較小或幾乎已排序的情況下，其性能可能不如其他排序算法，如插入排序。
阿摩線上測驗
登入