计数排序算法的变化？

我意识到这不是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

计数排序算法的变化？

回答

相关问题