将顺序表(a1,a2,…,an)重新排列以a1为界的两部分:a1前面的值均比a1小,a1后面的值均比a1大(数据元素的类型为整型)c++代码
时间: 2024-09-20 21:05:45 浏览: 36
顺序表 -- 以a1为界限划分1
在 C++ 中,你可以通过双指针技巧来解决这个问题,通常称为 "partition" 或者 "快速排序的分区操作"。这里是一个简单的示例代码片段,它创建了一个函数 `partition` 来完成这个任务:
```cpp
#include <iostream>
using namespace std;
// Function to partition the array
int partition(int arr[], int low, int high) {
// Choose the rightmost element as pivot
int pivot = arr[high];
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // Increment index of smaller element
swap(arr[i], arr[j]); // Swap arr[i] and arr[j]
}
}
swap(arr[i + 1], arr[high]); // Put pivot in its correct position
return (i + 1);
}
// Function to implement QuickSort
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi is partitioning index, arr[p] is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// and after partition point
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int a[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
int n = sizeof(a) / sizeof(a[0]);
cout << "Original array: \n";
for (int i = 0; i < n; i++)
cout << a[i] << " ";
quickSort(a, 0, n - 1);
cout << "\nArray after partitioning: \n";
for (int i = 0; i < n; i++)
cout << a[i] << " ";
return 0;
}
```
这个程序首先对数组进行了划分,使得所有小于或等于 `pivot` 的元素都在它的左边,大于 `pivot` 的元素在其右边。然后分别递归地对左右两边的子数组进行排序。
阅读全文