数据结构之排序算法Java实现（8）—— 线性排序之计数排序算法

计数排序是线性排序。

升序排序：

public  void sortByAsc(int[] data) {
		if(data == null || data.length <= 1)
			return;
		/** find the range of data */
		int range = data[0];
		for(int i = 1; i< data.length; i++){
			if(range < data[i]){
				range = data[i];
			}
		}
		 if (range <= 0) {  
			 System.out.println("边界不能为负数");
             return; 
         }  
		/** count sort */
		countSortByAsc(data,range);
		
	}

	private void countSortByAsc(int[] data, int range) {
		
		/**建一个长度为range+1的的数组countArray，里面的每一个元素初始都置为0(Java里面默认就是0)。*/
		int[] countArray = new int[range + 1];
		/**遍历待排序的数组，计算其中的每一个元素出现的次数，比如一个key为i的元素出现了3次，那么countArray[i]=3。*/
		for(int i = 0;i < data.length; i++){
			int val = data[i];
			if(val < 0 || val > range){
				System.out.println("下标超界");
	             return;
			}
			countArray[val] += 1;
		}
		for(int i = 0,index = 0;i < countArray.length ; i++){
			for(int j = 0; j <countArray[i];j++ ){
					data[index] = i;
					index++;
			}

		}
		
	}

　　降序排序：

public  void sortByDesc(int[] data) {
		if(data == null || data.length <= 1)
			return;
		/** find the range of data */
		int range = data[0];
		for(int i = 1; i< data.length; i++){
			if(range < data[i]){
				range = data[i];
			}
		}
		 if (range <= 0) {  
			 System.out.println("边界不能为负数");
             return; 
         }  
		/** count sort */
		countSortByDesc(data,range);
		
	}

	private void countSortByDesc(int[] data, int range) {
		/**建一个长度为range+1的的数组countArray，里面的每一个元素初始都置为0(Java里面默认就是0)。*/
		int[] countArray = new int[range + 1];
		/**遍历待排序的数组，计算其中的每一个元素出现的次数，比如一个key为i的元素出现了3次，那么countArray[i]=3。*/
		for(int i = 0;i < data.length; i++){
			int val = data[i];
			if(val < 0 || val > range){
				System.out.println("下标超界");
	             return;
			}
			countArray[val] += 1;
		}
		for(int i = countArray.length - 1,index = 0;i >=0 ; i--){
			for(int j = 0; j <countArray[i];j++ ){
					data[index] = i;
					index++;
			}

		}
		
	}