c++快速排序函数怎么使用
C++中的快速排序函数可以通过以下步骤来使用:
- 包含
<iostream>
头文件用于输入输出操作。 - 定义一个快速排序函数,参数为要排序的数组,起始索引和结束索引。
- 在快速排序函数内部,选择一个基准元素(一般选择数组的第一个元素)。
- 设置两个指针,一个指向起始索引,一个指向结束索引。
- 将比基准元素小的元素放在基准元素的左边,比基准元素大的元素放在右边。
- 递归调用快速排序函数,对基准元素左边的子数组和右边的子数组进行排序。
- 在快速排序函数外部,调用快速排序函数来对数组进行排序。
下面是一个使用快速排序函数的示例代码:
#include <iostream>
// 快速排序函数
void quickSort(int arr[], int start, int end) {
if (start < end) {
int pivot = arr[start]; // 基准元素
int i = start; // 左指针
int j = end; // 右指针
while (i < j) {
// 从右往左找到比基准元素小的元素
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i] = arr[j];
i++;
}
// 从左往右找到比基准元素大的元素
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot; // 将基准元素放到正确的位置
// 递归调用快速排序函数
quickSort(arr, start, i - 1); // 对左边的子数组进行排序
quickSort(arr, i + 1, end); // 对右边的子数组进行排序
}
}
int main() {
int arr[] = {5, 2, 8, 3, 1, 6};
int n = sizeof(arr) / sizeof(arr[0]);
std::cout << "原始数组:";
for (int i = 0; i < n; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
quickSort(arr, 0, n - 1); // 调用快速排序函数
std::cout << "排序后的数组:";
for (int i = 0; i < n; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
输出结果:
原始数组:5 2 8 3 1 6
排序后的数组:1 2 3 5 6 8
在上面的示例中,我们定义了一个 quickSort
函数来对数组进行快速排序。然后在 main
函数中调用该函数,并输出排序后的数组。