八大排序算法的Python实现__8__计数排序

环境

Python 3.5.2

原理

  • 找出列表中最大和最小的元素
  • 构建新列表,元素全为零,长度为最大值与最小值之间的差值加一
  • 统计待排序列表中每个值i出现的次数,并将新列表中下标为i-min的值加一
  • 将新列表中非零值的下标反转回原有元素i(即加上最小值),构建有序列表

源码

def count_sort(l):
    max = 0
    min = 1024

    for item in l:
        if item > max:
            max = item
        elif item < min:
            min = item

    count = [0]*(max-min+1)
    for index in l:
        count[index-min] += 1

    index = 0
    for i in range(max-min+1):
        for j in range(count[i]):
            l[index] = i+min
            index += 1

if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    count_sort(l)
    print(l)

时间复杂度

  • 最优时间复杂度:O(n+k)
  • 最坏时间复杂度:O(n+k)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):稳定

说点什么

  Subscribe  
提醒