当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

非基于比较的排序:桶排序

发表于: 2012-09-18   作者:128kj   来源:转载   浏览:
摘要:    我们最常用的快速排序和堆排序等算法需要对序列中的数据进行比较,因为被称为基于比较的排序。    而非基于比较的排序有计数排序,桶排序,和在此基础上的基数排序。要注意的是,非基于比较的排序算法的使用都是有条件限制的,例如元素的大小限制。 假设待排序数据是一个随机过程产生,该过程将元素一致地分布在某区间上。    
   我们最常用的快速排序和堆排序等算法需要对序列中的数据进行比较,因为被称为基于比较的排序。
   而非基于比较的排序有计数排序,桶排序,和在此基础上的基数排序。要注意的是,非基于比较的排序算法的使用都是有条件限制的,例如元素的大小限制。

假设待排序数据是一个随机过程产生,该过程将元素一致地分布在某区间上。

    桶排序的思想就是把区间划分成n个相同大小的子区间,或称桶,然后将输入数分布到各个桶中去。因为输入数均匀分布,所以一般不会有很多数落在一个桶中的情况。为得到结果,先对各个桶中的数进行排序,然后按次序把各桶中的元素列出来即可。

举个例子:一年的全国高考考生人数为500万,分数使用标准分,最低100,最高900,没有小数,你把这500万元素的数组排个序。一共可出现的分数可能有多少种呢?一共有900-100+1=801,创建801个“桶”,从头到尾遍历一次数组,对不同的分数给不同的“桶”加料.

   比如有个考生考了500分,那么就给500分的那个桶(下标为500-100)加1,完成后遍历一下这个桶数组,按照桶值,填充原数组,100分的有1000人,于是从0填到999,都填1000,101分的有1200人,于是从1000到2119,都填入101.于是经过这次遍历之后所有记录都是有序的了。
public static void bucketSort(int[] keys,int max){    
    int[] temp=new int[keys.length];//创建临时数组   
    int[] count=new int[max];//创建桶   
    //进桶,如果有重复的,那桶里的值为重复的次数   
    for(int i=0;i<keys.length;i++){   
        count[keys[i]]++;   
    }   
     // 计算“落入”各桶内的元素在有序序列中的位置

    for(int i=1;i<max;i++){   
        count[i]=count[i]+count[i-1];   
    }      
    //复制数组   
    System.arraycopy(keys, 0, temp, 0, keys.length);   
     // 根据count数组中的信息将待排序列的各元素放入相应位置

    for(int k=keys.length-1;k>=0;k--){   
        keys[--count[temp[k]]]=temp[k];   
    }   
}  

非基于比较的排序:桶排序

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
桶排序一般用于非数字元素排序,比如26个字母。做了一张图,应该好理解,因为数字是10进制,就准备1
桶排序一般用于非数字元素排序,比如26个字母。做了一张图,应该好理解,因为数字是10进制,就准备1
[url]http://www.ahhf45.com/info/Data_Structures_and_Algorithms/algorithm/commonalg/sort/intern
原文: http://hxraid.iteye.com/blog/647759 从《基于比较的排序结构总结 》中我们知道:全依赖“
【1】桶排序 桶排序(也称箱排序),据坊间演绎,其实现方式有很多。 在此我们仅仅阐述一下本文的实
概要 本章介绍排序算法中的桶排序。内容包括: 1. 桶排序介绍 2. 桶排序图文说明 3. 桶排序实现 3.1
从《基于比较的排序结构总结 》中我们知道:全依赖“比较”操作的排序算法时间复杂度的一个下界O(N*
1. 桶排序将数据区间划分为若干个k个相同大小的子区间,称为桶。将n个数字分别送到各个桶中,如果输
从《基于比较的排序结构总结 》中我们知道:全依赖“比较”操作的排序算法时间复杂度的一个下界O(N*
计数排序 计数排序是一种算法复杂度 O(n) 的排序方法,适合于小范围集合的排序。比如100万学生参加
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号