图解排序算法

摘要：十一假期于实验室无趣，逐研究起数据结构之排序。起初觉得就那么几种排序，两三天就搞定了，后来随着研究的深入，发觉里面有不少东西。本文介绍常用的排序算法，主要从以下几个方面：算法的介绍、算法思想、算法步骤、算法优缺点、算法实现、运行结果、算法优化等。最后对本文进行总结。本文为作者原创，程序经测试无误。部分资料引用论文和网络材料以及博客，后续参见参考文献。（ 本文原创，转载注明出处 ）

package com.multiplesort.bnc; import java.util.Arrays; /**  * 各种排序算法分析比较之冒泡排序:【交换排序】  * @author bnc  * @see http://www.cnblogs.com/liuling/p/2013-7-24-01.html  */ public class BubbleSort {  /**   * 随机生成从0-n的随机数组   * @param n  数组的成都   * @return resultArr   数组   * @author 白宁超   */  public static int[] randomArray(int arrayLength,int maxNum){   int[] array=new int[arrayLength];   for(int i=0;i<array.length;i++){    array[i]=(int)(Math.random()*maxNum);   }   return array;  }  /**   * 数据交换   * @param data  整数型数组   * @param i  第一层循环指针   * @param j  第二层循环指针   */  private static void swap(int[] data, int i, int j) {    int temp=data[i];   data[i]=data[j];   data[j]=temp;  }  /**   * 简单的冒泡排序:稳定   * @deprecated :冒泡排序是一种稳定的排序方法。      •若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)     •若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n^2)     •起泡排序平均时间复杂度为O(n^2)   * @param data 整数数组    */  public static void BubbleSort0(int[] array){   int i,j;   for(i=0;i<array.length;i++){    for(j=i+1;j<array.length;j++){     if(array[i]>array[j])      swap(array,i,j);//数据交换    }   }   System.out.println();   System.out.println("简单【冒泡排序】后的结果：");    for (i = 0; i < array.length; i++) {     System.out.print(array[i]+" ");    }  }  /**   * 改进后的冒泡排序:稳定   * @deprecated :冒泡排序是一种稳定的排序方法。      •若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)     •若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n^2)     •起泡排序平均时间复杂度为O(n^2)   * @param data 整数数组    */  public static void BubbleSort1(int[] array){   int i,j;   for(i=0;i<array.length;i++){    for(j=array.length-2;j>=i;j--){     if(array[j]>array[j+1]){     // System.out.println(array[j]+"<--->"+array[j+1]);//测试结果前面排序影响后面，相当于是从缓存有序的数组中获取      swap(array,j,j+1);//数据交换     }    }   }   System.out.println();   System.out.println("改进后【冒泡排序】的结果：");    for (i = 0; i < array.length; i++) {     System.out.print(array[i]+" ");    }  }  /**   * 当数组基本有序时，如何改进排序算法   * @param array   */  public static void BubbleSort2(int[] array){   int i,j;   Boolean flag=true;   for(i=0;i<array.length&&flag;i++){//如果flag为flag退出循环    flag=false;    for(j=array.length-2;j>=i;j--){     if(array[j]>array[j+1]){      swap(array,j,j+1);//数据交换      //System.out.println(array[j]+"<--->"+array[j+1]);      flag=true;//如果有数据交换，则flag为true     }    }   }   System.out.println();   System.out.println("基本有序数组【冒泡排序】的结果：");    for (i = 0; i < array.length; i++) {     System.out.print(array[i]+" ");    }  }  public static void main(String[] args) {   int[] array=randomArray(20, 100);//随机生成0--100的20个长度的数组   int[] array1={1,3,2,4,5,6};//基本有序数组      System.out.println("冒泡排序前:");   for(int i=0;i<array.length;i++){    System.out.print(array[i]+" ");   }   System.out.println();   System.out.println("使用内部排序的结果:");   for(int i=0;i<array.length;i++){    //使用内部排序的结果    Arrays.sort(array);//内部排序    System.out.print(array[i]+" ");   }   //BubbleSort0(array);   //BubbleSort1(array);   BubbleSort2(array1);  } } 

package com.multiplesort.bnc; /**  * 快速排序  * 基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,  *  此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。  * 分析:     快速排序是不稳定的排序。     快速排序的时间复杂度为O(nlogn)。      当n较大时使用快排比较好，当序列基本有序时用快排反而不好。  * @author bnc  *  */ public class QuickSort {  //随机生成数组  public static int[] randomArray(int arrayLength,int maxNum){   int[] array=new int[arrayLength];   for(int i=0;i<array.length;i++){    array[i]=(int)(Math.random()*maxNum);   }   return array;  }  //数据交换  public static void swap(int[] data,int i,int j){   int temp=data[i];   data[i]=data[j];   data[j]=temp;  }  //打印出数组  public static void printArray(int[] array){   for(int i=0;i<array.length;i++){    System.out.print(array[i]+" ");   }   System.out.println();  }  private static void quickSort(int[] array, int low, int high) {   if(array.length>0)   {    if(low<high){ //如果不加这个判断递归会无法退出导致堆栈溢出异常     int middle = getMiddle(array,low,high);     quickSort(array, 0, middle-1);     quickSort(array, middle+1, high);    }   }  }  private static int getMiddle(int[] array, int low, int high) {   //int m=low+(high-low)/2;//计算数组元素中间的下标   int temp = array[low];//基准元素   while(low<high){    //找到比基准元素小的元素位置    while(low<high && array[high]>=temp){     high--;    }    array[low] = array[high];     while(low<high && array[low]<=temp){     low++;    }    array[high] = array[low];   }   array[low] = temp;   return low;  }  //快排  public static void quickSort(int[] array){   System.out.println("快速排序前的结果");   printArray(array);   quickSort(array,0,array.length-1);   System.out.println("快速排序后的结果");   printArray(array);  }  public static void main(String[] args) {   quickSort(randomArray(20, 100));  } } 

package com.multiplesort.bnc; /**  * 选择排序：简单选择排序、堆排序。  * 思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。  * 关键问题：在剩余的待排序记录序列中找到最小关键码记录。  * •方法：     –直接选择排序     –堆排序  * @author bnc  *  */ public class SimpleSelectionSort {  //随机生成一组数  public static int[]  randomArray(int arrayLength,int maxNum){   int[] array=new int[arrayLength];   for(int i=0;i<array.length;i++){    array[i]=(int)(Math.random()*maxNum);   }   return array;  }  //数据交换  public static void swap(int[] data,int i,int j){   int temp=data[i];   data[i]=data[j];   data[j]=temp;  }  //打印出数组  public static void printArray(int[] array){   for(int i=0;i<array.length;i++){    System.out.print(array[i]+" ");   }   System.out.println();  }  ////简单的选择排序：  //基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。  public static void simpleSeclectSort(int[] array){   int i,j,min;   for(i=0;i<array.length;i++){    min=i;  //将当前下标定义最小下标    for(j=i+1;j<array.length;j++){ //循环之后的数据     if(array[min]>array[j])  //如果有小于当前值的最小数据      min=j;    //关键字的最小下标赋值给min    }    if(i!=min){      //若min!=i，说明找到最小值交换     swap(array,i,min); //最小的一个数与第i位置的数交换    }   }   System.out.println("排序后的数组：");   printArray(array);  }  ////简单的选择排序：  //基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。  public static void simpleSeclectSort1(int[] array){   int i,j,min;   for(i=0;i<array.length;i++){    min=array[i];    int n=i;//将当前下标定义最小下标    for(j=i+1;j<array.length;j++){ //循环之后的数据     if(min>array[j]){  //如果有小于当前值的最小数据      min=array[j];      n=j;   //关键字的最小下标赋值给min     }    }    array[n]=array[i];    array[i]=min;   }   System.out.println("排序后的数组：");   printArray(array);  }  public static void main(String[] args) {   int[] array=randomArray(10, 100);   System.out.println("排序前的数组：");   printArray(array);   simpleSeclectSort1(array);  } } 

package com.multiplesort.bnc; import java.util.Arrays; /**  * 选择排序:堆排序  * 适用于大数据  * 稳定性：不稳定  * 堆排序是一种树形选择排序，是对直接选择排序的有效改进。  * 堆的定义下：具有n个元素的序列 （h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2)时称之为堆。  *   在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二 叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。  * 思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个 堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。  * 然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对 它们作交换，最后得到有n个节点的有序序列。  * 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。  * 初始序列：50,10,90,30,70,40,80,60,20  * @author bnc  *  */ public class HeapSort {    //随机生成一组数  public static int[]  randomArray(int arrayLength,int maxNum){   int[] array=new int[arrayLength];   for(int i=0;i<array.length;i++){    array[i]=(int)(Math.random()*maxNum);   }   return array;  }  //数据交换  public static void swap(int[] data,int i,int j){   int temp=data[i];   data[i]=data[j];   data[j]=temp;  }  //打印出数组  public static void printArray(int[] array){   for(int i=0;i<array.length;i++){    System.out.print(array[i]+" ");   }   System.out.println();  }  /**   *构建大顶堆    * @param array 待建堆的数据   * @param lastIndex 从lastIndex处节点（最后一个节点）的父节点开始   */  public static void buildMaxHeap(int[] array,int lastIndex){    for(int i=(lastIndex-1)/2;i>=0;i--){     int k=i;  //k保存正在判断的节点      while(k*2+1<=lastIndex){  //如果当前k节点的子节点存在        int biggerIndex=2*k+1;  //k节点的左子节点的索引       if(biggerIndex<lastIndex){  //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在       if(array[biggerIndex]<array[biggerIndex+1])  //若果右子节点的值较大          biggerIndex++;  //biggerIndex总是记录较大子节点的索引        }      if(array[k]<array[biggerIndex]){  //如果k节点的值小于其较大的子节点的值         swap(array,k,biggerIndex);         k=biggerIndex; //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的      }      else        break;       }    }  }  //堆排序  public static void heapSort(int[] array){   int arrayLength=array.length;   //循环建堆     for(int i=0;i<arrayLength-1;i++){       buildMaxHeap(array,arrayLength-1-i);       //交换堆顶和最后一个元素     swap(array,0,arrayLength-1-i);     }   printArray(array);  }  //建大堆  public static void  HeapAdjust(int[] array,int s,int m){   int temp,j;   temp=array[s];   for(j=(2*s+1);j<m;j=(j*2+1)){    //System.out.println("j:"+j+" array[j]:"+array[j]);    if(j<m-1&&array[j]<array[j+1])     ++j;    if(temp>array[j])     break;    array[s]=array[j];    s=j;   }   array[s]=temp;  }  //堆排序  public static void heapSort1(int[] array){   int i,length;   length=array.length;   for(i=(length-1)/2;i>=0;i--)    HeapAdjust(array,i,length);   printArray(array);   for(i=length;i>1;i--){    swap(array,0,i-1);    HeapAdjust(array,0,i-1);   }   printArray(array);  }  public static void main(String[] args) {   int[] array={50,10,234,90,456,30,70,40,80,60,20,300,1000,1,30,1,45};   //heapSort(randomArray(11, 100));   int[] a = randomArray(15, 100);   heapSort1(a);  } } 

package com.multiplesort.bnc; /**  * 插入排序:  * 思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。  * 关键问题：在前面已经排好序的序列中找到合适的插入位置。  * 优点：记录本身基本有序，记录数比较少。  * 基本有序的定义：小的关键字基本在前面，大的基本在后面，不大不小基本在中间  * @author bnc  *  */ public class StraightInsertionSort {  //随机生成数组  public static int[] randomArray(int arrayLength,int maxNum){   int[] array=new int[arrayLength];   for(int i=0;i<array.length;i++){    array[i]=(int)(Math.random()*maxNum);   }   return array;  }  //数据交换  public static void swap(int[] data,int i,int j){   int temp=data[i];   data[i]=data[j];   data[j]=temp;  }  //打印出数组  public static void printArray(int[] array){   for(int i=0;i<array.length;i++){    System.out.print(array[i]+" ");   }   System.out.println();  }  /**   * 直接插入排序（从后向前找到合适位置后插入）   * 基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。   * 直接插入排序是稳定的排序。关于各种算法的稳定性分析可以参考http://www.cnblogs.com/Braveliu/archive/2013/01/15/2861201.html   * 文件初态不同时，若文件初态为正序算法的时间复杂度为O(n)，这时最好的情况。若初态为反序，则第i个待插入记录需要比较i+1次才能找到合适位置插入，故时间复杂度为O(n2)，这时最坏的情况。   * 直接插入排序的平均时间复杂度为O(n2)。   * @param array   */  public static void insertSort(int[] array){   System.out.println("直接插入排序前的结果");   printArray(array);   for(int i=1;i<array.length;i++){    int temp=array[i];  //待插入的元素    int j;    for(j=i-1;j>=0;j--){     if(array[j]>temp) //将大于temp的元素右移       array[j+1]=array[j];  //此时array[j+1]=array[j]=两者最大值     else      break;    }    array[j+1]=temp; //将待插入的元素赋值较小位置   }   System.out.println("直接插入排序后的结果");   printArray(array);  }  public static void insertSort1(int[] array){   System.out.println("直接插入排序前的结果");   printArray(array);   int i,j;   for(i=1;i<array.length;i++){      if(array[i]<array[i-1]){       int temp=array[i];  //设置哨兵       for(j=i-1;j>=0&&array[j]>=temp;j--){        array[j+1]=array[j];  //记录后移       }       array[j+1]=temp;//插入正确位置      }   }   System.out.println("直接插入排序后的结果");   printArray(array);  }  public static void main(String[] args) {   int[] array={57,68,59,52};   insertSort(randomArray(10, 100));   insertSort1(randomArray(10, 100));  } } 

package com.multiplesort.bnc; /**  * 希尔排序  * 基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；  *    然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。  * 我们知道一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。  * 希尔排序的时间性能优于直接插入排序，原因如下：   （1）当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。   （2）当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。   （3）在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，      但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。      因此，希尔排序在效率上较直接插人排序有较大的改进。  * 希尔排序的平均时间复杂度为O(nlogn)。  * @author bnc  *  */ public class ShellSort {  //随机生成数组  public static int[] randomArray(int arrayLength,int maxNum){   int[] array=new int[arrayLength];   for(int i=0;i<array.length;i++){    array[i]=(int)(Math.random()*maxNum);   }   return array;  }  //数据交换  public static void swap(int[] data,int i,int j){   int temp=data[i];   data[i]=data[j];   data[j]=temp;  }  //打印出数组  public static void printArray(int[] array){   for(int i=0;i<array.length;i++){    System.out.print(array[i]+" ");   }   System.out.println();  }  //希尔排序  public static void shellSort(int[] array){   System.out.println("希尔排序前的结果");   printArray(array);   int d=array.length;  //步长   while(true){    d=d/2;    for(int x=0;x<d;x++){     for(int i=x+d;i<array.length;i+=d){      int temp=array[i];      int j;      for(j=i-d;j>=0&&array[j]>temp;j-=d){       array[j+d]=array[j];      }      array[j+d]=temp;     }    }    if(d==1)     break;   }   System.out.println("希尔排序后的结果");   printArray(array);  }  //希尔排序  public static void shellSort1(int[] array){   System.out.println("希尔排序前的结果");   printArray(array);   int i,j;   int increment=array.length;   do{    increment=increment/3+1;    for(i=increment;i<array.length;i++){     if(array[i]<array[i-increment])     {      int temp=array[i];      for(j=i-increment;j>=0&&temp<array[j];j-=increment){       array[j+increment]=array[j];      }      array[j+increment]=temp;     }    }   }   while(increment>1);   System.out.println("希尔排序后的结果");   printArray(array);  }     public static void main(String[] args) {   int[] a={9,1,5,8,3,7,4,6,2};    //shellSort(randomArray(10, 100));   shellSort1(randomArray(20, 100));   //shellSort1(a);  } } 

package com.multiplesort.bnc; /**  * 归并排序  * 基本思想:归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列  * 分析:    归并排序是稳定的排序方法。    归并排序的时间复杂度为O(nlogn)。    速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。  * @author bnc  *  */ public class MergingSort {  //随机生成数组  public static int[] randomArray(int arrayLength,int maxNum){   int[] array=new int[arrayLength];   for(int i=0;i<array.length;i++){    array[i]=(int)(Math.random()*maxNum);   }   return array;  }  //数据交换  public static void swap(int[] data,int i,int j){   int temp=data[i];   data[i]=data[j];   data[j]=temp;  }  //打印出数组  public static void printArray(int[] array){   for(int i=0;i<array.length;i++){    System.out.print(array[i]+" ");   }   System.out.println();  }  //合并  private static void merge(int[] array, int left, int middle, int right) {   int[] tempArray=new int[array.length];   int mid=middle+1;//右边起始位置   int temp=left;   int third=left;   while(left<=middle&∣<=right){    //从两个数组中选取较小的数放入中间数组     if(array[left]<=array[mid]){        tempArray[third++] = array[left++];     }     else      tempArray[third++]=array[mid++];   }   //将剩余的部分放入中间数组    while(left<=middle){     tempArray[third++] = array[left++];    }    while(mid<=right){     tempArray[third++] = array[mid++];    }   //将中间数组复制回原数组    while(temp<=right){     array[temp] = tempArray[temp++];    }  }  //归并排序  private static void mergeSort(int[] array, int left, int right) {   if(left<right){    int middle=(left+right)/2;    //对左边进行递归    mergeSort(array, left, middle);    //对右边进行递归    mergeSort(array, middle+1, right);    //合并    merge(array,left,middle,right);   }  }  //稳定，归并排序（二路归并）[递归]  public static void mergingSort(int[] array){   System.out.println("归并排序前的结果");   printArray(array);   //归并排序   mergeSort(array,0,array.length-1);   System.out.println("归并排序前的结果");   printArray(array);  }  //两两归并  public static void Merge(int[] SR,int[] TR,int i,int m,int n){   int j,k,l;   for(j=m+1,k=i;i<=m&&j<=n;k++){    if(SR[i]<SR[j])     TR[k]=SR[i++];    else     TR[k]=SR[j++];   }   if(i<=m){    for(l=0;l<=m-i;l++)     TR[k+l]=SR[i+l];   }   if(j<=m){    for(l=0;l<=n-j;l++)     TR[k+l]=SR[j+l];   }  }  //归并  public static void MergePass(int[] SR,int[] TR,int s,int n){   int i=1;   int j;   while(i<=n-2*s-1){    Merge(SR,TR,i,i+s-1,i+2*s-1);    i=i+2*s;   }   if(i<n-s+1)    Merge(SR, TR, i, i+s-1, n);   else    for(j=i;j<=n;j++)     TR[j]=SR[j];  }  //稳定，归并排序（二路归并）[非递归]  public static void mergingSort1(int[] array){   System.out.println("归并排序前的结果");   printArray(array);   int[] tempArray=new int[array.length+1];   int k=0;   while(k<array.length){    MergePass(array,tempArray,k,array.length);    k=2*k+1;    MergePass(tempArray,array,k,array.length);    k=2*k+1;   }   System.out.println("归并排序前的结果");   printArray(array);  }  public static void main(String[] args) {   int[] array={50,10,90,30,70,40,80,60,20};   //mergingSort(randomArray(10, 100));   //mergingSort(array);   mergingSort1(array);  } } 

箱排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。

【例】要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序，需设置13个"箱子"，排序时依次将每张牌按点数放入相应的箱子里，然后依次将这些箱子首尾相接，就得到了按点数递增序排列的一副牌。

package com.multiplesort.bnc; import java.util.ArrayList; import java.util.List; /**  * 基数排序  * 基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。  * 基数排序是稳定的排序算法。   基数排序的时间复杂度为O(d(n+r)),d为位数，r为基数。  * @author bnc  *  */ public class RadixSort {  //随机生成数组  public static int[] randomArray(int arrayLength,int maxNum){   int[] array=new int[arrayLength];   for(int i=0;i<array.length;i++){    array[i]=(int)(Math.random()*maxNum);   }   return array;  }  //数据交换  public static void swap(int[] data,int i,int j){   int temp=data[i];   data[i]=data[j];   data[j]=temp;  }  //打印出数组  public static void printArray(int[] array){   for(int i=0;i<array.length;i++){    System.out.print(array[i]+" ");   }   System.out.println();  }  //基数排序  public static void radixSort(int[] array){   System.out.println("基数排序前的结果");   printArray(array);    //找到最大数，确定要排序几趟    int max = 0;    for (int i = 0; i < array.length; i++) {     if(max<array[i])      max = array[i];    }    //判断位数    int times = 0;    while(max>0){     max = max/10;     times++;    }    //建立十个队列     List<ArrayList> queue = new ArrayList<ArrayList>();     for (int i = 0; i < 10; i++) {      ArrayList queue1 = new ArrayList();      queue.add(queue1);     }   //进行times次分配和收集     for (int i = 0; i < times; i++) {    //分配      for (int j = 0; j < array.length; j++) {       int x = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);       ArrayList queue2 = queue.get(x);       queue2.add(array[j]);       queue.set(x,queue2);      }    //收集      int count = 0;      for (int j = 0; j < 10; j++) {       while(queue.get(j).size()>0){        ArrayList<Integer> queue3 = queue.get(j);        array[count] = queue3.get(0);        queue3.remove(0);        count++;       }      }     }   System.out.println("基数排序后的结果");   printArray(array);  }  public static void main(String[] args) {   radixSort(randomArray(10, 100));  } }