替換選擇排序

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