使用插入排序只对奇数进行排序

Question

我想在给定数组中使用插入排序对奇数进行排序，而不是触摸偶数，但偶数的位置会改变我不希望它们停留在奇数之间

EX:

int arr[] = {1,4,5,2,7,6,3,9,0}
The output should be = {1,3,5,7,9,4,2,6,0}

这是我的代码，我在其中写了插入代码，但我无法弄清楚问题的奇数部分的排序

如何将左边的奇数按升序排列，而将所有偶数放在右边而不排序？

public void InsertionOdd(int[] a) {
    for (int i = 1; i < a.length; i++) {
        
        int key = a[i];
        int j = i - 1;
        
        while(j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            j = j - 1;
        }
        
        a[j + 1] = key;
    }
    
    for (int i = 0; i < a.length; i++) {
        System.out.print(a[i]+" ");
    }
}

Answer 1

你需要改变两件事：

在为键变量赋值后添加验证int key = a[i]; if( key % 2 == 1)
如果键大于 a[j] 或者 a[j] 是偶数，请确保将所选元素移到左侧：while (j >= 0 && (a[j] > key || a[j]% 2 == 0)) 现在代码应该可以工作了。

Answer 2

这是一个采用比较器的替代方法。

当使用 compare(a,b) 比较两个值 a 和 b 时，比较器 returns -1, 0, 1 分别用于 a < b, a == b, and a > b。要为此方法构建一个比较器，需要特殊处理偶数，以便将它们推到列表的末尾。由于所需的顺序是升序，因此当 a < b 时 compare(a,b) 必须 return -1。要对 a 的偶数值强制执行此操作，请使用 a % 2 == 0，它必须 return 和 1。对于b，b % 2 == 0其中必须return一个-1。 a and b 的任何其他值将取决于 a.compareTo(b) 的结果。这可以使用比较器中的三元 (?:) 运算符来实现。

Comparator<Integer> comp = (a,b)-> a % 2 == 0 ? 1 : b % 2 == 0 ? -1 : 
                                        a.compareTo(b);

所以如果a是偶数，它return是一个1，如果b是偶数它return是一个-1，否则return是结果显式比较的。

这是它在您的方法中的工作原理。

public static void InsertionOdd(int[] arr, Comparator<Integer> comp) {
    
    for (int i = 1; i < arr.length; i++) {
        
        int key = arr[i];
        int j = i - 1;
        
        while (j >= 0 && comp.compare(key, arr[j]) < 0){
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        
        arr[j + 1] = key;
    }
}

这样做有几个好处。

除了比较部分之外，您没有修改方法的任何其他部分。所以你也可以通过其他比较器以不同的方式排序。
这也适用于正数和负数的混合。

请注意，您可以将比较器直接编码到方法中。但是，如果需要其他种类，它就不会那么通用。

使用插入排序只对奇数进行排序

Using Insertion-sort for sorting only odd numbers

java

numbers

insertion-sort