双指针快速排序c++
时间: 2023-11-04 13:00:42 浏览: 53
双指针快速排序是一种常见的排序算法。它通过选取一个基准元素,将数组分为两部分,左边的元素都小于等于基准元素,右边的元素都大于等于基准元素。然后对左右两部分递归地进行排序,最终将整个数组排序完成。
具体的C++代码实现如下所示:
```cpp
#include <iostream>
using namespace std;
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[low];
int i = low, j = high;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
while (i < j && arr[i] <= pivot) i++;
swap(arr[i], arr[j]);
}
swap(arr[low], arr[i]);
return i;
}
void quickSort(int arr[], int low, int high) {
if (low >= high) return;
int pivotPos = partition(arr, low, high);
quickSort(arr, low, pivotPos - 1);
quickSort(arr, pivotPos + 1, high);
}
int main() {
int arr[] = {8, 3, 7, 2, 9, 1, 5, 4, 6};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
```
以上是一个简单的双指针快速排序的实现,它可以对整型数组进行排序。你可以根据需要修改代码以适应其他类型的数组或容器。