排序3：计数排序、桶排序、基数排序

我们把时间复杂度为O(n)的排序算法称为线性排序。之所以能做到线性的时间复杂度，主要原因是，这样的算法是并非基于比较的排序算法，都不涉及元素之间的比较操作。但是如此高效是有代价的，线性排序的适用场景十分有限，条件苛刻。

桶排序

桶排序的思路是，遍历集合将不同范围的数据分割到不同的桶之中，然后对每个桶之中的数据进行排序，最后将每个桶合并就是已经排好序的数据。

比如我们有 [1,9,6,4,5,6,6,7,8,8,9,9] 将数据小于1-4划分为一个桶，5-8划分为一个桶，9划分为一个桶

在遍历之后，每个桶就有如下数据 [1，4] ，[6,5,6,6,7,8,8] , [9,9,9]
每个桶进行排序之后：[1,4] ，[5,6,6,6,7,8,8] , [9,9,9]
最后合并所有桶：[1,4,5,6,6,6,7,8,8,9,9,9]

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。比如在磁盘中有100G数据需要排序，我们不可能直接将所有数据都放入内存中。
那么我们可以这样做，分批扫描，每批100mb，记录数据范围，最大值最小值。
然后划分桶，再次分批读取，将数据放到不同的桶文件中。
再然后对每个桶文件的数据进行排序后返回到原来的桶文件之中。
最后合并桶文件，就可以得到排序好的100G数据。

实现使用到了排序2：归并排序、快速排序、希尔排序的归并排序

package cn.lishiyuan.algorithm.sort;  
  
import java.util.ArrayList;  
import java.util.List;  
import java.util.function.Function;  
  
  
/**  
 * 桶排序  
 * <br>  
 * 桶排序的思路是将数据划分到有序的不同的桶只中，每个桶单独进行排序，最后依次读取桶之中的数据就是有序的  
 */  
public class BucketSort {  
  
    /**  
     *     * @param data  
     * @param map 映射到bucket的index  
     * @return  
     * @param <T>  
     */  
    public <T extends Comparable<T>> List<T> sort(List<T> data,Function<T,Integer> map) {  
        List<List<T>> buckets = new ArrayList<>();  
        LeeSort sort = new MergeSort();  
  
        // 对每个函数映射到桶  
        for (T datum : data) {  
            Integer bucketIndex = map.apply(datum);  
            while (buckets.size() <= bucketIndex) {  
                buckets.add(new ArrayList<>());  
            }  
            List<T> nowList = buckets.get(bucketIndex);  
            if (nowList == null) {  
                nowList = new ArrayList<>();  
                buckets.set(bucketIndex,nowList);  
            }  
            nowList.add(datum);  
        }  
  
        // 对每个桶进行排序  
        for (List<T> bucket : buckets) {  
            // 排序  
            sort.sort(bucket);  
        }  
  
        // 合并所有桶  
        List<T> list = buckets.stream().flatMap(List::stream).toList();  
  
        return list;  
    }  
}

大多数适合我们应该定制桶排序，这里我的实现上只是一个玩具。

一方面为了使用到泛型，我这里使用到了一个映射函数将元素映射到特定的bucket的index。
另一方面由于桶数量的不确定，使用了while (buckets.size() <= bucketIndex) 创建桶，可能会频繁创建。

空间复杂度
桶排序需要构建额外的桶，其空间复杂度是O(n)。

稳定性
稳定性取决于桶内排序算法的稳定性。这里我的排序是稳定的，所以我的桶排序也是稳定的。

时间复杂度

最好时间复杂度为 O(n) ：
当数据均匀分布在各个桶中时，每个桶内的元素数量接近常数（如 k=n/m，其中 m 为桶的数量），此时桶内排序的时间复杂度可视为 O(1)。因此，总体时间复杂度为 O(n)，包括以下步骤：

数据分配到桶：O(n)
每个桶内排序：O(m⋅klogk)≈O(n)（若 k 为常数）
合并所有桶：O(n)

最坏时间复杂度，时间复杂度退化为 O(nlogn) 或 O(n2)：
若所有数据集中到一个桶中，桶排序退化为普通排序算法（如归并排序或快速排序），此时时间复杂度由桶内排序决定：

