比較計數排序 |
---|
概況 |
---|
類別 | 排序演算法 |
---|
資料結構 | 陣列 |
---|
複雜度 |
---|
平均時間複雜度 | |
---|
最壞時間複雜度 | |
---|
最佳時間複雜度 | |
---|
空間複雜度 | |
---|
相關變數的定義 |
---|
比較計數排序(英語: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])
參考資料
- ^ Knuth, The Art of Computer Programming, 5.2.
- ^ The winner of that particular honor: Dave Ackley, personal interview, Novermber 26, 2013。
- ^ ALGORITHMS TOLIVE BY The Computer Science of Human Decisions: Brian Christian, Tom Griffiths。
|
---|
| 理論 | |
---|
| 交換排序 | |
---|
| 選擇排序 | |
---|
| 插入排序 | |
---|
| 合併排序 | |
---|
| 分佈排序 | |
---|
| 並行排序 | |
---|
| 混合排序 | |
---|
| 其他 | |
---|
|