排序算法 - 计数排序

基本思想

计数排序是一种非基于比较的排序算法，其空间复杂度和时间复杂度均为O(n+k)，其中k是整数的范围。基于比较的排序算法时间复杂度最小是O(nlogn)的。该算法于1954年由 Harold H. Seward 提出。

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

算法步骤

1. 花O(n)的时间扫描一下整个序列 A，获取最小值 min 和最大值 max。

2. 开辟一块新的空间创建新的数组 B，长度为 ( max - min + 1)。

3. 数组 B 中 index 的元素记录的值是 A 中某元素出现的次数。

4. 最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数。

算法演示

算法演示说明

1. 首先，扫描一下整个序列。

2. 获得最小值为 2 ，最大值为 7。

3. 新建数组包含 2~7 的元素。

4. 再次扫描序列，将序列的值放置在新建数组中。

5. 扫描数字 5，数组中 index 为 3 的值为 5，次数为 1。

6. 扫描数字 3，数组中 index 为 1 的值为 3，次数为 1。

7. 扫描数字 4，数组中 index 为 2 的值为 4，次数为 1。

8. 扫描数字 7，数组中 index 为 5 的值为 7，次数为 1。

9. 扫描数字 2，数组中 index 为 0 的值为 2，次数为 1。

10. 扫描数字 4，数组中 index 为 2 的值为 4，次数为 2。

11. 扫描数字 3，数组中 index 为 1 的值为 3，次数为 2。

12. 按照这种节奏，扫描结束后，新建数组中存放了整个序列以及每个数字出现的次数。

13. 最后输出目标整数序列。

14. 输出数字 2，同时数组中 index 为 0 的值为 2 的元素次数变为 0。

15. 输出数字 3，同时数组中 index 为 1 的值为 3 的元素次数变为 1。

16. 同样的操作，整个序列就完全输出了。

代码

package main.java.com.study.sortingAalgorithm;

import main.java.com.study.utils.CommonUtils;

import java.util.Arrays;

/**
 * @author: whb
 * @description: 计数排序
 */
public class CountingSort {

    public static int[] countingSort(int[] unsorted) {
        //开始声明桶,找到数组的最小值和最大值
        int minNum = unsorted[0];
        int maxNum = unsorted[0];
        for (int i = 0; i < unsorted.length; i++) {
            if (unsorted[i] < minNum) {
                minNum = unsorted[i];
            }
            if (unsorted[i] > maxNum) {
                maxNum = unsorted[i];
            }
        }
        System.out.println("最小数字为:" + minNum);
        System.out.println("最大数字位:" + maxNum);
        //找到最大最小值的之后,就开始声明有序桶,桶的初始位代表的值为minNum最大值为maxNum
        //数组的长度为(maxNum-minNum+1)
        int[] bucket = new int[(maxNum - minNum + 1)];
        //声明了有序桶之后,开始对数字进行放桶操作
        for (int j = 0; j < unsorted.length; j++) {
            //因为是找到了待排序数组的最小值minNum,所以,与数组数组比较的值应为(j+minNum)
            //如果遍历的值大小与数组代表的数字大小相等,则放入
            //j次循环得到的数字是tempArray[j],则存储到下标为tempArray[j]+minNum的桶中
            bucket[unsorted[j] - minNum] = bucket[unsorted[j] - minNum] + 1;
        }
        //将得到的桶排序结果进行输出,输出的是桶排序的数组的下标
        //可以声明新数组对该序列进行存储
        int[] sorted = new int[unsorted.length];
        int count = 0;
        for (int k = 0; k < bucket.length; k++) {
            if (bucket[k] != 0) {
                //桶里装的值可能不是1,所以,在不等于一的时候,对桶里面的数字进行遍历存储
                if (bucket[k] != 1) {
                    for (int z = 0; z < bucket[k]; z++) {
                        sorted[count] = k + minNum;
                        count++;
                    }
                } else {
                    sorted[count] = k + minNum;
                    count++;
                }
            }
        }
        return sorted;
    }

    public static void main(String[] args) {
        //产生随机待排序列
        int[] unsorted = new int[(int) (Math.random() * 11) + 5];
        for (int i = 0; i < unsorted.length; i++) {
            unsorted[i] = (int) (Math.random() * 100);
        }
        System.out.println("**************计数排序******************");
        System.out.println("排序前：");
        CommonUtils.display(unsorted);
        System.out.println("排序后：");
        int[] sorted = countingSort(unsorted);
        CommonUtils.display(sorted);
    }
}

测试结果