1

我有一个练习，我必须改进一个算法。该算法采用一个数组并将偶数放在左侧（SORTED），将赔率放在右侧（NOT-SORTED）。该算法效率低下，因此我必须对其进行改进。

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

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) 的效率实现这种“排序”。

有任何想法吗？

谢谢！

4

3 回答 3

0

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

于 2013-06-15T12:52:51.447 回答
0

建议一：线性通过数组并将其拆分为两个 - 偶数元素和奇数元素。这需要 Theta(n) 时间。当您进行线性扫描并检查每个元素时，您可以找出哪个是最大的，哪个是最小的元素。然后你可以对偶数数组实现计数排序。计数排序示例：

计数排序互动 计数排序视频

计数排序运行时间是 O(n) 摊销的，所以你的算法的整体运行时间是 O(n)。

建议二：如果你想使用快速排序，将每个奇数威胁为+无穷大，它自然会排在列表的末尾，无需比较。如果您碰巧选择了奇数支点，请将其放在最后，然后再试一次。我建议使用随机枢轴而不是第一个/最后一个。

于 2013-06-15T13:12:55.333 回答
0

正如@zerocool 建议的那样，由代码实现：

private static int medianEven(int [] arr){
        int i=-1, j=arr.length; int temp=0; int w=0;
        while ((w<j)){
            if (arr[w]%2==0){
                i++;
                w++;
            }
            else
            {
                temp=arr[j-1];
                arr[j-1]=arr[w];
                arr[w]=temp;
                j--;
            }
        }
        return i;

    }

之后，从 arr[0] 到 arr[i] 调用 quickSort 方法：

quicksort(arr,0,i);

谢谢你的建议。

于 2013-06-15T14:20:11.757 回答