c++ vector快速排序
时间: 2023-08-29 22:11:57 浏览: 55
你可以使用C++中的STL库来进行向量(vector)的快速排序。下面是一个示例代码:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> nums = {5, 2, 9, 1, 3};
std::sort(nums.begin(), nums.end());
for (int num : nums) {
std::cout << num << " ";
}
return 0;
}
```
在上述示例代码中,我们使用`std::sort`函数对向量`nums`进行排序。该函数会自动使用快速排序算法对元素进行排序。最后,我们遍历并打印排序后的向量元素。
运行上述代码,输出将为:1 2 3 5 9,表示向量已经按升序排列完成。
相关问题
c++ vector 排序算法
在 C++ 中,可以使用 `std::sort` 函数对 `std::vector` 进行排序。`std::sort` 函数使用快速排序算法或者其它有效的排序算法来对容器中的元素进行排序。以下是一个示例代码:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {5, 2, 8, 1, 9};
// 对 vec 进行升序排序
std::sort(vec.begin(), vec.end());
// 输出排序后的结果
for (const auto& num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
```
输出结果为:
```
1 2 5 8 9
```
在这个示例中,我们使用了 `std::sort` 函数来对 `vec` 进行升序排序。`std::sort` 函数接受两个迭代器作为参数,表示排序范围的起始位置和结束位置。通过传入 `vec.begin()` 和 `vec.end()`,我们对整个 `vec` 容器进行排序。最后,我们使用循环输出排序后的结果。根据需要,你也可以使用自定义的比较函数来进行排序。
vector快速排序
要使用快速排序算法对向量进行排序,可以按照以下步骤进行操作:
1. 选择一个基准元素(通常是向量的第一个元素)作为比较对象。
2. 将向量分成两个子向量,一个包含比基准元素小的元素,另一个包含比基准元素大的元素。这个过程称为分区(partitioning),可以使用双指针法或者递归实现。
3. 对两个子向量分别递归地应用快速排序算法。
4. 将两个排序好的子向量合并起来,得到最终的排序结果。
下面是一个示例的C++代码实现:
```cpp
#include <iostream>
#include <vector>
// 分区函数,返回基准元素的最终位置
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[low]; // 选择第一个元素作为基准
int i = low + 1; // 左指针
int j = high; // 右指针
while (i <= j) {
if (arr[i] <= pivot) {
i++;
} else if (arr[j] > pivot) {
j--;
} else {
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[low], arr[j]); // 将基准元素放到正确的位置上
return j;
}
// 快速排序函数
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high); // 获取基准元素的最终位置
quickSort(arr, low, pivotIndex - 1); // 对左子向量进行快速排序
quickSort(arr, pivotIndex + 1, high); // 对右子向量进行快速排序
}
}
// 测试快速排序算法
int main() {
std::vector<int> arr = {5, 2, 9, 1, 6, 3};
quickSort(arr, 0, arr.size() - 1);
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
```
这段代码使用了递归实现快速排序算法,将基准元素放到正确的位置上后,再对左右子向量分别进行排序。最终输出排序后的向量:1 2 3 5 6 9。