題目：

請手動實現快速排序算法，包括單向分區以及雙向分區：

// 單向分區快速排序算法
void quick_sort_one_way(int arr[], int len);
//雙向分區快速排序算法
void quick_sort_two_way(int arr[], int len);

---

關鍵點

---

分析：

：

---

代碼

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))#define SWAP(arr, i, j){ \
int tmp = arr[i]; \
arr[i] = arr[j]; \
arr[j]=tmp; \
}void print_arr(int arr[], int len) {printf("[ ");for (int i = 0; i < len; i++) {printf("%d", arr[i]);if (i != len - 1) {printf(", ");}else {printf("]\n");}}
}
// 函數。函數就是分區的。 然后讓左邊比樞紐值小；右邊比它大。 
// 最后返回樞紐值的最終下標。 
int partition(int arr[], int left, int right) {int pivot_index = left;int pivot_value = arr[pivot_index];// 將 pivot_index 換到右邊了。 SWAP(arr, pivot_index, right);//  0     1   2   3   4    5     6//  11    8   9   7   12   16   17//                  c_left      c_right// pivot_index = 0;  pivot_value = 12int cur_left = left;int cur_right = right;while (cur_left < cur_right) {// 上來先找左邊，找左邊的比pivot 大的，弄到后面去。 while (cur_left < cur_right && arr[cur_left] < pivot_value) {cur_left++;}if (cur_left < cur_right) {arr[cur_right] = arr[cur_left];}while (cur_left < cur_right && arr[cur_right] > pivot_value) {cur_right--;}if (cur_left < cur_right) {arr[cur_left] = arr[cur_right];}}arr[cur_left] = pivot_value;return cur_left;
}void partition_recursive(int arr[], int left, int right) {if (left >= right) {// 沒數據，或者只有一個數據了。 這時候，我們認為遞歸結束。 return;}// 核心的代碼，其實是 partition。int partition_index = partition(arr, left, right);partition_recursive(arr, left, partition_index - 1);partition_recursive(arr, partition_index + 1, right);
}void quick_sort(int arr[], int len) {// 基本思路： 首先，找到一個樞紐值。 // 然后將比樞紐值小的數， 放在左邊； 比樞紐值大的數，放在右邊。 // 樞紐的位置，是正確的。  緊接著，繼續處理左邊的小數組，和右邊的小數組。 partition_recursive(arr, 0, len - 1);
}int main(void) {int arr[10] = { 16,1,45,23,99,2,18,67,42,10 };print_arr(arr, ARR_LEN(arr));quick_sort(arr, ARR_LEN(arr));print_arr(arr, ARR_LEN(arr));return 0;
}

---

解決方案總結：

：