Go语言视频零基础入门到精通

javalearner

基数排序的方法如下:
1、根据数据项个位上的值，把所有的数据项分为10组；

2、然后对这10组数据重新排列：把所有以0结尾的数据排在最前面，然后是结尾是1的数据项，照此顺序直到以9结尾的数据，这个步骤称为第一趟子排序。 3、在第二趟子排序中，再次把所有的数据项分为10组，但是这一次是根据数据项十位上的值来分组的。这次分组不能改变先前的排序顺序。也就是说，第二趟排序之后，从每一组数据项的内部来看，数据项的顺序保持不变； 4、然后再把10组数据项重新合并，排在最前面的是十位上为0的数据项，然后是10位为1的数据项，如此排序直到十位上为9的数据项。 5、对剩余位重复这个过程，如果某些数据项的位数少于其他数据项，那么认为它们的高位为0。
      
      
        
         
        

        
        
      
     
    下面是一个例子：
421 240 035 532 305 430 124(原数据）
（240 430） （421） （532） （124） （035 305）（第一趟排序之后）
    (305) (421 124) (430 532 035) (240) (第二趟排序之后）
    (035) (124) (240) (305) (421 430) (532) (第三趟排序之后）
    请看基数排序的java程序：
   

1. class Node {
   
2.     private String data;   // 节点数据
   
3.     private Node next;  // 下一个节点位置
   
4.     public void setData(String data) {  
   
5.      this.data = data;
   
6.     }
   
7.     public void setNext(Node next) {
   
8.         this.next = next;
   
9.     }
   

复制代码

   
  
  

1. 
   
2.     public String getData() {  
   
3.        return data;
   
4.     }
   
5.     public Node getNext() {
   
6.         return next;
   
7.     }
   
8. }
   
9.                   

复制代码

class Radixsort{
private Node list[] = new Node[10]; //数据分成10组
private Node masterlist,previous;
private int numdigits;   public void Radixsort(){ //初始化
masterlist = null;
previous = null;
numdigits = 0;   for(int i = 0;i < list.length;i++)
    list = new Node();
}   public void add(String data){ //加入数据方法   Node newNode = new Node(); //增加一个位置
if(data.length() > numdigits) //找出最大位??
numdigits = data.length();
newNode.setData(data);
if(masterlist == null)
masterlist = newNode; //加入第一笔
else
previous.setNext(newNode);
previous = newNode;
}
   public String list() { //输出数据方法   Node tmpNode;
String out = "<table border="1"><tr>";
tmpNode = masterlist;
out = out+"<td>数列?热?</td>";
while(tmpNode != null) {
out=out+"<td>" + tmpNode.getData() + "</td>";
tmpNode = tmpNode.getNext();
}
out = out+"</tr></table>";
return out;
}
   public String Radix() { //Radix排序方法
String s=list();
String out = "";
for(int i= 1;i <= numdigits;i++){
distribute(i); //分组
out = out+"<table border="1"><tr><td>第"+i+"次分组
      </td></tr><tr><td>"+coalesce()+"</td></tr><tr><td>"+list()+"</td></tr></table><hr width="80%">";
}
return s+out;
}
   private void distribute(int i) { //分组分法,i=1,按个位分;i=2,按十位分...  Node tmpNode = masterlist;
for(int j = 0;j < 10;j++){ //将数据分为十组
list[j] = new Node();
}   while(tmpNode != null){
int j;
String Data = tmpNode.getData();
if((Data.length() - i) < 0) //找出所要填入的位数
j = 0; //当位数不足时
else
j = Integer.parseInt(Data.substring( ( Data.length()-i ),( Data.length()-i) + 1 ) ); //计算位数   Node listtmpNode = list[j]; //找寻list[j]的尾端
while(listtmpNode.getNext()!=null)
listtmpNode = listtmpNode.getNext();   listtmpNode.setNext(tmpNode); //将tmpNode连到list[j]的尾端   tmpNode = tmpNode.getNext();   listtmpNode=listtmpNode.getNext(); //切断尾端的数据   listtmpNode.setNext(null);   }
}
   private String coalesce() { //组合方法
   String out = "<table border="0" width="100%">";
Node tmpNode = new Node(),
previous = new Node(),
listtmpNode = new Node();
masterlist = tmpNode;
for(int j = 0;j < 10;j++){
listtmpNode = list[j].getNext(); //输出数列分组的情况
out = out+"<tr><td>组"+j+"</td><td>";
while(listtmpNode != null){ //输出第j组中的数据
out = out+"  "+listtmpNode.getData();
listtmpNode = listtmpNode.getNext();
}   out = out+"</td></tr>";   if(list[j].getNext() != null){ //将十组数据重新合并
if(masterlist.getData() == null){
   masterlist = list[j].getNext();
}
else{
tmpNode = masterlist;
while(tmpNode.getNext() != null)
tmpNode = tmpNode.getNext();
tmpNode.setNext( list[j].getNext() );
}
}   }
out = out+"</table>";
return out;
}
   public static void main(String args[]){
   Radixsort r=new Radixsort();
    r.add("421");r.add("240");r.add("35");
    r.add("532");r.add("305");r.add("430");
    r.add("124");    String sortresult=r.Radix();
   System.out.println(sortresult);
}
}  请观看演示结果  

  
  
   
   

     
   

     
   
  

  

  










源码下载：http://file.javaxxz.com/2014/10/29/235931296.zip