java - 仅对数组的一半实现快速排序

Question

我有一个练习，我必须改进算法。该算法采用一个数组，并将偶数放在左侧(已排序)，将赔率放在右侧(未排序)。该算法效率低下，所以我必须改进它。

这是练习的原始代码，我必须“改进”:

public void what (int [] arr) {
    int temp;
    for (int i=0; i<arr.length; i++)
        if (arr[i]%2 == 0) {
            temp = arr[i];
            for (int j=i; j>0; j--)
                arr[j] = arr[j-1];
            arr[0] = temp;
    }
}

我想在这个练习中实现快速排序算法，但问题是我不知道如何使用主元:通常，主元是中位数，数组的一半较小，另一半较小更大。

这里的问题是左边部分必须是偶数，右边部分必须是奇数。

我必须以低于 O(n^2) 的效率实现这种“排序”。

有什么想法吗？

谢谢!

Answer 1

拥有两个索引怎么样，一个从开头开始 (i=-1)，另一个从结尾开始 (j=a.length)。递增 i 并放入偶数，递减 j 放入奇数。迭代完成后，我将指向偶数元素的最后一个元素。应用快速排序，以中间元素为基准(即从 0 到 i)。