前面说的那些排序算法,都是要通过比较来实现的。排序还能不通过比较来实现?是的,计数排序就是这么神奇。 一、排序思想创建一个计数数组,利用数组下标来表示该元素,用数组下标对应的值来表示元素出现的次数。然后遍历计数数组即可。比如下标为5,元素值为2,表示5出现两次,连续写两次5即可。 1. 案例: 假如待排序列arr 如下: 5 7 4 8 3 5
最大元素是8,所以创建一个最大下标为8的数组: int[] count = new int[9];
遍历待排序列,第一个是5 ,所以count[5]++ ,第二个是7 ,所以count[7]++ ……
最终count数组就是: 0 0 0 1 1 2 0 1 1 // 元素值 0 1 2 3 4 5 6 7 8 // 下标
最后根据count数组,可以知道,3 出现一次,4 出现一次,5 出现两次……就可以知道排序后应该是这样的: 3 4 5 5 7 8
这样看似很完美,但是会存在两个问题。 2. 问题一: 上面的5 出现了两次,最后排完序的的数组中下标为2的那个5 ,还是原序列中下标为0的那个5 吗?也就是说,当值相同的情况下,无法保证排序后相同元素出现的顺序和排序前一致,这也就是我们说的不稳定排序。如何优化呢? 我们给之前的数组中两个5 做上标记,便于区分: 小红 小白 5 7 4 8 3 5
- 然后和之前一样,统计每个元素出现的次数,得到count数组:
0 0 0 1 1 2 0 1 1 // 元素值 0 1 2 3 4 5 6 7 8 // 下标
- 接下来,对count数组进行变形,让后一个元素加上前一个元素,即:
count[i] = count[i] + count[i-1];
这样一来,count数组就变成了: 0 0 0 1 2 4 4 5 6 // 元素值 0 1 2 3 4 5 6 7 8 // 下标
- 然后,创建一个新数组
resultArr ,长度和原数组arr 一样。从后往前遍历原数组arr ,第一个是5 ,标记是小白,count[5] 的值是4 ,表示小白排第四位,所以resultArr[4-1] = 5 ,同时count[5]-- ,即把4 变成3 ,下一个5 就表示排第三位,小红就排第三,和原数组的顺序一致。这样一来,就将计数排序变成稳定的了。
3. 问题二: 假如现有待排序列arr 如下: 999 998 1000 995
按照之前的说法,count 数组的最大下标是arr 数组最大值,即如果要排这四个数,需要创建长度为1001的数组。而且,下标0到994的这些空间都用不到,白白浪费了。所以,count 数组的长度应该是max(arr) - min(arr) + 1 ,即用最大值减去最小值再加1即可。此案例中,count 的长度就是1000 - 995 + 1 = 6 ,那么每个元素应该放在哪个下标上呢?每个元素都减去最小元素,得出来的值就对应count 的下标。比如999 - 995 = 4 ,那么999 就应该对应count[4] 。 4. 计数排序的缺点:从上面的分析可以知道,计数排序适合分布比较集中的数据,即最大值和最小值相差不多,如果相差特别多,就会很耗费空间。 二、代码实现public static void countSort(int[] arr) { if (arr == null || arr.length == 1) { return; } // 1. 找到数组中最大的数和最小的数 int max = arr[0]; int min = arr[0]; for (int i=1; i<arr.length; i++) { max = arr[i] > max ? arr[i] : max; min = arr[i] < min ? arr[i] : min; } // 2. 定义count数组 int[] count = new int[max - min + 1]; // 3. 遍历原数组,进行计数 for (int i=0; i<arr.length; i++) { count[arr[i] - min]++; } // 4. 对count数组进行变形,让计数排序变成稳定的 for (int i=1; i<count.length; i++) { count[i] += count[i-1]; } // 5. 创建接收结果的数组 int[] result = new int[arr.length]; // 6. 倒序遍历原数组,并且将结果存到result数组中 for (int i=arr.length-1; i>=0; i--) { result[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min] --; } // 7. 把result数组拷贝回原数组即可 System.arraycopy(result, 0, arr, 0, arr.length); }
|