ALGORTIHM ComparisonCountingSort(A[0...n-1])
//Sorts an array by comparison counting
//Input: Array A[0...n-1] of orderable values
//Output: Array S[0...n-1] of A's elements sorted in nondecreasing order
for i←0 to n-1 do
Count[i] ←0
for i←0 to n-2 do
for j←i+1 to n-1 do
if A[i]<A[j]
Count[j] ←Count[j]+1
else Count[i] ←Count[i]+1
for i←0 to n-1 do
S[Count[i]] ←A[i]
return S
不太常用的排序算法，时间复杂度 θ(n^2) 。需要额外的空间，不是在位排序。
主要思路是：
Count数组中的元素记录了A中对应序号元素的Ranking（等级，也就是比此个元素小的元素的个数）。
每次最外层循环，得出A[i]的Ranking（i从0到n-2)
内层循环,A[i]和A[i+1]到A[n-1]的所有元素比较。如果A[i]比a[j]小，就把A[j]的Ranking上升一个（＋1），否则就将A[i]的Ranking上升一个（＋1）。
最后后按照Ranking顺序将A数组的所有元素复制到S数组中，排序就算是完成了。
该算法对列表”60,35,81,98,14,
|
Array A[0...5] |
60 |
35 |
81 |
98 |
14 |
47 |
|
|
Count[0] |
Count[1] |
Count[2] |
Count[3] |
Count[4] |
Count[5] |
|
Initially |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
3 |
0 |
1 |
1 |
0 |
0 |
|
1 |
|
1 |
2 |
2 |
0 |
1 |
|
2 |
|
|
4 |
3 |
0 |
1 |
|
3 |
|
|
|
5 |
0 |
1 |
|
4 |
|
|
|
|
0 |
2 |
|
|
3 |
1 |
4 |
5 |
0 |
2 |
|
Array S[0…5] |
14 |
35 |
47 |
60 |
81 |
98 |