[原]14-Python3实用教程-排序算法-计数排序

计数排序

计数排序的基本思想在于给定的输入序列中的每一个元素x,确定该序列中值小于等于x元素的个数,然后将x直接存放到最终的排序序列的正确位置上。

局限性

  • 当数列的最大和最小值差距过大时,并不适用计数排序
  • 当数列元素不是整数,并不适用计数排序

步骤:

需要知道列表中的最大值,最小值

1、创建一个新列表,长度为原列表的最大值+1

2、遍历原列表中的元素,以原列表中的元素作为新列表的索引,以原列表中的元素出现次数作为新列表的元素值。

3、再遍历新列表。

代码:

仅以正整数和零的列表为例,包含负整数的话,计算上偏移量就行了

def sort(arr, max):
    mid_list = [0 for i in range(max+1)]
    ret_list = []

    for item in arr:
        mid_list[item] = mid_list[item] + 1

    for index, value in enumerate(mid_list):
        if value != 0:
            for i in range(value):
                ret_list.append(index)
    return ret_list



seq_list = [8, 2, 3, 9, 3, 3, 2, 0, 12]

print(sort(seq_list, 12))
#[0, 2, 2, 3, 3, 3, 8, 9, 12]
分享 提问
comments powered by Disqus