計數排序算法的變化？

我意識到這不是CLRS中所述的標準計數排序，但是我的簡化版本缺少標準計數排序的功能嗎？我意識到我只能分類正整數，但這應該很容易調整（通過使用地圖）。計數排序算法的變化？

def count_sort(array): 
    maximum = max(array) 
    minimum = min(0, min(array)) 
    count_array = [0]*(maximum-minimum+1) 

    for val in array: 
     count_array[val] += 1 

    sorted_array = [] 
    for i in range(minimum, maximum+1): 
     if count_array[i] > 0: 
      for j in range(0, count_array[i]): 
       sorted_array.append(i) 

    return sorted_array 

array = [3,2,-1,1,5,0,10,18,25,25] 
print array 
print count_sort(array)

編輯：爲什麼我認爲這是沒有標準計數排序是因爲蓋在麻省理工學院開放式講座的算法似乎稍微複雜的原因（http://youtu.be/0VqawRl3Xzs?t = 34m54s）。

來源

2012-02-14 Zubair Khan

什麼讓你覺得這不算數？這對我來說完全有效。 – templatetypedef 2012-02-14 08:56:58

是的，我也沒有看到問題。 FWIW，你甚至不需要使用地圖來處理負數 - 只需創建一個足夠大的'count_array'來容納它們，並讓負指數環繞。 – 2012-02-14 09:42:07

沒有使用內建的'max（）'有一個特別的原因？ – 2012-02-14 09:48:39

-1

你的意思是http://en.wikipedia.org/wiki/Counting_sort？

如果是的話，它幾乎和你的代碼相似。但它有一個改進：「在這裏保留了具有相同密鑰的項目的相對順序，即這是一個穩定的排序。」因此，如果您對鍵值字典進行排序，則如果值相等，則這些值的順序將保持不變。

來源

2012-02-14 09:37:01 Archeg

不，它不穩定，創建的數組不包含初始元素的拷貝，但它是使用'i'索引創建的。 – Kru 2012-02-14 09:43:44

你能解釋一下嗎？引號中的那個短語只是從wiki中複製而來。我認爲作者的意思是穩定的排序是用相同的密鑰保存項目順序的排序。也許這個詞在這裏用得不好，但無論如何從它之前的句子中可以清楚地看出，這是什麼意思 – Archeg 2012-02-14 10:03:07

好吧，在上面的算法中，整數是排序的。在維基百科上，鏈接到鍵的項目是。 – Kru 2012-02-14 11:00:48

你正在做一些奇怪的事情，你的最大和最小。試試這個：

def count_sort(array): 
    maximum = max(array) 
    minimum = min(array) 
    count_array = [0]*(maximum-minimum+1) 

    for val in array: 
     count_array[val-minimum] += 1 

    sorted_array = [] 
    for i in range(minimum, maximum+1): 
     if count_array[i-minimum] > 0: 
      for j in range(0, count_array[i-minimum]): 
       sorted_array.append(i) 

    print sorted_array 

array = [3,2,-1,1,5,0,10,18,25,25] 
print array 
count_sort(array)

來源

2012-02-14 10:24:27

我沒有看到你數排序的方式問題，反正一些建議，你的代碼浮現在腦海中，也許能感興趣。

例如行：

minimum = min(0, min(array))

可以替換爲：

minimum = min(0, *array)

如果您在python-2.x中使用的xrange()代替range()跑了你的代碼，所以你可以改變：

for i in range(minimum, maximum+1):

附：

for i in xrange(minimum, maximum+1):

對於最後的循環，你實際上並不需要range()可言，檢查出的問題pythonic way to do something N times，所以你可以改變：

for j in range(0, count_array[i]): 
    sorted_array.append(i)

有：

for _ in itertools.repeat(None, count_array[i]): 
    sorted_array.append(i)

來源

2012-02-14 10:44:17

計數排序算法的變化？

回答

相關問題