c++求快速排序第一趟
时间: 2023-12-11 18:32:38 浏览: 34
快速排序是一种高效的排序算法,其核心思想是通过分治的思想将一个大问题分解成多个小问题,然后递归地解决这些小问题。在快速排序的第一趟中,我们需要选取一个基准元素,然后将待排序序列中小于等于基准元素的元素放在基准元素的左边,大于基准元素的元素放在基准元素的右边。这个过程称为一次划分。
以下是C++实现快速排序第一趟的代码示例:
```c++
#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++;
if (i < j) swap(arr[i], arr[j]); }
swap(arr[low], arr[i]); // 将基准元素放到正确的位置
return i;
}
int main() {
int arr[] = { 5, 3, 8, 4, 2, 7, 1, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
int index = partition(arr, 0, n - 1);
cout << "第一趟排序后的结果为:";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl << "基准元素的下标为:" << index << endl;
return 0;
}
```
以上代码中,我们选取第一个元素作为基准元素,然后使用双指针i和j分别从待排序序列的左右两端开始扫描,当i指向的元素大于基准元素,j指向的元素小于等于基准元素时,交换i和j指向的元素。最终,将基准元素放到正确的位置上,返回基准元素的下标。