Java排序之计数排序

计数排序思路

计数排序适用于有明确范围的数组，比如给定一个数组，且知道所有值得范围是[m,n]。这个时候可以使用一个n-m+1长度的数组，待排序的数组就可以散在这个数组上，数组的值就是当前值的个数，再经过一次遍历展开，得到的数组就有序了。

1. 新建一个长度为n-m+1的临时数组
2. 遍历待排序数组，它的值-m作为临时数组下角标，这个位置的值加1
3. 遍历结束，临时数组就存储了每个值得个数
4. 最后将它展开赋值给原数组

Java代码实现

package com.wangjun.arithmetic;

import java.util.Arrays;

public class SortCount {

	public static void main(String[] args) {

		//测试

		int[] arr = {1,4,6,7,5,4,3,2,1,4,5,10,9,10,3};

		sortCount(arr, 1, 10);

		System.out.println(Arrays.toString(arr));

	}

	//计数排序的初步实现，使用了多余的空间，可以尝试不使用多余的空间

	public static void sortCount(int[] arr, int m, int n) {

		int len = arr.length;

		int[] tem = new int[n - m + 1];

		for(int i = 0; i < len; i++) {

			tem[arr[i] - m] += 1;

		}

		for(int i = 0, index = 0; i < tem.length; i++) {

			int item = tem[i];

			while(item-- != 0) {

				arr[index++] = i + m;

			}

		}

	}

}

打印结果：

[1, 1, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 9, 10, 10]