排序算法——计数排序

描述

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法思想

1. 开辟一个临时数组
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

动图演示

代码实现

import java.util.*;
import java.lang.*;

class Rextester
{  
   public static void main(String args[]) {
	   int[] data = {2,3,8,7,1,2,2,2,7,3,9,8,2,1,4,2,4,6,9,2,0,0};
		 countingSort(data);
	   System.out.println(Arrays.toString(data));
   }
	
	public static void countingSort(int[] data) {
		int[] temp = new int[data.length];
		for(int i = 0; i< data.length; i++) {
			temp[data[i]] = temp[data[i]]+1;
		}
		int idx = 0;
		for(int i = 0;i<temp.length;i++) {
			while(temp[i]>0){
				temp[i] -= 1;
				data[idx++] = i;
			}
		}	
	}
}