替换选择排序

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