十大排序算法(三)

目录

8计数排序

9桶排序

10基数排序

10.1总结

算法步骤：

1. 遍历无序序列得到最大值和最小值，开辟一个长度为最大值和最小值的差值加1的数组；
2. 让每一个整数按照值对号入座，对应数组下标的元素加1；
3. 最后遍历数组，输出数组元素的下标值，元素的值是几就输出多少次。

```Java
public static int[] sortCount(int[]a){
        int max=a[0];
        int min=a[0];
        //求数组最大值与最小值O(n)
        for (int i=1;imax){
                max=a[i];
            }
            if(a[i] 

 基数排序只能对正整数序列进行排序，时间复杂度O(n+k)，空间复杂度O(k)，无序序列中数组值越大，时间复杂度越高，算法一般用在有条件限制的排序中，比如对年龄排序。
 
9桶排序 
桶排序是计数排序的升级版，它利用了函数的映射关系，高效与否的关键在于这个映射函数的确定。为了使桶排序高效，要做到以下两点：1. 在额外空间充足的条件下，尽量增大桶的数量；
 2. 使用映射函数能够将输入的n个数据均匀分派到k个桶中。
 当输入的数据被分配到同一个桶中，速度最慢，均匀分配到每一个桶中速度最快。桶排序是通过分配和收集完成排序。
 
```Java
    public static int[] sortBucket(int[] a){
        return bucket(a, 5);//5是桶的大小
    }

    private static int[] bucket(int[] a, int bucketSize) {
        if (a.length == 0) {
            return a;
        }
        //求数组最大值与最小值O(n)
        int max=a[0];
        int min=a[0];
        for (int i=1;imax){
                max=a[i];
            }
            if(a[i] 

 10基数排序 
基数排序是将整数按位数切割成不同的数字，然后按每个位数分别比较。分别进行个位排序，十位排序，百位排序，千位排序等等，每次排序桶的数量都是0-9。
 代码写起来比较繁琐，给大家一个专门将基数排序的链接https://blog.csdn.net/xiaoxi_hahaha/article/details/113186384
 获取十位数个位数及百位数的方法
 
```Java
int n=1234;
        int[] num=new int[4];
        num[0]=n%10;//个位
        num[1]=(n/10)%10;//十位
        num[2]=(n/100)%10;//百位
        num[3]=(n/1000)%10;//千位
```
 
10.1总结 
1. 计数排序：每个桶只存储一个值；
 2. 桶排序：每个桶存储符合映射的一组值；
 3. 基数排序：每个桶的值为0-9，要经过多次桶排序；
 4. 归根到底，以上三种排序方法都是基于桶的排序。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5717992.html