c快速排序vector

### C语言中使用 `std::vector` 和快速排序 虽然标准C语言本身并不提供类似于C++中的 `std::vector` 数据结构，但在实际开发中可以借助外部库或者通过手动模拟来实现类似的动态数组功能。如果希望在C语言环境中完成类似操作，则可以通过自定义函数配合指针管理的方式来处理。 以下是基于C语言的快速排序实现代码示例，假设已有一个动态分配内存的整型数组作为输入： ```c #include <stdio.h> #include <stdlib.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); // 右半边继续排序 } } // 动态数组创建与释放 typedef struct Vector { int size; int capacity; int* data; } Vector; Vector* createVector() { Vector* vec = malloc(sizeof(Vector)); vec->size = 0; vec->capacity = 8; vec->data = calloc(vec->capacity, sizeof(int)); return vec; } void pushBack(Vector* vec, int value) { if (vec->size >= vec->capacity) { vec->capacity *= 2; vec->data = realloc(vec->data, vec->capacity * sizeof(int)); } vec->data[vec->size++] = value; } void freeVector(Vector* vec) { free(vec->data); free(vec); } // 打印向量内容 void printVector(const Vector* vec) { printf("["); for (int i = 0; i < vec->size; ++i) { printf("%d", vec->data[i]); if (i != vec->size - 1) printf(", "); } printf("]\n"); } int main() { Vector* v = createVector(); // 向向量中添加一些随机数 srand(time(NULL)); for (int i = 0; i < 10; ++i) { pushBack(v, rand() % 100); } printf("原始数组: "); printVector(v); // 调用快速排序 quickSort(v->data, 0, v->size - 1); printf("排序后的数组: "); printVector(v); freeVector(v); return 0; } ``` 上述代码实现了以下几点： - 使用了一个简单的动态数组（即 `struct Vector`），模仿了C++中 `std::vector` 的基本行为。 - 提供了 `pushBack()` 函数用于扩展数组大小并插入新元素[^1]。 - 利用了经典的快速排序逻辑对动态数组的内容进行了排序[^3]。 #### 关键说明 - **空间复杂度**：由于采用了原地分治策略，因此额外的空间需求较低。 - **时间复杂度**：平均情况下为 \( O(n \log n) \)，但当数据接近完全有序时会退化至 \( O(n^2) \)。 --- ###