java - 替换选择排序

Question

所以我一直在尝试实现这个算法，但我不太确定从哪里开始。基本上，根据我的理解，您可以通过两种方式实现它，通过排序顶层是最小值(minHeap)或顶层是所有内容的最大值(maxHeap)。我在谷歌上搜索了很多关于这两种方法的信息，但我无法掌握如何实际实现它。我一般不明白我会说，有人可以解释一下这是如何工作的吗？就像 minHeap 或 maxHeap 应该如何工作一样。预先感谢您!

Answer 1

我假设您对数组中的二进制堆实现有基本的了解。

假设您有一个整数数组，想要按升序排序。一种方法是重新排列数组中的项目，使它们形成最大堆。

然后，将顶部项目(数组中最大的项目)与堆中的最后一个项目交换，将堆计数减 1，并将该项目从顶部向下筛选到堆中的新位置。最后，数组中的第一项将是下一个最大的项。您对每个项目重复此操作，并且您的数组已排序。

让我们举一个小例子。给定数组 [4,7,6,1,3,5,2]，您可以使用 Floyd 算法将它们重新排列到堆中。

for (int i = array.length/2; i >= 0; i--)
{
    siftDown(i);
}

这是一个 O(n) 操作。

完成后，数组将排列在二进制堆中。在这种情况下，堆将为[7,4,6​​,1,3,5,2]，或:

       7
     4   6
    1 3 5 2

因此，我们将根项与最后一项交换，得到:[2,4,6,1,3,5,7]。我们减少计数并将 2 筛选到适当的位置，给出:[6,4,5,1,3,2,7]，或堆表示:

       6
     4   5
    1 3 2

(我省略了 7，因为我们减少了计数。但它仍然位于数组的末尾。)

再次，将顶部项目与堆中的最后一个项目交换:[2,4,5,1,3,6,7]，减少计数，然后向下筛选:[5,4,2,1,3,6,7]:

      5
    4   2
   1 3

如果对堆中剩余的五个项目继续执行此操作，您最终将得到一个已排序的数组。

代码非常简单:

int count = array.length-1;
while (count > 0)
{
    swap(array[0], array[count]);
    --count;
    siftDown(0);
}

如果你想进行降序排序，你可以使用最大堆执行上述操作，然后反转数组(O(1) 操作)，或者可以构建一个最小堆来开始。

siftDown 方法只是将项目向下移动到正确的位置，遵循二进制堆构造的规则:

void siftDown(int index)
{
    // Left child is at index*2+1. Right child is at index*2+2;
    while (true)
    {
        // first find the largest child
        int largestChild = index*2+1;
        // if left child is larger than count, then done
        if (largestChild >= count)
        {
            break;
        }
        // compare with right child
        if (largestChild+1 < count && array[largestChild] < array[largestChild+1])
        {
            ++largestChild;
        }

        // If item is smaller than the largest child, then swap and continue.
        if (array[index] < array[largestChild])
        {
            swap(array[index], array[largestChild]);
            index = largestChild;
        }
        else
        {
            break;
        }
}