如何跳过特定的数组索引？

Question

需要对数组中的奇数值进行排序，但偶数值必须保留在原地。

以下是我的代码：

public static int[] sortArray(int[] array) {

    int length = array.length;
    int temp = 0;


    for (int i = 0; i < length; i++) {
        for (int j = 1; j < length - i; j++) {
            if (j > 0 && array[j] % 2 == 0)continue;

                if (array[j - 1] > array[j]){
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                }
            }
        }

    return array;
}

输入：new int[]{5, 3, 2, 8, 1, 4, 0}

输出：[1, 3, 5, 2, 8, 4, 0]

但我需要：[1, 3, 2, 8, 5, 4, 0]

如何跳过数组中的某些索引？

认为应该使用continue运算符来解决，但我不知道如何操作。

- IMBABOT

---

当array[j]为奇数时，你不能仅仅交换它与其直接前驱的位置，因为其前驱可能是偶数。你需要找到最近的奇数前驱来确定是否需要进行交换。 - pjs

Answer 1

在我看来，这段代码在逻辑上是错误的。因为如果你使用这段代码交换数字，

temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;

您不能保留偶数的位置。

那么，只需在数组中搜索奇数并对其进行排序如何？

- Sang Won

---

然后我需要按照它们在数组中的位置进行数字排序。对奇数进行排序不是问题，问题是将其放回到数组中的原始位置，并且不要与偶数混淆。偶数应保留在原位。 - IMBABOT

@IMBABOT 这不是问题。首先，将奇数的索引存储在一个数组中。然后，仅对奇数进行排序。最后，将每个奇数放置到存储的索引数组给定的索引位置上。 - eozd

Answer 2

对于像冒泡排序这样的简单算法，您可以使用continue来忽略偶数值。

for(int i=0; i<ar.length; i++) {
    if(ar[i] % 2 == 0) continue;
    for(int j=i; j<ar.length; j++) {
        if(ar[j] % 2 == 0) continue;

        if(ar[i] > ar[j]) {
        int temp = ar[i];
        ar[i] = ar[j];
        ar[j] = temp;
    }
}

- Prabhat Ranjan

---

对于输入 [3, 1, 5, 2, 8, 4, 0]，期望输出为 [1, 3, 2, 8, 5, 4, 0]。 - IMBABOT

你的陈述 - “但是偶数值必须保持在它们的位置上。”：2从第3个索引移动到第2个索引？（以数组索引为单位），8从第4个移动到第3个索引。 - Prabhat Ranjan

Answer 3

请使用以下代码替代：

public static int[] sortArray(int[] array) {

    int length = array.length;

    for (int i = 0; i < length - 1; i++) {
        int k = -1; // The index of last odd element
        for (int j = 0; j < length - i; j++)
            if (array[j] % 2 != 0) {
                if (k >= 0 && array[k] > array[j]) {
                    int temp = array[k];
                    array[k] = array[j];
                    array[j] = temp;
                }
                k = j;
            }
    }

    return array;
}

- John McClane

---

提示：返回数组是可选的，因为外部数组将被修改。 - User8461

Answer 4

只是为了好玩:

使用Lambda和Stream ;-)

import java.util.Arrays;

public class IntSort {

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

        sortOnlyOddRemainEven(array);

        System.out.println(Arrays.toString(array));
    }

    public static void sortOnlyOddRemainEven(int[] array) {

        // get list of sorted odd numbers
        int[] odd = Arrays.stream(array).filter( x -> x % 2 != 0).sorted().toArray();

        int c = 0;
        for (int i = 0; i < array.length; i++) {
            if(array[i] % 2 != 0)
            {
                // replace each odd number in the array with the sorted one
                array[i] = odd[c++];
            }
        }
    }
}

- User8461

---

你也可以用流（streams）代替 for 循环。 - Koray Tugay

你是指map函数还是其他更好的解决方案？[Map函数不是一个好的版本] (https://pastebin.com/MntMxaD5) - User8461

流并不总是比for循环更好。 - User8461

请查看我的回答。 - Koray Tugay

@KorayTugay：pop() 是个好主意；-) - User8461

Answer 5

另一个可能的解决方案是将原始数组包装在一个OddArray类中，这使得底层的原始数组看起来只持有奇数项。大致如下所示：

class OddArray {

  int[] baseArray;

  // Constructor
  OddArray(int[] base) {
    this.baseArray = base;
  }

  // Getter
  public int get(int index) {
    return baseArray[2 * index + 1];  // Odd entries only.
  }

  // Setter
  public void set(int index, int value) {
    baseArray[2 * index + 1] = value;  // Odd entries only.
  }

  // Return changed baseArray.
  public int[] getBaseArray() {
    return baseArray;
  }

} // end class OddArray

需要添加一些错误检查等，但它隐藏了所有偶数位置，使您可以将数组视为仅存在奇数位置，并按0、1、2等编号。 排序完成后，请调用OddArray.getBaseArray()以检索整个数组。

- rossum

Answer 6

使用流的另一种答案：

import java.util.Arrays;
import java.util.LinkedList;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class IntSort {

    public static void main(String[] args) {
        int[] array = new int[]{5, 3, 2, 8, 1, 4, 0};
        final int[] result = sortOnlyOddRemainEven(array);
    }

    public static int[] sortOnlyOddRemainEven(int[] array) {
        final LinkedList<Integer> collect;
        collect = Arrays.stream(array)
                        .filter(x -> x % 2 != 0)
                        .boxed()
                        .sorted()
                        .collect(Collectors.toCollection(LinkedList::new));

        return IntStream.of(array)
                        .map(value -> value % 2 != 0 ? collect.pop() : value)
                        .toArray();
    }
}

- Koray Tugay