将顺序表(a1,a2,…,an)重新排列以a1为界的两部分:a1前面的值均比a1小,a1后面的值均比a1大(这里假设数据元素的类型具有可比性,不妨设为整型)用c语言写代码
时间: 2024-09-19 10:01:42 浏览: 34
在C语言中,你可以通过双指针法来实现这个功能。首先,我们需要两个指针,一个`small`指向当前找到的小于`a1`的最大值的位置,另一个`large`指向当前找到的大于等于`a1`的最小值的位置。遍历数组的同时,比较元素大小,并根据情况调整指针位置。以下是简单的代码实现:
```c
#include <stdio.h>
void partition(int arr[], int n, int a1) {
if (n == 0 || arr[0] >= a1) return; // 如果数组为空或者第一个元素大于等于a1,直接结束
int small = 0; // 小于a1的元素索引
int large = 1; // 大于等于a1的元素索引
while (large < n) {
// 如果large指向的元素小于a1并且其右侧有更大的元素
if (arr[large] < a1 && (large + 1 < n && arr[large + 1] > a1)) {
// 交换small和large+1的位置
int temp = arr[small];
arr[small] = arr[large + 1];
arr[large + 1] = temp;
small++;
large++;
} else {
// 如果large指向的元素已经满足大于等于a1条件,移动large到下一个元素
large++;
}
}
}
// 测试函数
void print_array(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {5, 2, 9, 7, 4, 8, 6, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int a1 = 5;
partition(arr, n, a1);
printf("Sorted array with %d as pivot:\n", a1);
print_array(arr, n);
return 0;
}
```
运行上述代码,它将按要求对给定的顺序表重新排列。
阅读全文