比較計數排序

比較計數排序
概況
類別	排序演算法
資料結構	陣列
複雜度
平均時間複雜度	$O(n^{2})$
最壞時間複雜度	$O(n^{2})$
最佳時間複雜度	$O(n^{2})$
空間複雜度	$O(n^{2})$
相關變數的定義

比較計數排序（英語：Comparison Counting Sort）是一種穩定的線性時間排序演算法，此種演算法時間複雜度雖然是平方時間，但它是擁有較強抗干擾能力和穩固性的排序演算法。

比較計數排序的特徵

此種演算法把每個項目與其它項目作比較，計數出每個項目大於(或小於)它的項目個數，此數字及可當作各個項目排序的基準值。此種演算法與泡沫排序一樣時間複雜度都是平方時間，不受傳統電腦科學青睞，但容錯率超群。

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])