计数排序and基数排序

阳光穿透心脏的1/2处 2021-10-01 03:08 360阅读 0赞

1 计数排序，稳定    复杂度o(k + n)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

public static int[] countingSort(int[] nums) {
            int n = nums.length;
            int k = 0;
            for (int i = 0; i < n; i++) {
                k = Math.max(k, nums[i]);
            }
            int[] count = new int[k + 1];
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                count[nums[i]]++;
            }
            for (int i = 1; i <= k; i++) {
                count[i] += count[i - 1];
            }
            for (int i = n - 1; i >= 0; i--) {
                res[--count[nums[i]]] = nums[i];
            }
            return res;
        }

2 基数排序 需要稳定排序  有n个d位数，每一位有k个取值，复杂度为d（n + k）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

public static int[] radixSort(int[] nums) {
            int max = 0;
            int n = nums.length;
            for (int i = 0; i < nums.length; i++) {
                max = Math.max(max, nums[i]);
            }
            int exp = 1;
            int[] cur = new int[n];
            while (max / exp > 0) {
                int[] count = new int[10];            
                for (int i = 0; i < n; i++) {
                    count[(nums[i] / exp) % 10]++;
                }
                for (int i = 1; i < 10; i++) {
                    count[i] += count[i - 1];
                }
                for (int i = n - 1; i >= 0; i--) {
                    cur[--count[(nums[i] / exp) % 10]] = nums[i];
                }
                for (int i = 0; i < n; i++) {
                    nums[i] = cur[i];
                }
                exp *= 10;
            }
            return nums;
        }

3 桶排序

![1074350-20170917102254797-1649791140.png][]

转载于:https://www.cnblogs.com/whesuanfa/p/7534892.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210724/557a5f11e98e4b1cb128b8fc94905b40.png
[1074350-20170917102254797-1649791140.png]: /images/20210724/c57d207317fe4f709f99394e09ca8226.png