用c++:利用快速排序算法对以下数组进行排序。 (12,25,17,19,51,32,45,18,22,37,15)
时间: 2024-10-11 16:05:01 浏览: 21
在C++中,我们可以使用快速排序算法(Quick Sort)对给定的整数数组进行排序。快速排序是一种分治策略,通常由递归实现。下面是一个简单的示例,展示如何使用快速排序对数组(12,25,17,19,51,32,45,18,22,37,15)进行排序:
```cpp
#include <iostream>
using namespace std;
// 交换两个元素的值
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 快速排序函数
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 选择最右边作为基准
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++; // increment index of smaller element
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) {
// pi是分区索引
int pi = partition(arr, low, high);
// 对左半部分和右半部分分别递归排序
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 测试快速排序
int main() {
vector<int> numbers = {12, 25, 17, 19, 51, 32, 45, 18, 22, 37, 15};
int n = numbers.size();
cout << "Original array: ";
for (int num : numbers)
cout << num << " ";
quickSort(numbers, 0, n - 1);
cout << "\nSorted array: ";
for (int num : numbers)
cout << num << " ";
return 0;
}
```
当你运行这个程序,它会输出已经排序好的数组。
阅读全文