計(jì)數(shù)排序是一個(gè)非基于比較的線性時(shí)間排序算法。它對輸入的數(shù)據(jù)有附加的限制條件：
1、輸入的線性表的元素屬于有限偏序集S；
2、設(shè)輸入的線性表的長度為n，|S|=k（表示集合S中元素的總數(shù)目為k），則k=O(n)。
在這兩個(gè)條件下，計(jì)數(shù)排序的復(fù)雜性為O(n)。
計(jì)數(shù)排序算法的基本思想是對于給定的輸入序列中的每一個(gè)元素x，確定該序列中值小于x的元素的個(gè)數(shù)。一旦有了這個(gè)信息，就可以將x直接存放到最終的輸出序列的正確位置上。例如，如果輸入序列中只有17個(gè)元素的值小于x的值，則x可以直接存放在輸出序列的第18個(gè)位置上。
計(jì)數(shù)排序算法沒有用到元素間的比較，它利用元素的實(shí)際值來確定它們在輸出數(shù)組中的位置。因此，計(jì)數(shù)排序算法不是一個(gè)基于比較的排序算法，從而它的計(jì)算時(shí)間下界不再是Ω(nlogn)。另一方面，計(jì)數(shù)排序算法之所以能取得線性計(jì)算時(shí)間的上界是因?yàn)閷υ氐娜≈捣秶髁艘欢ㄏ拗疲磌=O(n)。如果k=n2,n3,..，就得不到線性時(shí)間的上界。
標(biāo)簽：
線性
輸入
排序
元素
上傳時(shí)間：
2015-10-30
上傳用戶：chenxichenyue
