修改QuickSort（分区Hoare），先将偶数降序，再将奇数降序。

Question

我有一个很大的问题，就是要修改Hoare分区，让它按降序排序：先按偶数排序，再按奇数排序。例如：arr[] = {1，6，7，8，4，5}，出：arr[] = {8，6，4，7，5，1}。

我可以通过将数组分别分为偶数和奇数，并分别对这些部分进行排序来实现。然而，任务是重新设计quicksort，使你不必对数组进行划分。

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

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)