Java语言怎么先在输入一个数组然后，再在其中寻找所有比中位数小的数字放在前面，比中位数大的数字放在后面，不能用排序的方法，怎么实现比较好？不容易出错的呢
参考：https://blog.csdn.net/jeddzd/article/details/88668699
可以先找到中位数，然后将数组分为两个部分，一个部分是比中位数小的数字，另一个部分是比中位数大的数字。然后，将这两个部分重新组合，比中位数小的数字放在前面，比中位数大的数字放在后面。以下是一种实现方式：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] nums = new int[10];
int n = nums.length;
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
int median = findMedian(nums);
int[] small = new int[n / 2];
int[] large = new int[n - n / 2];
for (int i = 0; i < n; i++) {
if (nums[i] < median) {
small[small.length - i / 2 - 1] = nums[i];
} else {
large[large.length - i / 2] = nums[i];
}
}
for (int i = 0; i < n / 2; i++) {
nums[i] = small[i];
}
for (int i = n / 2; i < n; i++) {
nums[i] = large[i - n / 2];
}
for (int i = 0; i < n; i++) {
System.out.print(nums[i] + " ");
}
}
private static int findMedian(int[] nums) {
int n = nums.length;
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (mid % 2 == 0) {
if (nums[mid] > nums[mid + 1]) {
left = mid + 2;
} else {
right = mid - 1;
}
} else {
if (nums[mid] > nums[mid - 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return nums[left / 2];
}
}
首先，通过 Scanner 类从标准输入中读取数组。然后，使用 findMedian 方法找到中位数。接下来，创建两个新的数组，一个用来存放比中位数小的数字，另一个用来存放比中位数大的数字。遍历原始数组，将数字分别放入这两个数组中。最后，将这两个数组重新组合，比中位数小的数字放在前面，比中位数大的数字放在后面。
不知道你这个问题是否已经解决, 如果还没有解决的话:一个较好的实现方法是使用两个指针来操作数组。下面是具体的步骤：
下面是用Java语言实现以上思路的代码：
import java.util.Arrays;
public class ArrayPartition {
public static void main(String[] args) {
int[] nums = {5, 2, 7, 3, 9, 1, 6};
int median = findMedian(nums);
partition(nums, median);
System.out.println(Arrays.toString(nums));
}
private static int findMedian(int[] nums) {
// 使用快速选择算法找到中位数
int start = 0;
int end = nums.length - 1;
int targetIndex = nums.length / 2;
while (start < end) {
int pivotIndex = partition(nums, start, end);
if (pivotIndex == targetIndex) {
break;
} else if (pivotIndex < targetIndex) {
start = pivotIndex + 1;
} else {
end = pivotIndex - 1;
}
}
return nums[targetIndex];
}
private static int partition(int[] nums, int start, int end) {
int pivot = nums[start];
int left = start + 1;
int right = end;
while (left <= right) {
if (nums[left] < pivot && nums[right] > pivot) {
swap(nums, left, right);
left++;
right--;
}
if (nums[left] >= pivot) {
left++;
}
if (nums[right] <= pivot) {
right--;
}
}
swap(nums, start, right);
return right;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
这个实现方法的时间复杂度为O(n)，因为找到中位数和分隔数组的操作都是线性时间复杂度。并且它不使用任何排序方法来实现，所以是可靠的。