比较计数排序 |
---|
|
类别 | 排序算法 |
---|
资料结构 | 数组 |
---|
|
平均时间复杂度 | |
---|
最坏时间复杂度 | |
---|
最优时间复杂度 | |
---|
空间复杂度 | |
---|
|
比较计数排序(英语: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。
|
---|
理论 | |
---|
交换排序 | |
---|
选择排序 | |
---|
插入排序 | |
---|
归并排序 | |
---|
分布排序 | |
---|
并发排序 | |
---|
混合排序 | |
---|
其他 | |
---|
|