计算机科学

首页 > 计算机科学

比较计数排序

2018-08-28 09:41:46     所属分类:排序算法
比较计数排序
分类 排序算法
数据结构 数组
最坏时间复杂度
最优时间复杂度
平均时间复杂度
最坏空间复杂度

比较计数排序(Comparison Counting Sort)[1]是一种稳定的线性时间排序算法,此种算法时间复杂度虽然是平方时间,但它是拥有较强抗干扰能力和稳固性的排序算法[2]

比较计数排序的特征

此种算法把每个项目与其它项目作比较,计数出每个项目大于(或小于)它的项目个数,此数字及可当作各个项目排序的基准值。此种算法与气泡排序一样时间复杂度都是平方时间,不受传统计算机科学青睐,但容错率超群[3]

Python 2.7 实现

def compare_counter_sort(l):
    C = 
    for i in l:
        count = 0
        for j in l:
            if j < i:
                count += 1
                
        while(count in C):
            count += 1
            
        C.append(count)

    return lC.index(i) for i in xrange(len(l))

if __name__ == '__main__':
    print compare_counter_sort(4, 5, 1, 2, 5, 6, 5, 5, 5, 1)

参考资料

  1. ^ Knuth, The Art of Computer Programming, 5.2.
  2. ^ The winner of that particular honor: Dave Ackley, personal interview, Novermber 26, 2013。
  3. ^ ALGORITHMS TOLIVE BY The Computer Science of Human Decisions: Brian Christian, Tom Griffiths。

上一篇:外排序
下一篇:Bogo排序
相关推荐