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

作者: 流月0 | 来源:发表于2017-11-18 16:17 被阅读0次

    个人技术博客地址:http://songmingyao.com/


    原理

    • 找出列表中最大和最小的元素
    • 构建新列表,元素全为零,长度为最大值与最小值之间的差值加一
    • 统计待排序列表中每个值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)
    • 稳定性(多个元素等值的情况下是否会破坏原有顺序):稳定

    相关文章

      网友评论

        本文标题:八大排序算法的Python实现__8__计数排序

        本文链接:https://www.haomeiwen.com/subject/dunevxtx.html