Java实现计数排序经典代码和算法思路

本文重点讲解Java实现计数排序经典代码和算法思路。

计数排序核心思想

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

计数排序就是一个排序时不比较元素大小的排序算法。

对一定范围内的整数排序的时候速度非常快，优于其他算法。同时局限性也比较大，只能对于整数进行排序，并且待排序元素分布较连续，跨度小的情况。

如果一个数组里所有元素都是整数，且在0—k以内，那对于这个数组的每个元素来说，如果能知道数组里有多少项小于或等于该元素，就能准确地给出该元素在排序后的数组的位置。

算法描述

找出待排序的数组中最大和最小的元素;
统计数组中每个值为i的元素出现的次数，存入数组C的第i项;
对所有的计数累加(从C中的第一个元素开始，每一项和前一项相加);
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

计数排序动态图解

Java实现计数排序代码

public static int[] countingSort(int[] arr) { int minV = arr[0], maxV = arr[0]; for (int i = 1; i < arr.length; i++) { if (minV > arr[i]) { minV = arr[i]; } if (maxV < arr[i]) { maxV = arr[i]; } } int gap = maxV - minV + 1; int[] countArr = new int[gap]; for (int i = 0; i < arr.length; i++) { countArr[arr[i] - minV] += 1; } for (int i = 1; i < gap; i++) { countArr[i] += countArr[i - 1]; } int[] result = new int[arr.length]; for (int i = 0; i < arr.length; i++) { /** * countArr[arr[i] - minV] - 1 当前arr[i]可以放的最右的位置,每放一次往前移一位 */ result[countArr[arr[i] - minV] - 1] = arr[i]; countArr[arr[i] - minV] -= 1; } return result; }