若使用归并排序：O(nlogn)
若使用快速排序：最坏 O(n2)

计数排序

计数排序是更加特殊的桶排序。它要求数据是有限的几个已经知晓的几个枚举数据组成，比如人的年龄，周1到周日这样的。
它的思路是，遍历数据，将数据映射到不同枚举后计数，然后对数据进行向前加处理得出当前枚举之前包括当前枚举在内有几个数，再次遍历数据，将数据放入到合适的位置，并减小计数。

比如，一个工作单位有10人，这些人的年龄在25到35之间，那么我们构建[0,0,0,0,0,0,0,0,0,0] 用以存储25到35岁之间的人的数量

首先第一遍遍历得到计数如下 [1,2,3,1,0,2,0,0,0,1]
然后向前加处理，得到当前枚举之前和当前枚举有几个数 [1,3,6,7,7,9,9,9,9,10]
最后再次遍历，通过这个计数数组可以得到当前元素应该放到什么index，比如年纪是25，那么该元素的index是1-1为0，然后当前枚举的count减一，得到[0,3,6,7,7,9,9,9,9,10] ，年纪为26，该元素index是3-1=2，然后当前枚举的count减一，得到[0,2,6,7,7,9,9,9,9,10]

实现：

package cn.lishiyuan.algorithm.sort;  
  
import java.util.ArrayList;  
import java.util.Collections;  
import java.util.List;  
import java.util.function.Function;  
  
/**  
 * 计数排序  
 * <br>  
 * 计数排序是桶排序的优化，它对数据的要求要比桶排序还要更高。  
 * <br>  
 * 计数排序的思路是，对数据范围数据映射到线性表index，每个index里面的item都是小于等于该index值的数量。  
 * <br>  
 * 先扫描一边进行计数，再扫描一边进行排序也就是位置确定。  
 */  
public class CountingSort {  
  
    public <T extends Comparable<T>> List<T> sort(List<T> data,Function<T, Integer> map) {  
        List<Integer> buckets = new ArrayList<>();  
        // 第一遍扫描进行计数  
        for (T datum : data) {  
            Integer bucketIndex = map.apply(datum);  
  
            while (buckets.size() <= bucketIndex) {  
                buckets.add(0);  
            }  
            Integer count = buckets.get(bucketIndex);  
            if (count == null) {  
                count = 0;  
                buckets.set(bucketIndex,count);  
            }  
            count++;  
            buckets.set(bucketIndex,count);  
        }  
  
        // 对countData进行向后加  
        for (int i = 1; i < buckets.size(); i++) {  
            int before = i-1;  
            Integer now = buckets.get(i);  
            Integer beforeValue = buckets.get(before);  
            buckets.set(i,beforeValue + now);  
        }  
  
        // 直接插入null  
        List<T> result = new ArrayList<>(Collections.nCopies(data.size(), null));  
  
        // 第二遍扫描确认位置进行排序，从后向前，保证稳定  
        for (int i = data.size() - 1; i >= 0; i--){  
            T datum = data.get(i);  
            Integer bucketIndex = map.apply(datum);  
            Integer count = buckets.get(bucketIndex);  
  
            result.set(count - 1,datum);  
            count--;  
            buckets.set(bucketIndex,count);  
        }  
  
        return result;  
    }  
}

大多数适合我们应该定制排序，这里我的实现上只是一个玩具。

一方面为了使用到泛型，我这里使用到了一个映射函数将元素映射到特定的bucket的index。
另一方面由于我对调用方桶数量的不确定，使用了while (buckets.size() <= bucketIndex) 创建桶，可能会频繁创建。

空间复杂度
计数数值的长度取决于枚举数量，通常是O(1)。

稳定性
是否稳定取决于遍历顺序，在第三遍扫描时需逆序遍历原数组 ，并将元素放置在结果数组的对应位置（如 count - 1），此时是稳定的。若正序遍历，则可能导致相同元素的顺序颠倒，破坏稳定性。我这里是稳定的。

时间复杂度

计数排序的时间复杂度为 O(n + k) ，其中 n 是输入数据的数量，k 是数据的取值范围（即最大值与最小值的差）

