计数排序的优点有哪些

这篇文章主要介绍“计数排序的优点有哪些”，在日常操作中，相信很多人在计数排序的优点有哪些问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”计数排序的优点有哪些”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

计数排序

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时， 它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序 （基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）

算法思想

计数排序对输入的数据有附加的限制条件： 1、输入的线性表的元素属于有限偏序集S； 2、设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。 在这两个条件下，计数排序的复杂性为O(n)。 计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。 一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。 当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改

算法思想

计数排序是一种稳定的排序算法,它能在线性时间 (O(n+k)) 内对包含n个元素的数组进行排序,其中数组元素均大于等于 0 且小于等于 k。

对输入数组 A的各个元素A[x]进行排序时,我们先将A[x]的元素个数记录在计数数组C中, 然后根据C中的数值计算在输出数组B中的位置。 考虑到存在多个相等元素的情况,再维护了B中的数据同时，如果A中存在相同的数据需要在B中相应减去一。

代码实现

public static int[] countSort(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int[] res = new int[arr.length];
        //O(n)
        for (int j : arr) {
            min = Math.min(j, min);
            max = Math.max(j, max);
        }
        int[] pos = new int[max + 1];
        //O(k)
        for (int i = 0; i < arr.length; i++) {
            //因为此处计数是从 1 开始的。
            pos[arr[i]]++;
        }
        for (int i = 1; i < pos.length; i++) {
            pos[i] = pos[i] + pos[i - 1];
        }
        for (int i = 0; i < arr.length; i++) {
            //计数是从 1开始的，我们重新排res[]应该从0开始
            res[pos[arr[i]]-1] = arr[i];
            pos[arr[i]]--;
        }
        return res;
    }

总结

• 计数排序本质就是用数组存储一个映射关系把它的位置保存起来，然后再遍历原先的数组从位置数组中把它拿出来进行排序。

• 所排序的数组中必须为非负整数，因为数组的下标被限制了。

• 计数排序时间复杂度为O(n+k),n 为待排序的长度，k为数组的中元素最大值。

到此，关于“计数排序的优点有哪些”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！