快速排序数组monster=[4,2,1,5,3]从小到大排序C++实现
时间: 2024-09-26 20:09:24 浏览: 26
快速排序是一种高效的排序算法,其基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录继续进行排序,以达到整个序列有序。
以下是使用C++实现快速排序算法,对给定数组`monster=[4,2,1,5,3]`从小到大排序的一个例子:
```cpp
#include <iostream>
#include <vector>
// 交换两个元素的值
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// 分区函数,返回基准元素的最终位置
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = (low - 1); // i用于找到小于基准的元素
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) { // 如果当前元素小于基准
i++; // 移动i指针并交换
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]); // 将基准放到正确的位置
return i + 1;
}
// 快速排序主函数
void quickSort(std::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() {
std::vector<int> monster = {4, 2, 1, 5, 3};
int n = monster.size();
quickSort(monster, 0, n - 1);
// 打印排序后的数组
std::cout << "Sorted array: ";
for (const auto &num : monster)
std::cout << num << " ";
std::cout << "\n";
return 0;
}
```
当你运行这个程序,它会输出已经从小到大排列的数组 `[1, 2, 3, 4, 5]`。
阅读全文