首页 > 代码库 > 排序算法(二)
排序算法(二)
一、桶排序
（1）算法描述：假设数组元素值的范围是0~n-1。我们需要N个标记为0,1,2,...,n的桶。如果元素的值是i,那么就将该元素放入桶i中。然后将0~n-1号桶中的元素放回原数组，即可得到从小到大的序列。
public static <E>void bucketSort(E[] list){//list为数组 E[] buckets=(E[])new java.util.ArrayList[N]; //将元素放入桶 for(int i=0;i<list.length;i++){ int key=list[i]; if(buckets[key]=null){ buckets[key]=new java.util.ArrayList(); } buckets[key].add(list[i]); } //将桶中的元素放回数组 int k=0; for(int i=0;i<buckets.length;i++){ if(buckets[i]!=null){ for(int j=0;j<buckets[i].size();j++){ list[k++]=buckets[i].get(j); } } }}
（2）算法实现
package algorithm;import java.util.ArrayList;public class BucketsSort{ public static <E> void bucketSort(E[] list,int max){//list为数组 E[] buckets=(E[]) new java.util.ArrayList[max+1];//声明 for(int i=0;i<list.length;i++){ int key=(Integer) list[i]; if(buckets[key]==null){ buckets[key]=(E) new java.util.ArrayList();//初始化 } ((ArrayList) buckets[key]).add(list[i]); } int k=0; for(int i=0;i<buckets.length;i++){ if(buckets[i]!=null){ for(int j=0;j<((ArrayList) buckets[i]).size();j++){ list[k++]=(E) ((ArrayList) buckets[i]).get(j); } } }} public static void main(String[] args){ Integer[] list={8,3,2,4,7,9}; int max=9; BucketsSort.<Integer>bucketSort(list,max); for(Integer u:list) System.out.print(u+","); }}
（3）总结:桶排序的时间为O(n+N),n表示线性表的大小。桶排序不是基于比较排序的，因此好过比较排序算法的下限O(nlogn)。桶排序是稳定的。
二、基数排序
1.最低位优先(Least Significant Digit first)法，简称LSD法
（1）算法描述：
第一步：建立10个桶，对应着编号0-9.位置关键字k=1,表示从最低位开始。
第二步：遍历需要排序的序列。数把序列中的数分配到第k位数对应的桶里。
第三步：遍历桶，从0-9把桶中的数据依次放回到原数组中！
第四步：如果k的等于序列中最大数的最高位数，则排序结束。否则k=k+1,跳转到第二步。
2.最高位优先(Most Significant Digit first)法，简称MSD法
（1）算法描述：
从最高位开始，实际上已经能保证大体上是从小到大的递增序列了！但是位数相同时，就不一定了！实际上就是：桶外有序，而桶类无序！这时候，就是递归的思想起作用了！既然桶外有序，我们就不管桶外了，关注处理桶内的数据。从次高位开始，再建立10个桶，然后把数据放到桶里，按第一次的方式来处理，直到处理到最低位！
3.算法实现
import java.util.ArrayList;public class RadixSort { public static void main(String[] args){ Integer[] a={122,55,422,333,655,599,799}; Integer[] b={122,55,422,333,655,599,799}; RadixSort.LSD(a,3); System.out.println(); RadixSort.MSD(b,3); for(Integer u:b) System.out.print(u+","); } //最低位优先(Least Significant Digit first)法 @SuppressWarnings("unchecked") public static void LSD(Integer[] a,int d){ ArrayList[] buckets=new java.util.ArrayList[10]; //数据有d位数 for(int x=0;x<d;x++){ //将数据放入桶 for(int i=0;i<a.length;i++){ int[] r=getr( a[i],d); if(buckets[r[x]]==null) buckets[r[x]]=new java.util.ArrayList<Integer>(); buckets[r[x]].add(a[i]); } //将桶中数据放数组 int k=0; for(int j=0;j<10;j++){ if(buckets[j]!=null){ for(int y=0;y<buckets[j].size();y++){ a[k++]=(Integer) buckets[j].get(y); } buckets[j].clear();//清空桶，否则元素会重复聚集，导致数组a下标异常 } } } //打印数据 for(Integer u:a) System.out.print(u+","); } //最高位优先(Most Significant Digit first)法 public static void MSD(Integer[] a,int d){ MSD(a,0,a.length,d); } public static void MSD(Integer[] a,int n1,int n2,int d){//对a[n1,n1+n2)部分元素排序,n1为子数组起始下标，n2为元素个数 if(d>0){ ArrayList[] buckets=new java.util.ArrayList[10]; //将数组数据放入桶 for(int i=n1;i<n1+n2;i++){ int[] r=getr( a[i],d); if(buckets[r[d-1]]==null) buckets[r[d-1]]=new java.util.ArrayList<Integer>(); buckets[r[d-1]].add(a[i]); } //将桶中数据放回数组 for(int j=0;j<10;j++){ int num=0;//记录每个桶中元素个数 if(buckets[j]!=null){ for(int y=0;y<buckets[j].size();y++){ a[n1++]=(Integer)buckets[j].get(y); num++; } buckets[j].clear();//清空桶，否则元素会重复聚集，导致数组a下标异常,对于MSD方法，此步骤可省略，因为每次递归都会新建buckets数组没有重用buckets数组 } MSD(a,n1-num,num,d-1);//对每个桶中的元素递归排序 } } } //返回由数据各位组成的数组 public static int[] getr(int n,int d){ int[] r=new int[d]; for(int i=0;i<d;i++){ r[i]=n%10; n=n/10; } return r; }}
三、外部排序
要对存储在外部文件中的数据进行排序，首先要将数据送入内存，然后排序。但当文件过大时，所有数据不能同时送入内存。解决方法：
（1）重复将文件读入数组，并调用内部排序算法对数组排序，然后将数组输出到一个临时文件；
（2）将每对有序分段归并到一个大一些的有序分段中，将新分段存储到新的临时文件。继续同样的过程直到得到一个有序分段。（归并排序）
排序复杂度：O(nlogn)
排序算法(二)