#include <iostream> #include <vector> using namespace std; // 分区函数 int partition(vector<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(vector<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(){ vector<int> arr = {10, 7, 8, 9, 1, 5}; int n = arr.size(); cout << "Original array: "; for(auto num : arr) cout << num << " "; quickSort(arr, 0, n - 1); cout << "\nSorted array: "; for(auto num : arr) cout << num << " "; return 0; }转换为C语言

### C语言实现快速排序 以下是基于数组的快速排序算法在C语言中的完整实现。此实现遵循标准的快速排序逻辑，即通过选取一个基准值（pivot），将小于该基准值的元素放在左侧，大于或等于它的元素放在右侧。 #### 完整代码示例 ```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[low]; // 选择第一个元素作为基准 int i = low + 1; // 左指针 int j = high; // 右指针 while (1) { while (i <= j && arr[i] <= pivot) { // 找到第一个大于等于基准的元素 i++; } while (arr[j] >= pivot && j >= i) { // 找到第一个小于基准的元素 j--; } if (j < i) { // 如果两指针交叉，则退出循环 break; } else { // 否则交换两个元素的位置 swap(&arr[i], &arr[j]); } } swap(&arr[low], &arr[j]); // 将基准放到正确位置 return j; // 返回基准所在索引 } 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); // 对右子数组递归排序 } } void printArray(int arr[], int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int data[] = {8, 3, 7, 6, 4, 1, 0, 5, 9, 10}; int n = sizeof(data) / sizeof(data[0]); printf("原始数组:\n"); printArray(data, n); quickSort(data, 0, n - 1); printf("排序后的数组:\n"); printArray(data, n); return 0; } ``` --- #### 实现说明 1. **`swap` 函数** 此函数用于交换两个变量的值，在调整数组顺序时会频繁调用[^2]。 2. **`partition` 函数** 这是快速排序的核心部分之一。它负责选定基准并重新排列数组，使得所有小于基准的元素位于其左侧，而所有大于或等于基准的元素位于其右侧[^3]。 3. **`quickSort` 函数** 使用递归来分别对基准两侧的子数组执行相同的操作，直到整个数组有序[^1]。 4. **主程序 (`main`) 部分** 初始化待排序的数据集 `data` 并打印排序前后的结果以便验证功能是否正常工作。 --- #### 复杂度分析 - **时间复杂度**: 最优情况下为 \(O(n \log n)\)，最坏情况下的时间复杂度为 \(O(n^2)\)[^4]。 - **空间复杂度**: 主要由递归栈决定，平均情况下为 \(O(\log n)\)[^4]。 ---