快速排序c++语言程序
时间: 2024-01-05 14:20:32 浏览: 22
以下是快速排序的C++语言程序示例:
```cpp
#include <iostream>
// 划分操作
int Partition(int *A, int low, int high) {
int pivot = A[low]; // 选择第一个元素作为基准值
int i = low, j = high;
while (i < j) {
// 从右向左找到第一个小于基准值的元素
while (i < j && A[j] >= pivot) {
j--;
}
if (i < j) {
A[i++] = A[j];
}
// 从左向右找到第一个大于基准值的元素
while (i < j && A[i] <= pivot) {
i++;
}
if (i < j) {
A[j--] = A[i];
}
}
A[i] = pivot; // 将基准值放到最终位置
return i; // 返回基准值的位置
}
// 快速排序
void QuickSort(int *A, int low, int high) {
if (low < high) {
int pivotPos = Partition(A, low, high); // 划分
QuickSort(A, low, pivotPos - 1); // 对左子表进行递归排序
QuickSort(A, pivotPos + 1, high); // 对右子表进行递归排序
}
}
int main() {
int A[] = {5, 2, 8, 9, 1, 3};
int n = sizeof(A) / sizeof(A[0]);
QuickSort(A, 0, n - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
std::cout << A[i] << " ";
}
std::cout << std::endl;
return 0;
}
```