设有一元素为整数的线性表L=(a1,a2,a3,…,an),存放在一维数组A[N]中,设计一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都大于an, an位于分界位置上(要求结果仍存放在A[N]中)。
上面是核心代码和一个随手写的简单测试,注意看数字15,左边都比15小,右边都比15大。
你的这个题目其实就是快速排序算法的一部分,有兴趣可以去看看快排的原理,我这个函数就是从之前写的快排拿出来小改了一下的。
下面是完整的测试函数,随手写的,可能不太优雅:
#include <bits/stdc++.h>
using namespace std;
void halfSort(int* v, int low, int high, int k) {
int mid = k, i = low, j = high;
while (true) {
while (v[j] > v[mid] && j != i) {
--j;
}
while (v[i] <= v[mid] && j != i) {
++i;
}
if (j != i) {
v[j] += v[i];
v[i] = v[j] - v[i];
v[j] -= v[i];
} else {
int temp = v[j];
v[j] = v[mid];
v[mid] = temp;
mid = j;
break;
}
}
}
int main(void) {
int arr[45];
for (int i = 0; i < 45; ++i) {
arr[i] = 45 - i;
}
int k = 30;
printf("k = %d, arr[k] = %d\n", k, arr[k]);
halfSort(arr, 0, 44, k);
for (int i = 0; i < 45; ++i) {
printf("%d ", arr[i]);
}
return 0;
}