如何在Java中对一些元素进行排序并保留其他元素？

Question

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

以一个包含整数的简单示例为例，我想对奇数进行排序，而将偶数保留在原地。

到目前为止，我有以下代码：

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

无法确定在原始数组中，一个更小的奇数数值是否排在一个偶数数值之前需要满足什么逻辑条件。

- BIGJOHN

---

请提供您期望的输出。 - User27854

1、3、2、8、5、4 - 奇数已排序，偶数保持原位。 - BIGJOHN

我很难想出这种算法的使用案例。 - corsiKa

@corsiKa 不挂科是我所期望的一个原因。 - AlbertEngelB

Answer 1

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

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

上述解决方案可能不是最优解（因为浪费内存在第二个数组上，并花费时间复制值），但应该很容易写下和测试。

理论上，你也可以在原地执行。意思是：你可以创建一个类，它封装了一个 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或更新版本。

- GhostCat

---

好的解决方案。我也是想建议同样的 :) - nagendra547

如果你必须暴力破解一个相对标准的排序或使用预期运行时间高于n log n（其中n =输入数组的大小），那么你做错了什么。 - user1258361

非常好的通用实现，我刚刚点赞了！但为了完整起见：Lambda表达式是在Java 8中引入的，如果需要使用较低版本的Java，则无法使用。 - Andre Kampling

此外，这个解决方案应该比其他二次方O(n^2)的答案更快。由于IntStream.sorted()，它的最坏情况应该是O(n log n)，请参见：https://dev59.com/O10Z5IYBdhLWcg3wlBFU#31302160。这里还有一个很好的Big-O符号的快速参考：http://bigocheatsheet.com/。 - Andre Kampling

Answer 2

你已经实现了一种（不是特别高效的）冒泡排序。你代码的问题在于，即使只有一个元素是偶数，它也将两个元素都排除在排序之外。在你的解决方案基础上，你可以按照以下方式调整你的代码：

public class MyClass {
    public static void main(String args[]) {
        int temp;
        //odd numbers are sorted, even number stay where they are
        //Expected output: 1, 3, 2, 8, 5, 4
        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++) {

                while(array[x] % 2 == 0 && x < array.length-1){
                    x++;
                }

                int y = x+1;

                if(y < array.length) {
                    while (array[y] % 2 == 0 && y < array.length - 1) {
                        y++;
                    }

                    if (array[x] > array[y] && array[y] % 2 == 1 && array[x] % 2 == 1) {
                        temp = array[x];
                        array[x] = array[y];
                        array[y] = temp;
                        sortedArray = array;
                    }
                }
            }
        }
        for (int i: sortedArray) {
            System.out.println(i);
        }
    }
}

这会导致以下结果：

1 3 2 8 5 4

- Ueli Hofstetter

---

尝试对 int array[] = {5, 3, 2, 8, 6, 4}; 进行排序。 - Pushan Gupta

4个嵌套循环 --> 类似于：O(n^4)。非常低效！尽管如此，它仍然能够工作。 - Andre Kampling

@AndreKampling 我认为你误解了 while 循环 - 它们两个都在常数时间内完成（它们只运行一次或根本不运行）- 应该是 O(n^2)。 - Hulk

Answer 3

您的代码有点像冒泡排序，但您只比较每个相邻的元素。这里是一个使用两个for循环的工作代码，可以原地排序。它不一定比较直接相邻的元素，而是查找下一个奇数以与当前奇数进行比较。

此外，在将您的array复制到sortedArray时存在小错误，因为您在循环中这样做：sortedArray = array;，这只是复制了数组引用。在下面的工作代码中，我采用了您的解决方案并进行了更改。我也只是在排序开始之前复制了数组，以便源数组不变。

内部for循环从外部for循环的索引加1开始。此外，内部循环仅循环到结束前的一个元素。在最坏的情况下，它将需要n-1 * n/2 = n^2/2 - n/2次操作，这导致像常规冒泡排序一样的O(n^2)。 代码和ideone上的工作示例:

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

      int[] sortedArray = new int[array.length];
      System.arraycopy(array, 0, sortedArray, 0, array.length);

      for (int i = 0; i < sortedArray.length - 1; i++)
      {
         /* is current odd, if so search next odd */
         if (sortedArray[i] % 2 != 0)
         {
            /* search for next odd and compare */
            for (int j = i + 1; j < sortedArray.length; j++)
            {
               if ((sortedArray[j] % 2 != 0) && (sortedArray[i] > sortedArray[j]))
               {
                  int temp = sortedArray[i];
                  sortedArray[i] = sortedArray[j];
                  sortedArray[j] = temp;
               }
            }
         }
      }
      for (int i: sortedArray)
      {
         System.out.println(i);
      }
   }
}

输出：

1
3
2
8
5
4

- Andre Kampling

Answer 4

给定未排序的数组A：创建两个向量实例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，它返回Vector中的第一项，然后将其从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）。

排序后，按照原始顺序将偶数和排序后的奇数拼接回去。从向量E和S中按顺序取元素并读取向量B，这样可以保持偶数的顺序，因为它们最初是按顺序放入向量E中的，并且它们被按顺序放回去了。

- user1258361

---

我还应该补充一点，我的答案比其他人发布的二次方程式（更慢）的答案运行速度更快（通过算法分析）。特别是，每个循环操作最坏情况下都以线性时间（与输入数组的大小）运行，并且排序操作以n log n时间运行（使用生产级别的排序算法，例如quicksort或mergesort），甚至如果您使用数据相关排序，如基数排序，则以线性时间运行。 - user1258361

非常类似于GhostCat在此问题的顶部给出的答案的实现：https://dev59.com/j1cO5IYBdhLWcg3wgRsG#45714248，但不使用Java 8的功能。我只是因为有用的解释而点赞了它！ - Andre Kampling