第一步：实现分区函数
根据题目中的“快速排序”，我们需要实现一个分区函数，这个功能的实现：
- 设定基准值
pivot。 - 使用两个指针
low和high，分别从数组的两端向中间移动，进行元素交换。
int part(int A[], int low, int high){int pivot = A[low]; // 设定基准值while (low < high) { // 循环直到两个指针相遇while (low < high && A[high] >= pivot) // 从右边开始向左找第一个小于pivot的数--high;A[low] = A[high]; // 将找到的数放到左边while (low < high && A[low] <= pivot) // 从左边开始向右找第一个大于pivot的数++low;A[high] = A[low]; // 将找到的数放到右边}A[low] = pivot; // 将基准值放到中间return low; // 返回基准值的位置
}
第二步：实现快速排序函数
根据题目中的“快速排序”，我们需要递归地对分区后的子数组进行排序。
void Quicksort(int A[], int low, int high){if (low < high) { // 如果子数组长度大于1，则继续排序int pivotpos = part(A, low, high); // 调用分区函数Quicksort(A, low, pivotpos - 1); // 对左子数组排序Quicksort(A, pivotpos + 1, high); // 对右子数组排序}
}
代码注释
// 分区函数，用于快速排序
int part(int A[], int low, int high) {int pivot = A[low]; // 选择最左边的元素作为基准值while (low < high) { // 当两个指针没有相遇时继续while (low < high && A[high] >= pivot) // 从右向左找第一个小于基准值的元素--high;A[low] = A[high]; // 将找到的元素放到左边while (low < high && A[low] <= pivot) // 从左向右找第一个大于基准值的元素++low;A[high] = A[low]; // 将找到的元素放到右边}A[low] = pivot; // 将基准值放到中间return low; // 返回基准值的位置
}// 快速排序函数
void Quicksort(int A[], int low, int high) {if (low < high) { // 如果数组长度大于1，则继续排序int pivotpos = part(A, low, high); // 获取基准值的位置Quicksort(A, low, pivotpos - 1); // 对左边的子数组进行快速排序Quicksort(A, pivotpos + 1, high); // 对右边的子数组进行快速排序}
}
变量变化表格
| 步骤 | low | high | pivot | A[low] | A[high] | 说明 |
|---|---|---|---|---|---|---|
| 开始 | 0 | 5 | 3 | 3 | 7 | 初始化 |
| 第1次循环 | 1 | 4 | 3 | 3 | 2 | 移动high |
| 第2次循环 | 1 | 4 | 3 | 3 | 2 | 交换A[low]和A[high] |
| 第3次循环 | 2 | 3 | 3 | 1 | 2 | 移动low |
| 第4次循环 | 2 | 3 | 3 | 1 | 5 | 移动high |
| 结束 | 2 | 2 | 3 | 3 | 5 | 基准值归位 |