java - QuickSort的修改(分区Hoare)，先偶数降序，然后奇数降序

Question

我有一个大问题要修改 Hoare 分区，以便它按降序排序:首先按偶数，然后按奇数。示例:arr[] = {1, 6, 7, 8, 4, 5}，输出:arr[] = {8, 6, 4, 7, 5, 1}。

我可以通过将数组分别划分为偶数和奇数并分别对每个部分进行排序来做到这一点。但是，任务是重新设计快速排序，以便您不必划分数组。

下面是我的分区，我的方向正确吗？

static int partition(int []arr, int low,  
                                int high) 
{ 
    int pivot = arr[low]; 
    int i = low - 1, j = high + 1; 

    while (true) 
    { 

        do
        { 
            i++; 
        } while ((arr[i] > pivot && ((arr[i]%2==0 && pivot%2==0) || (arr[i]%2!=0 && pivot%2!=0))) || (arr[i]<pivot && arr[i]%2==0 && pivot%2!=0)); 


        do
        { 
            j--; 
        } while (arr[j] < pivot); 

        if (i >= j) 
            return j; 
        int temp = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = temp; 
    } 
} 

Answer 1

你在第一个循环的情况下做了努力，但是:

• 这并不完全正确
• 它也应该与第二个循环条件类似地应用

出于第二个原因，定义一个比较函数可能会更好:

    private static int cmp(int a, int b) {
        if (a % 2 != b % 2) return a % 2 - b % 2; 
        return b - a;
    }

现在循环条件应该很简单:

• while (cmp(arr[i], pivot) < 0)
• while (cmp(arr[j], pivot) > 0)