優化週期排序實施

Question

週期排序是一種就地排序，基於這樣的想法，即您排序的排列可以分解爲週期。如果你將每個循環旋轉一個位置，數組將被排序。這可以很容易地編碼，以便對陣列的寫入次數是任何就地排序所需的理論最小值（這對於閃存驅動器上的大量數據集非常好，您希望將寫入次數最小化裝置）。

是否有任何方法可以在保持原地排序並保持最佳寫入次數的同時提高code on Wikipedia的運行時間？還是最佳？

下面是實現（注意，range(a, b)去從a到b - 1） ：

# Sort an array in place and return the number of writes. 
def cycleSort(array): 
    writes = 0 
    # Loop through the array to find cycles to rotate. 
    for cycleStart in range(0, len(array) - 1): 
    item = array[cycleStart] 
    # Find where to put the item. 
    pos = cycleStart 
    for i in range(cycleStart + 1, len(array)): 
     if array[i] < item: 
     pos += 1 
    # If the item is already there, this is not a cycle. 
    if pos == cycleStart: 
     continue 
    # Otherwise, put the item there or right after any duplicates. 
    while item == array[pos]: 
     pos += 1 
    array[pos], item = item, array[pos] 
    writes += 1 
    # Rotate the rest of the cycle. 
    while pos != cycleStart: 
     # Find where to put the item. 
     pos = cycleStart 
     for i in range(cycleStart + 1, len(array)): 
     if array[i] < item: 
      pos += 1 
     # Put the item there or right after any duplicates. 
     while item == array[pos]: 
     pos += 1 
     array[pos], item = item, array[pos] 
     writes += 1 
    return writes 

Answer 1

該算法的昂貴的部分是找出其中每個項目去。其餘的部分是一次應用一個週期的置換。這段代碼需要O（n^2）找出物品的位置，O（n）實際移動它們。

如果你願意使用一些臨時存儲器（例如DRAM而不是閃存），你可以通過使用臨時指針數組，將其排序，然後使用結果移動實際數據。這就是你如何對重複移動它們的成本過高的大記錄進行排序。

如果你不允許有O（n lg（n））位的輔助存儲，我認爲你可能會運氣不好。只記錄要執行的排列需要log（n！）= O（n lg（n））個存儲位。所以你需要逐步計算排列（比如cycleSort），我看不出有什麼辦法可以做到這一點。