如何使用O（n）額外空間實現穩定的快速排序算法？

與一般的快速排序算法不同，我可以使用額外的數組來執行穩定的快速排序。我知道如何隨機選擇分區和相應的分區，但我無法弄清楚如何使用附加數組來使其穩定。如何使用O（n）額外空間實現穩定的快速排序算法？

來源

2015-09-20 humblenoob

什麼是不穩定的快速排序？ –

你的代碼在哪裏？ –

想到最簡單的方法是將初始索引存儲在數組中（1,2,3等），並在交換數據時交換它們。

然後在比較中，如果兩個元素相同，則比較它們的指標，從而使其穩定。

來源

2015-09-20 02:23:22 Blindy

或者，根本不要修改數組中的數據，但要從指向原始數組元素的新數組開始。然後簡單地對指針數組進行排序，首先比較指向的對象，然後將指針比作一個決勝因素。這是一種很好的技術，因爲它可以對原始副本無法修改的數據進行排序。但是，如果您確實需要重新排序原始數組，那麼這是最後一個額外的（稍微不重要的）步驟。 –

是的，這是關於你將使用更多，有序數組或原始映射。我認爲，既然你排序，你將需要排序的數組:) – Blindy

如果使用O（n）額外的空間，可以使用合併排序，它已經穩定。如果要使用索引或指針數組，通常使用兩個索引或指針數組，但如果索引或指針使用像鏈接列表一樣，則索引或指針的單個數組就足夠了，其中每個索引或指針指向到下一個元素。每個列表的末尾將是索引== -1或指針== null。局部變量用於跟蹤合併算法中列表的開始，並且合併算法返回列表值的單個開始。 – rcgldr

正如Blindy和R所建議的那樣，您可以對索引進行排序，然後可以使用循環排序的變體對原始數組進行排序，副作用是排序後的索引將重新排列爲0到n-1。每一步都要放置一個元素，所以時間複雜度是O（n）。

void reorder_according_to(int array[], size_t indices[], size_t len) 
{ 
size_t i, j, k; 
int t; 
    for(i = 0; i < len; i++){ 
     if(i != indices[i]){ 
      t = array[i]; 
      k = i; 
      while(i != (j = indices[k])){ 
       array[k] = array[j]; 
       indices[k] = k; 
       k = j; 
      } 
      array[k] = t; 
      indices[k] = k; 
     } 
    } 
}

來源

2015-09-20 09:02:24 rcgldr

由於各種技術原因，如果調整爲使用TYPE *數組，TYPE **指針，size_t len'，則此函數會更好。 –

的確，但它應該仍然遵循最佳實踐，例如使用size_t來表示size/indices，因爲int可能會溢出。 :-)使用指針更多的是技術細節（使用'qsort' API，你必須對指針進行排序，而不是索引，因爲'qsort'沒有附加的上下文參數來傳遞給比較函數），但它不如果你使用自己的排序方式，那麼排序索引的排序方式很簡單。 –

Uhg。如果沒有明確的合約，您對元素的大小/數量有限制，'size_t'是唯一正確/安全的使用方法。令人沮喪的是，有人在SO上建議反對...... :-( –

如何使用O（n）額外空間實現穩定的快速排序算法？

回答

相關問題