比較計數排序

维基百科,自由的百科全书
跳到导航 跳到搜索
比較計數排序
分类 排序算法
数据结构 数组
最坏时间复杂度
最优时间复杂度
平均时间复杂度
最坏空间复杂度

比較计数排序(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 [l[C.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。