30天挑战数据结构和算法之第8天计数排序

October 27 2019

今天挑战的内容是计数排序，这是一种不太常用的排序算法，因为太浪费内存空间了。

它的核心思想在于循环数组中的元素，以元素的值作为新数组的长度，统计相同元素的值出现的次数，最后根据新数组里有值的数据以及其下标进行排序。

先看看伪码

1
2
3
4
5
6
7
8
9
10
11
12
13
create key (counting) array

for each element in list

  increase the respective counter by 1

for each counter, starting from smallest key

  while counter is non-zero

    restore element to list

    decrease counter by 1

代码实现

javascript版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function MyCountingSort() {
	this.sort = function(array) {
		var keyArray = [];
		for(var i = 0; i < array.length; i++) {
			var key = array[i];
			if(keyArray[key]) {
				keyArray[key] += 1;
			} else {
				keyArray[key] = 1;
			}
		}
		var finalArray = [];
		for(var j = 0; j < keyArray.length; j++) {
			if(keyArray[j]) {
				while(keyArray[j] > 0) {
					finalArray.push(j);
					keyArray[j] -= 1;
				}
			}
		}
		return finalArray;
	}
}

var sorter = new MyCountingSort();
var list = [2,5,2,5,9,2];
var newlist = sorter.sort(list);
console.log(newlist);
ruby版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def my_counting_sort(array)
		keyArray = []
		(array.size - 1).times do |i|
				key = array[i]
				if keyArray[key]
						keyArray[key] += 1
				else
						keyArray[key] = 1
				end
		end
		finalArray = []
		(keyArray.size).times do |j|
				if keyArray[j]
						while keyArray[j] > 0
								finalArray.push(j)
								keyArray[j] -= 1
						end
				end
		end
		finalArray
end

list = [2,5,2,5,9,2]
newlist = my_counting_sort(list)
print newlist, "\n"
Java版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class MyCountingSort {
	public static void main(String []args){
		//排序的数组
		int a[] = {2,5,2,5,9,2};
		int b[] = countSort(a);
		for(int i : b){
			System.out.print(i + "  ");
		}
		System.out.println();
	}
	public static int[] countSort(int []a){
		int b[] = new int[a.length];
		int max = a[0], min = a[0];
		for(int i : a){
			if(i > max){
				max = i;
			}
			if(i < min){
				min = i;
			}
		}
		//这里k的大小是要排序的数组中，元素大小的极值差+1
		int k = max - min + 1;
		int c[] = new int[k];
		for(int i = 0; i < a.length; ++i){
			c[a[i]-min] += 1;//优化过的地方，减小了数组c的大小
		}
		for(int i = 1; i < c.length; ++i){
			c[i] = c[i] + c[i-1];
		}
		for(int i = a.length-1; i >= 0; --i){
			b[--c[a[i]-min]] = a[i];//按存取的方式取出c的元素
		}
		return b;
	}
}

Java版本的代码是我在维基上找的。它和前两个脚本语言的实现版本不同之处在于，javascript和ruby支持动态生成数组，无需给定数组长度，但是Java不行。可以看到Java的实现算法更复杂和抽象一点。

时间复杂度

当输入的元素是n个0到k之间的整数，那么时间复杂度就是O(n+k)，k是数组中的最大值。这个时间复杂度可以从javascript的版本中得到体现。最优、最差以及平均时间复杂度都是O(n+k)。

空间复杂度

空间复杂度和时间复杂度一样也是O(n+k)，参照javascript版本中的实现，对数组长度的内存开销。

总结

因为要去理解Java版本的实现算法，以及一些其它的事情，导致这篇文章的发布进度落后了，很高兴没有停止我的挑战计划。说回算法，计数排序法是一种不太常用，但是稳定的排序算法。维基百科对它的评价是，计数排序不是比较排序，排序的速度快于任何比较排序算法。由于因为对内存空间的浪费，尤其是数组中有极大值的元素，这种情况下就不考虑技术排序了。

avatar

chilihotpot

You Are The JavaScript In My HTML