※ 引述《oin1104 (是oin的說)》之銘言：
: 我要吐了
: 明明我寫的丟去執行都沒問題
: 可是就是時間太久 不接受
: qsort怎麼用阿
: 機掰 我吐了
請用c語言實現快速排序
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
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);
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
for(int i=0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
這裡主要邏輯是:
選擇一個基準值pivot,通常選擇數組的最後一個元素
定義兩個指標i和j,i初始化為low-1,j初始化為low。
j從low到high-1遍歷數組,如果arr[j]小於等於pivot,交換arr[++i]和arr[j]的位置,這樣
可以保證左邊的值都小於pivot。
最後交換pivot和arr[i+1]的位置,這樣可以保證pivot的左邊值都小於pivot,右邊值都大
於pivot。
遞歸對pivot左邊和右邊的子數組進行快速排序。
這樣就可以實現快速排序了。