美文网首页啊哈算法java实现
最简单的并且最快排序-桶排序

最简单的并且最快排序-桶排序

作者: Airycode | 来源:发表于2018-04-18 09:19 被阅读11次

在我们生活中排序是经常出现的,比如我们网上买东西的时候需要按照价格排序,创建的数据需要按照创建的时间排序等等,可以说排序是无处不在的。

举一个简单的栗子:比如一个分数数组为[5,3,5,2,8],满分是10分,接下来我们按照从大到小排序,排序后的结果是[8,5,5,3,2].

提示:首先我们借助一个一维数组就可以搞定。

思路:首先我们申请一个大小为11的数组int[]arr = new int[11],好了,现在我们已经有11个变量,编号一次是arr[0]-arr[10];你可以初始化为这十个变量值为0,在这里我们用的是java,java初始化的时候默认是0.初始化为0的含义是表示这些分数还没有人得过。比如arr[0]=0表示没有人得过0分;arr[1]=0表示没有人得过1分;arr[10]=0表示没有得过10分。

下面开始处理每一个人的分数,第一个是5分,我们就将对应的arr[5]的值在原来的基础上增加1.即arr[5]=1。表示5分数出现过一次。同理所有的数据一次这样处理。
java代码实现如下:


public class BubleSort {
    public static void main(String[] args) {
        int [] arr = {5,3,5,2,8};
        int max = 10;
        sortASC(arr,max);
        sortDESC(arr,max);
    }
    //从小到大排序
    private static void sortASC(int[] arr,int max) {
        int [] help = new int[max+1];
        for (int i=0;i<arr.length;i++) {
            int num = arr[i];
            help[num]+=1;
        }
        //循环遍历help
        for (int i=0;i<help.length;i++) {
            int num = help[i];
            
            for (int t=1;t<=num;t++) {
                if (num !=0) {
                    System.out.print(i+" ");
                }
            }   
        }
        System.out.println();
        
    }
    //从小到大排序
        private static void sortDESC(int[] arr,int max) {
            int [] help = new int[max+1];
            for (int i=0;i<arr.length;i++) {
                int num = arr[i];
                help[num]+=1;
            }
            //循环遍历help
            for (int i = help.length-1;i>=0;i--) {
                int num = help[i];
                for (int t=1;t<=num;t++) {
                    if (num !=0) {
                        System.out.print(i+" ");
                    }
                }
            }
            System.out.println();
            
        }
    
}

这种排序的方法我们暂且叫做桶排序,其实真正的桶排序比这个要复杂,这个只是一个简单栗子而已,使用的范围也不大,因为这个排序太浪费空间了,如果我的max很大是不是要申请的内存空间很大。简单的桶排序时间复杂度O(m+n)

相关文章

  • 最简单的并且最快排序-桶排序

    在我们生活中排序是经常出现的,比如我们网上买东西的时候需要按照价格排序,创建的数据需要按照创建的时间排序等等,可以...

  • 读书心得--啊哈算法

    最快最简单的排序——桶排序,优点:时间复杂度低,缺点:耗费空间 交换相邻数据的排序——冒泡排序 优点:解决了桶排序...

  • 最快最简单的排序——桶排序

    在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按...

  • 最快最简单的排序——桶排序

    在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按...

  • 算法1 - 桶排序算法

    桶排序算法是一种最快最简单的排序方法。 算法说明 举例说明:例如当前有一个一维数组有几个数字例如(1-10)之间,...

  • 浅谈排序算法

    排序算法有很多种,今天先谈谈一些简单的排序算法。包括桶排序、冒泡排序和快速排序算法。后期总结各种排序算法。 桶排序...

  • 经典排序算法——桶排序

    补充说明三点 1,桶排序是稳定的2,桶排序是常见排序里最快的一种,比快排还要快…大多数情况下3,桶排序非常快,但是...

  • 算法基础 排序(一)

    桶排序冒泡排序快速排序 1.桶排序 所谓的桶排序就是列出所有的可能进行排序 小结:这里的桶排序只是简化版的.桶排序...

  • 常见的排序算法

    冒泡排序 快速排序 直接插入排序 希尔排序 简单选择排序 基数排序 归并排序 堆排序 计数排序 桶排序 参考资料:...

  • 八种基本排序算法的使用

    最经典最常用的排序算法有:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序。这些排序算...

网友评论

    本文标题:最简单的并且最快排序-桶排序

    本文链接:https://www.haomeiwen.com/subject/kbomkftx.html