计数排序

目录

计数排序原理和步骤：

        完整代码实现：

---

计数排序原理和步骤：

         当一段数据比较集中在一个范围，比如 98，95，98，91，90，93，94，97，93，99，95，92；这段数据都集中在90 ~ 99 之间，那么使用计数排序来解决排序问题很方便快捷。

        第一步：

        先得到原始数组的最大值 和最小值的差值 a 。建立一个  a + 1 大小的计数数组。

        第二部：

        遍历原始数组，得到的原始数组的元素大小作为 计数数组的下标，并在计数数组对应下标位置元素大小加1，直到遍历完原始数组。

        第三步：

        遍历计数数组，给到原始数组。

        代码：

public static void countSort(int[] arr) {//取得原始数组最大值和最小值int max = arr[0];int min = arr[0];for (int i = 1; i < arr.length; i++) {if(arr[i] < min) {min = arr[i];}if(arr[i] > max) {max = arr[i];}}//建立计数数组int len = max - min + 1;int[] countArray = new int[len];//遍历原始数组for (int i = 0; i < arr.length; i++) {int index = arr[i];countArray[index]++;}//遍历计数数组给到原始数组int k = 0;for (int i = 0; i < countArray.length; i++) {while(countArray[i] != 0) {arr[k] = i;k++;countArray[i]--;}}}

        到这里，起始代码还没完全写好，如果是很大的数字范围，比如 90 ~ 99这种，就会出现错误，所以，在此基础上改成：

        

        这样原始数组原来的值先减去最小值得到的下标，之后在计数数组给回原始数组时在次加上最小值就能确保正常功能。 

        完整代码实现：

public static void countSort(int[] arr) {//取得原始数组最大值和最小值int max = arr[0];int min = arr[0];for (int i = 1; i < arr.length; i++) {if(arr[i] < min) {min = arr[i];}if(arr[i] > max) {max = arr[i];}}//建立计数数组int len = max - min + 1;int[] countArray = new int[len];//遍历原始数组for (int i = 0; i < arr.length; i++) {int index = arr[i]-min;countArray[index]++;}//遍历计数数组给到原始数组int k = 0;for (int i = 0; i < countArray.length; i++) {while(countArray[i] != 0) {arr[k] = i+min;k++;countArray[i]--;}}}

        计数排序是稳定的。