计数排序

素颜马尾好姑娘i 2022-05-28 00:20 219阅读 0赞

### 计数排序 ###

##### 算法描述：是一种通过计数来达到排序的方法。 #####

![20180326152550965][]

1.选出数组的最大值k，创建一个k+1长度的数组countArray，countArray的数组下标代表array数组中的元素值，而countArray中的元素值代表的是array中每一个元素的出现次数。

![20180326152600451][]

2.遍历array数组，统计每个元素的出现次数。例如array\[0\]是7，那么countArray\[7\]++，因为countArray的下标代表array中的数。统计完如下图。

![20180326152608660][]

3.对countArray进行循环，对每一个元素countArray\[i\] = countArray\[i\] + countArray\[i-1\]，目的是统计每一个元素前面有多少个小于它的元素。

![20180326152617314][]

4.复制array数组存到temp中，循环temp，将temp中i位置的的元素放到array中的--countArray\[temp\[i\]\]位置。也就是array\[--countArray\[temp\[i\]\]\] = temp\[i\]。

##### 注意: #####

1.数组只能是整形数组。  
2.数组元素必须都大于0。  
3.计数排序是一种拿空间换时间的排序算法。

##### 时间复杂度：O(n) #####

##### 空间复杂度：O(n) #####

java实现：

public static void countSort(int[] array) {
    		int max = getMax(array); // 获取数组的最大值，数组所有值都在0 - max之间
    		int[] countArray = new int[max + 1]; // 创建一个max+1大小的数组用于表示从0 - max所有数字的重复次数
    		int[] resultArray = new int[array.length];
    		resultArray = Arrays.copyOf(array, array.length);// 用于存储排好序的数组
    		for (int i = 0; i < array.length; i++) { // 循环array数组
    			countArray[array[i]] += 1; // 因为countArray的下标代表array中的数字，而值代表array中元素的出现次数，所以countArray[array[i]]++
    		}
    		for (int i = 1; i < countArray.length; i++) {
    			countArray[i] += countArray[i - 1]; // 将countArray中的每一个元素变成与前一个元素相加的和
    		}
    		for (int i = 0; i < resultArray.length; i++) {
    			int position = countArray[resultArray[i]]; //找出要排序的位置
    			array[position-1] = resultArray[i]; //位置减一
    			countArray[resultArray[i]] -= 1; // 统计数要减一
    		}
    	}
    
    	private static int getMax(int[] array) {
    		int max = array[0];
    		for (int i = 0; i < array.length; i++) {
    			if (array[i] < 0) {
    				throw new RuntimeException("数组中有数小于0");
    			}
    			if (max < array[i]) {
    				max = array[i];
    			}
    		}
    		return max;
    	}

GitHub地址： [https://github.com/xckNull/Algorithms-introduction.git][https_github.com_xckNull_Algorithms-introduction.git]

[20180326152550965]: /images/20220528/c290737dee734c41aa3e1fc48812c4a0.png
[20180326152600451]: /images/20220528/8fae5d442ba84ce8ba5988b5ab4bf814.png
[20180326152608660]: /images/20220528/8361991a1a274e77a5f12f124ab62f66.png
[20180326152617314]: /images/20220528/553bf6e2ff6441c09033b256e0352537.png
[https_github.com_xckNull_Algorithms-introduction.git]: https://github.com/xckNull/Algorithms-introduction.git