如何对一些元素进行排序，而将其他元素留在Java中？

arrays sorting lambda java

2022-09-02 13:18:42

我希望对数组中的一些元素进行排序，但排除其他元素。

对于一个简单的例子，一个包含整数的数组，我想对奇数进行排序，但将偶数保留在原处。

到目前为止，我有以下内容：

public class MyClass {
    public static void main(String args[]) {
        int temp;
        int array[] = {5, 3, 2, 8, 1, 4};

        int[] sortedArray = new int[array.length];
        for (int j = 0; j < array.length - 1; j++) {
            for (int x = 0; x < array.length - 1; x++) {
                if (array[x] > array[x + 1] && array[x] % 2 != 0 && array[x + 1] % 2 !=0) {
                    temp = array[x];
                    array[x] = array[x + 1];
                    array[x + 1] = temp;
                    sortedArray = array;
                }
            }
        }
        for (int i: sortedArray) {
            System.out.println(i);
        }

    }
}

给定整数数组：5、 3、 2、 8、 1、 4

代码输出：3、5、2、8、1、4

预期输出： 1， 3， 2， 8， 5， 4

无法完全弄清楚原始数组中较低的奇数先于偶数的场景所需的逻辑。

答案 1

一个简单的暴力破解解决方案：

迭代输入数组，并检索所有奇数
在一个新的、更小的数组中收集奇数
对该数组进行排序
现在再次遍历初始数组：每当您找到奇数时，您就从奇数组中选择“next”条目

以上可能不是最佳解决方案（因为在第二个数组上浪费内存，并花时间复制/向后复制值） - 但它应该非常容易写下来并进行测试。

从理论上讲，您也可以“就地”做到这一点。含义：您可以创建一个围绕int数组的类 - 但它为其用户提供了一个仅显示奇数int数组的视图。

示例实现（感谢 Daniel Foerster）：

public static int[] sortFiltered(int[] src, IntPredicate predicate) {
  int[] filtered = IntStream.of(src).filter(predicate).sorted().toArray();
  int[] dst = new int[src.length];
  for (int i = 0, j = 0; i < src.length; i++) {
    dst[i] = predicate.test(src[i]) ? filtered[j++] : src[i];
  }
  return dst;
}

使用过滤器调用奇数：

sortFiltered(array, (n) -> n % 2 != 0);

如您所见，此算法不依赖于特定的谓词或数组/列表类型。但是由于它使用IntStream和Lambda表达式，因此它需要Java 8或更高版本。

答案 2

给定未排序的数组 A：按顺序创建 2 个包含数组奇数和偶数元素的 Vector 实例 O 和 E。（所有代码示例都是伪代码。循环中的“up to”表示根据标准数组边界编号，不包括限制的右侧）

for i in 0 up to A.length: if A[i] is odd, append it to O, else append it to E

创建一个单独的布尔值 B 数组，如下所示：

for i in 0 up to A.length: if A[i] is odd, B[i] = true, else B[i] = false

将 O 排序到新的向量 S 中（按升序）。我建议使用Java的内置排序，因为它比你正在使用的其他答案声称的气泡排序更有效。

S = ascendingSort(O)

定义一个操作 pop，该操作 pop 返回 Vector 中的第一个项目，然后将其从 Vector 中删除。

创建一个新的空矢量 R，然后实现以下伪代码：

for i in 0 up to B.length: if B[i] is true, then append pop(S) to R, else append pop(E) to R.

返回 R 作为结果。

为什么这样做有效：

首先，将赔率与偶数分开，以隐藏排序中的偶数，保持其原始顺序（向量 O 和 E）。保持原始数组中奇数/偶数项的位置（向量 B）。

对赔率进行排序（向量 S）。

排序后，将偶数和排序赔率按顺序拼接，保持偶数的原始顺序。通读向量 B，按顺序从向量 E 和 S 中获取元素。这保持了偶数的顺序，因为它们首先按顺序放置在向量E中，并且它们被按顺序放回。