替换选择排序

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;
        }
}

替换选择排序

Replacement selection sorting

java

sorting

heap

replace