第一遍扫描 ：统计每个元素的出现次数，时间复杂度为 O(n) 。
第二遍扫描 ：对计数数组进行前缀和计算，时间复杂度为 O(k) 。
第三遍扫描 ：将元素按计数位置放入结果数组，时间复杂度为 O(n) 。
总时间复杂度为三者之和，即 O(n + k) 。当 k 接近 n 时，时间复杂度接近线性最优解。

基数排序

基数排序通过分治策略将排序问题转化为多轮稳定排序。适合处理非负整数 或可分解为多维键的数据（如字符串、日期等），且数据位数 d 较小的情况。思想是从低到高，且高位的顺序优先级高于低位的情况下，每一维数据都进行一轮排序，并保证每一轮排序的稳定性，依次排序后便可得到有序合集。

比如，我们需要对日期数据进行排序[2021-5-15,2020-5-15,2012-6-1,2021-4-11] 我们分别对日期、月份、年份三个维度依次排序：

首先第一轮对日期进行排序，得到结果：[2012-6-1,2021-4-11,2021-5-15,2020-5-15]
首先第二轮对月份进行排序，得到结果：[2021-4-11,2021-5-15,2020-5-15,2012-6-1]
最后第三轮对年份进行排序，得到结果：[2012-6-1,2020-5-15,2021-4-11,2021-5-15,]

实现使用到了[[排序2：归并排序、快速排序、希尔排序]] 的归并排序

package cn.lishiyuan.algorithm.sort;  
  
  
import java.util.ArrayList;  
import java.util.List;  
import java.util.function.Function;  
  
/**  
 * 基数排序  
 * <br>  
 * 基数排序的思路是，数据的高位大小可以决定大小的情况下，对每一位数据从低到高进行稳定排序。  
 */  
public class RadixSort{  
  
    private static class Item<T>  implements Comparable<Item<T>>{  
        T value;  
        int index;  
        Integer[] radix;  
  
        @Override  
        public int compareTo(Item<T> o) {  
            if(index != o.index){  
                throw new IllegalStateException("位置不一致");  
            }  
            return radix[index].compareTo(o.radix[index]);  
        }  
    }  
  
  
    public <T extends Comparable<T>> List<T> sort(List<T> data,Function<T, Integer[]> slip) {  
        if (data == null || data.size() <= 1){  
            return data;  
        }  
  
        // 进行分割  
        List<Item<T>> result = new ArrayList<>(data.size());  
        for (T d : data) {  
            Item<T> item = new Item<>();  
            Integer[] indexArr = slip.apply(d);  
            item.index = indexArr.length - 1;  
            item.radix = indexArr;  
            item.value = d;  
            result.add(item);  
        }  
  
        // 按位进行排序  
        int n = result.get(0).index;  
  
        LeeSort sort = new MergeSort();  
  
        for (int i = 0; i <= n; i++){  
            sort.sort(result);  
            for (Item<T> item : result) {  
                item.index--;  
            }  
        }  
  
        return result.stream().map(d -> d.value).toList();  
    }  
  
}

基数排序通常需要你定制实现，基数排序通常和计数排序搭配使用，通常每一轮维度的排序所排序的都是有限枚举。
我这里的实现是一个玩具：为了使用通用性，使用到泛型，使用slip函数来划分维度；使用item额外结构存储维度，每个item自己调整当前index。

稳定性
基数排序是一种稳定的排序算法 。因为基数排序要求每一轮的排序都是稳定的。

空间复杂度
我这里使用内部数据结构Item来存储临时数据，空间复杂度是O(n)

时间复杂度
时间复杂度是O(d × nlogn)，d是维度数量，也就是循环排序轮数。O(nlogn)是MergeSort的时间复杂度，如果你使用计数排序可以变成O(n)，也就是可以将基数排序优化为O(d × n) = O(d × n) ，d如果小的话。

注意

for (Item<T> item : result) {  
    item.index--;  
}

大多是时候你是不需要这步调整索引的操作的，稍微更改使用 i 作为索引就行。我这边由于不想更改MergeSort算法实现才使用如此丑陋的操作，

排序3：计数排序、桶排序、基数排序

桶排序

计数排序

基数排序

评论已关闭

最新文章

分类