`
yangfuchao418
  • 浏览: 161270 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

java常用排序算法总结<二>【转】

    博客分类：
  • java
 
阅读更多

交换排序

冒泡排序

将最后一个元素与倒数第二个元素对比，如果最后一个元素比倒数第二个小，则交换两个元素的位置，再用倒数第二个元素与倒数第三个元数对比，直到比到第一个元素，这样经过第一趟排序后得到第一个最小元素。如此反复几过N（N=length-1）次后可得到排序结果。

Java代码  收藏代码
  1. package  sort;  
  2.   
  3. import  java.util.Comparator;  
  4.   
  5. /**  
  6.  * 冒泡排序算法  
  7.  * @author jzj  
  8.  * @date 2009-12-9  
  9.  *   
  10.  * @param <E>  
  11.  */   
  12. public   class  BubbleSort<E  extends  Comparable<E>>  extends  Sort<E> {  
  13.   
  14.     /**  
  15.      * 排序算法的实现，对数组中指定的元素进行排序  
  16.      * @param array 待排序的数组  
  17.      * @param from 从哪里开始排序  
  18.      * @param end 排到哪里  
  19.      * @param c 比较器  
  20.      */   
  21.     public   void  sort(E[] array,  int  from,  int  end, Comparator<E> c) {  
  22.         //需array.length - 1轮比较   
  23.         for  ( int  k =  1 ; k < end - from +  1 ; k++) {  
  24.             //每轮循环中从最后一个元素开始向前起泡，直到i=k止，即i等于轮次止   
  25.             for  ( int  i = end - from; i >= k; i--) {  
  26.                 //按照一种规则（后面元素不能小于前面元素）排序   
  27.                 if  (c.compare(array[i], array[i -  1 ]) <  0 ) {  
  28.                     //如果后面元素小于了（当然是大于还是小于要看比较器实现了）前面的元素，则前后交换   
  29.                     swap(array, i, i - 1 );  
  30.                 }  
  31.             }  
  32.         }  
  33.     }  
  34.   
  35.     /**   
  36.     * 测试   
  37.     * @param args   
  38.     */   
  39.     public   static   void  main(String[] args) {  
  40.         Integer[] intgArr = { 7 ,  2 ,  4 ,  3 ,  12 ,  1 ,  9 ,  6 ,  8 ,  5 ,  11 ,  10  };  
  41.         BubbleSort<Integer> sort = new  BubbleSort<Integer>();  
  42.         BubbleSort.testSort(sort, intgArr);  
  43.         BubbleSort.testSort(sort, null );  
  44.     }  
  45. }  

快速排序

快速排序采用了分治法的思想，把大的问题分解为同类型的小问题。
一般分如下步骤：
1）选择一个中枢元素（有很多选法，我的实现里使用第一个元素为中枢的简单方法）
2）以该中枢元素为基准点，将小于中枢的元素放在中枢后集合的前部分，比它大的在集合后部分，待集合基本排序完成后（此时前部分元素小于后部分元素），把中枢元素放在合适的位置。
3）根据中枢元素最后确定的位置，把数组分成三部分，左边的，右边的，枢纽元素自己，对左边的，右边的分别递归调用快速排序算法即可。

这里的重点与难点在于第二步，实现的方式有很多种，我这里实现了三种。
第一种实现 （partition1方法）：
以第一个元素为中枢元素，在中枢元素后面集合中从前往后寻找第一个比中枢元素小的元素，并与第一个元素交换，然后从剩余的元素中寻找第二个比中枢元素小的 元素，并与第二位元素交换，这样直到所有小于中枢元素找完为止，并记下最后一次放置小于中枢的元素位置minIndex（即小于中枢与大于中枢的分界）， 并将中枢元素与minIndex位置元素互换，然后对中枢元素两边的序列进行同样的操作。
此种实现最为简洁，处理过程中不需要把中枢元素移来移去，只是在其它元素完成基本排序后（前部分小于后部分元素）再把中枢元素放置到适当的位置

第二种实现 （partition2方法）：
以第一个元素为中枢元素，刚开始时使用低指针指向中枢元素。当中枢元素在低指针位置时，此时我们判断高指针指向的元素是否小于中枢元素，如果大于中枢元素 则高指针继续向头移动，如果小于则与中枢元素交换，此时中枢元素被移到了高指针位置；当中枢元素在高指针位置时，我们此时判断低指针指向的元素是否大于中 枢元素，如果小于中枢元素则低指针继续向尾移动，如果大于则与中枢元素交换，此时中枢元素又回到了低指针位置；这时是拿高还是低指针所指向的元素与中枢比 较时根据前面逻辑来处理，直到高低指针指向同一位置则完成一轮排序，然后再对中枢元素两边的序列进行同样的操作直到排序完成
此种实现逻辑比较好理解，中枢元素的永远在低指针或指针所指向的位置，每次找到需处理的元 素后，要与中枢交换，中枢就像皮球一样从这里踢到那里，又从那里踢到这里。但此种实现会频繁地交换中枢元素，性能可能不如第一种

第三种实现 （partition3方法）：
此种方式与前两种方式不太一样，同时移动高低指针，低指针向尾找出大于等于中枢的元素，而高向头找出小于中枢的元素，待两者都找出后交换高低指针所指向的 元素，直到高低指针指向同一位置止，然后比较中枢与高低指针所指向的元素大小，如果中枢元素大，则直接与高低指针元素交换，如果中枢元素小于等于高低指针 元素，则中枢元素与高低指针前一元素交换，完成一轮比较，然后再对中枢元素两边的序列进行同样的操作直到排序完成

此种方式有点难度，在移动元素时要注意的是：与中枢相等的元素也要向集合后部移动，不然的话如[3,3,0,3,3]第一轮排序结果不准确，虽然最后结果 正确。当中枢后面的元素集合移动完成后，还得要把中枢元素放置在集合中的合适位置，这就需要找准集合中前部分与后部分的边界，最后只能把中枢元素与最后一 个小于中枢的元素进位置互换。但此种实现方式与第一种有点像，也不需要把中枢元素调来调去的，而是待后面集合排序完成后将中枢放入适当位置

Java代码  收藏代码
  1. package  sort;  
  2.   
  3. import  java.util.Arrays;  
  4. import  java.util.Comparator;  
  5.   
  6. /**  
  7.  * 快速排序算法  
  8.  * @author jzj  
  9.  * @date 2009-12-9  
  10.  *   
  11.  * @param <E>  
  12.  */   
  13. public   class  QuickSort<E  extends  Comparable<E>>  extends  Sort<E> {  
  14.   
  15.     /**  
  16.      * 排序算法的实现，对数组中指定的元素进行排序  
  17.      * @param array 待排序的数组  
  18.      * @param from 从哪里开始排序  
  19.      * @param end 排到哪里  
  20.      * @param c 比较器  
  21.      */   
  22.     public   void  sort(E[] array,  int  from,  int  end, Comparator<E> c) {  
  23.         quickSort(array, from, end, c);  
  24.     }  
  25.   
  26.     /**  
  27.      * 递归快速排序实现  
  28.      * @param array 待排序数组  
  29.      * @param low 低指针  
  30.      * @param high 高指针  
  31.      * @param c 比较器  
  32.      */   
  33.     private   void  quickSort(E[] array,  int  low,  int  high, Comparator<E> c) {  
  34.         /*  
  35.          * 如果分区中的低指针小于高指针时循环；如果low=higth说明数组只有一个元素，无需再处理；  
  36.          * 如果low > higth，则说明上次枢纽元素的位置pivot就是low或者是higth，此种情况  
  37.          * 下分区不存，也不需处理  
  38.          */   
  39.         if  (low < high) {  
  40.             //对分区进行排序整理   
  41.             int  pivot = partition1(array, low, high, c);  
  42.             /*  
  43.              * 以pivot为边界，把数组分成三部分[low, pivot - 1]、[pivot]、[pivot + 1, high]  
  44.              * 其中[pivot]为枢纽元素，不需处理，再对[low, pivot - 1]与[pivot + 1, high]  
  45.              * 各自进行分区排序整理与进一步分区  
  46.              */   
  47.             quickSort(array, low, pivot - 1 , c);  
  48.             quickSort(array, pivot + 1 , high, c);  
  49.         }  
  50.   
  51.     }  
  52.   
  53.     /**  
  54.      * 实现一  
  55.      *   
  56.      * @param array 待排序数组  
  57.      * @param low 低指针  
  58.      * @param high 高指针  
  59.      * @param c 比较器  
  60.      * @return int 调整后中枢位置  
  61.      */   
  62.     private   int  partition1(E[] array,  int  low,  int  high, Comparator<E> c) {  
  63.         E pivotElem = array[low];//以第一个元素为中枢元素   
  64.         //从前向后依次指向比中枢元素小的元素，刚开始时指向中枢，也是小于与大小中枢的元素的分界点   
  65.         int  border = low;  
  66.   
  67.         /*  
  68.          * 在中枢元素后面的元素中查找小于中枢元素的所有元素，并依次从第二个位置从前往后存放  
  69.          * 注，这里最好使用i来移动，如果直接移动low的话，最后不知道数组的边界了，但后面需要  
  70.          * 知道数组的边界  
  71.          */   
  72.         for  ( int  i = low +  1 ; i <= high; i++) {  
  73.             //如果找到一个比中枢元素小的元素   
  74.             if  (c.compare(array[i], pivotElem) <  0 ) {  
  75.                 swap(array, ++border, i);//border前移，表示有小于中枢元素的元素   
  76.             }  
  77.         }  
  78.         /*  
  79.          * 如果border没有移动时说明说明后面的元素都比中枢元素要大，border与low相等，此时是  
  80.          * 同一位置交换，是否交换都没关系；当border移到了high时说明所有元素都小于中枢元素，此  
  81.          * 时将中枢元素与最后一个元素交换即可，即low与high进行交换，大的中枢元素移到了 序列最  
  82.          * 后；如果 low <minIndex< high，表 明中枢后面的元素前部分小于中枢元素，而后部分大于  
  83.          * 中枢元素，此时中枢元素与前部分数组中最后一个小于它的元素交换位置，使得中枢元素放置在  
  84.          * 正确的位置  
  85.          */   
  86.         swap(array, border, low);  
  87.         return  border;  
  88.     }  
  89.   
  90.     /**  
  91.      * 实现二  
  92.      *   
  93.      * @param array 待排序数组  
  94.      * @param low 待排序区低指针  
  95.      * @param high 待排序区高指针  
  96.      * @param c 比较器  
  97.      * @return int 调整后中枢位置  
  98.      */   
  99.     private   int  partition2(E[] array,  int  low,  int  high, Comparator<E> c) {  
  100.         int  pivot = low; //中枢元素位置，我们以第一个元素为中枢元素   
  101.         //退出条件这里只可能是 low = high   
  102.         while  ( true ) {  
  103.             if  (pivot != high) { //如果中枢元素在低指针位置时，我们移动高指针   
  104.                 //如果高指针元素小于中枢元素时，则与中枢元素交换   
  105.                 if  (c.compare(array[high], array[pivot]) <  0 ) {  
  106.                     swap(array, high, pivot);  
  107.                     //交换后中枢元素在高指针位置了   
  108.                     pivot = high;  
  109.                 } else  { //如果未找到小于中枢元素，则高指针前移继续找   
  110.                     high--;  
  111.                 }  
  112.             } else  { //否则中枢元素在高指针位置   
  113.                 //如果低指针元素大于中枢元素时，则与中枢元素交换   
  114.                 if  (c.compare(array[low], array[pivot]) >  0 ) {  
  115.                     swap(array, low, pivot);  
  116.                     //交换后中枢元素在低指针位置了   
  117.                     pivot = low;  
  118.                 } else  { //如果未找到大于中枢元素，则低指针后移继续找   
  119.                     low++;  
  120.                 }  
  121.             }  
  122.             if  (low == high) {  
  123.                 break ;  
  124.             }  
  125.         }  
  126.         //返回中枢元素所在位置，以便下次分区   
  127.         return  pivot;  
  128.     }  
  129.   
  130.     /**  
  131.      * 实现三  
  132.      *   
  133.      * @param array 待排序数组  
  134.      * @param low 待排序区低指针  
  135.      * @param high 待排序区高指针  
  136.      * @param c 比较器  
  137.      * @return int 调整后中枢位置  
  138.      */   
  139.     private   int  partition3(E[] array,  int  low,  int  high, Comparator<E> c) {  
  140.         int  pivot = low; //中枢元素位置，我们以第一个元素为中枢元素   
  141.         low++;  
  142.         //----调整高低指针所指向的元素顺序，把小于中枢元素的移到前部分，大于中枢元素的移到后面部分   
  143.         //退出条件这里只可能是 low = high   
  144.   
  145.         while  ( true ) {  
  146.             //如果高指针未超出低指针   
  147.             while  (low < high) {  
  148.                 //如果低指针指向的元素大于或等于中枢元素时表示找到了，退出，注：等于时也要后移   
  149.                 if  (c.compare(array[low], array[pivot]) >=  0 ) {  
  150.                     break ;  
  151.                 } else  { //如果低指针指向的元素小于中枢元素时继续找   
  152.                     low++;  
  153.                 }  
  154.             }  
  155.   
  156.             while  (high > low) {  
  157.                 //如果高指针指向的元素小于中枢元素时表示找到，退出   
  158.                 if  (c.compare(array[high], array[pivot]) <  0 ) {  
  159.                     break ;  
  160.                 } else  { //如果高指针指向的元素大于中枢元素时继续找   
  161.                     high--;  
  162.                 }  
  163.             }  
  164.             //退出上面循环时 low = high   
  165.             if  (low == high) {  
  166.                 break ;  
  167.             }  
  168.   
  169.             swap(array, low, high);  
  170.         }  
  171.   
  172.         //----高低指针所指向的元素排序完成后，还得要把中枢元素放到适当的位置   
  173.         if  (c.compare(array[pivot], array[low]) >  0 ) {  
  174.             //如果退出循环时中枢元素大于了低指针或高指针元素时，中枢元素需与low元素交换   
  175.             swap(array, low, pivot);  
  176.             pivot = low;  
  177.         } else   if  (c.compare(array[pivot], array[low]) <=  0 ) {  
  178.             swap(array, low - 1 , pivot);  
  179.             pivot = low - 1 ;  
  180.         }  
  181.   
  182.         //返回中枢元素所在位置，以便下次分区   
  183.         return  pivot;  
  184.     }  
  185.   
  186.     /**   
  187.     * 测试   
  188.     * @param args   
  189.     */   
  190.     public   static   void  main(String[] args) {  
  191.         Integer[] intgArr = { 3 ,  1 ,  1 ,  1 ,  1 ,  1 ,  1  };  
  192.         QuickSort<Integer> sort = new  QuickSort<Integer>();  
  193.         QuickSort.testSort(sort, intgArr);  
  194.         QuickSort.testSort(sort, null );  
  195.     }  
  196. }   

归并排序

Java代码  收藏代码
  1. package  sort;  
  2.   
  3. import  java.lang.reflect.Array;  
  4. import  java.util.Comparator;  
  5.   
  6. /**  
  7.  * 归并排序算法  
  8.  * @author jzj  
  9.  * @date 2009-12-11  
  10.  *   
  11.  * @param <E>  
  12.  */   
  13. public   class  MergeSort<E  extends  Comparable<E>>  extends  Sort<E> {  
  14.   
  15.     /**  
  16.      * 排序算法的实现，对数组中指定的元素进行排序  
  17.      * @param array 待排序的数组  
  18.      * @param from 从哪里开始排序  
  19.      * @param end 排到哪里  
  20.      * @param c 比较器  
  21.      */   
  22.     public   void  sort(E[] arr,  int  from,  int  end, Comparator<E> c) {  
  23.         partition(arr, from, end, c);  
  24.     }  
  25.   
  26.     /**  
  27.      * 递归划分数组  
  28.      * @param arr  
  29.      * @param from  
  30.      * @param end  
  31.      * @param c void  
  32.      */   
  33.     private   void  partition(E[] arr,  int  from,  int  end, Comparator<E> c) {  
  34.         //划分到数组只有一个元素时才不进行再划分   
  35.         if  (from < end) {  
  36.             //从中间划分成两个数组   
  37.             int  mid = (from + end) /  2 ;  
  38.             partition(arr, from, mid, c);  
  39.             partition(arr, mid + 1 , end, c);  
  40.             //合并划分后的两个数组   
  41.             merge(arr, from, end, mid, c);  
  42.         }  
  43.     }  
  44.   
  45.     /**  
  46.      * 数组合并，合并过程中对两部分数组进行排序  
  47.      * 前后两部分数组里是有序的  
  48.      * @param arr  
  49.      * @param from  
  50.      * @param end  
  51.      * @param mid  
  52.      * @param c void  
  53.      */   
  54.     private   void  merge(E[] arr,  int  from,  int  end,  int  mid, Comparator<E> c) {  
  55.         E[] tmpArr = (E[]) Array.newInstance(arr[0 ].getClass(), end - from +  1 );  
  56.         int  tmpArrIndex =  0 ; //指向临时数组   
  57.         int  part1ArrIndex = from; //指向第一部分数组   
  58.         int  part2ArrIndex = mid +  1 ; //指向第二部分数组   
  59.   
  60.         //由于两部分数组里是有序的，所以每部分可以从第一个元素依次取到最后一个元素，再对两部分   
  61.         //取出的元素进行比较。只要某部分数组元素取完后，退出循环   
  62.         while  ((part1ArrIndex <= mid) && (part2ArrIndex <= end)) {  
  63.             //从两部分数组里各取一个进行比较，取最小一个并放入临时数组中   
  64.             if  (c.compare(arr[part1ArrIndex], arr[part2ArrIndex]) <  0 ) {  
  65.                 //如果第一部分数组元素小，则将第一部分数组元素放入临时数组中，并且临时数组指针   
  66.                 //tmpArrIndex下移一个以做好下次存储位置准备，前部分数组指针part1ArrIndex   
  67.                 //也要下移一个以便下次取出下一个元素与后部分数组元素比较   
  68.                 tmpArr[tmpArrIndex++] = arr[part1ArrIndex++];  
  69.             } else  {  
  70.                 //如果第二部分数组元素小，则将第二部分数组元素放入临时数组中   
  71.                 tmpArr[tmpArrIndex++] = arr[part2ArrIndex++];  
  72.             }  
  73.         }  
  74.         //由于退出循环后，两部分数组中可能有一个数组元素还未处理完，所以需要额外的处理，当然不可   
  75.         //能两部分数组都有未处理完的元素，所以下面两个循环最多只有一个会执行，并且都是大于已放入   
  76.         //临时数组中的元素   
  77.         while  (part1ArrIndex <= mid) {  
  78.             tmpArr[tmpArrIndex++] = arr[part1ArrIndex++];  
  79.         }  
  80.         while  (part2ArrIndex <= end) {  
  81.             tmpArr[tmpArrIndex++] = arr[part2ArrIndex++];  
  82.         }  
  83.   
  84.         //最后把临时数组拷贝到源数组相同的位置   
  85.         System.arraycopy(tmpArr, 0 , arr, from, end - from +  1 );  
  86.     }  
  87.   
  88.     /**  
  89.      * 测试  
  90.      * @param args  
  91.      */   
  92.     public   static   void  main(String[] args) {  
  93.         Integer[] intgArr = { 5 ,  9 ,  1 ,  4 ,  1 ,  2 ,  6 ,  3 ,  8 ,  0 ,  7  };  
  94.         MergeSort<Integer> insertSort = new  MergeSort<Integer>();  
  95.         Sort.testSort(insertSort, intgArr);  
  96.         Sort.testSort(insertSort, null );  
  97.     }  
  98. }   

基数排序

基数排序的主要思路是,将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.

它的理论比较容易理解，但实现却有一点绕。


Java代码  收藏代码
  1. package  sort;  
  2.   
  3. import  java.util.Arrays;  
  4.   
  5. public   class  RadixSort {  
  6.   
  7.     /**  
  8.      * 取数x上的第d位数字  
  9.      * @param x 数  
  10.      * @param d 第几位，从低位到高位  
  11.      * @return  
  12.      */   
  13.     public   int  digit( long  x,  long  d) {  
  14.   
  15.         long  pow =  1 ;  
  16.         while  (--d >  0 ) {  
  17.             pow *= 10 ;  
  18.         }  
  19.         return  ( int ) (x / pow %  10 );  
  20.     }  
  21.   
  22.     /**  
  23.      * 基数排序实现，以升序排序（下面程序中的位记录器count中，从第0个元素到第9个元素依次用来  
  24.      * 记录当前比较位是0的有多少个..是9的有多少个数，而降序时则从第0个元素到第9个元素依次用来  
  25.      * 记录当前比较位是9的有多少个..是0的有多少个数）  
  26.      * @param arr 待排序数组  
  27.      * @param digit 数组中最大数的位数  
  28.      * @return  
  29.      */   
  30.     public   long [] radixSortAsc( long [] arr) {  
  31.         //从低位往高位循环   
  32.         for  ( int  d =  1 ; d <= getMax(arr); d++) {  
  33.             //临时数组，用来存放排序过程中的数据   
  34.             long [] tmpArray =  new   long [arr.length];  
  35.             //位记数器，从第0个元素到第9个元素依次用来记录当前比较位是0的有多少个..是9的有多少个数   
  36.             int [] count =  new   int [ 10 ];  
  37.             //开始统计0有多少个，并存储在第0位，再统计1有多少个，并存储在第1位..依次统计到9有多少个   
  38.             for  ( int  i =  0 ; i < arr.length; i++) {  
  39.                 count[digit(arr[i], d)] += 1 ;  
  40.             }  
  41.             /*  
  42.              * 比如某次经过上面统计后结果为：[0, 2, 3, 3, 0, 0, 0, 0, 0, 0]则经过下面计算后 结果为：  
  43.              * [0, 2, 5, 8, 8, 8, 8, 8, 8, 8]但实质上只有如下[0, 2, 5, 8, 0, 0, 0, 0, 0, 0]中  
  44.              * 非零数才用到，因为其他位不存在，它们分别表示如下：2表示比较位为1的元素可以存放在索引为1、0的  
  45.              * 位置，5表示比较位为2的元素可以存放在4、3、2三个(5-2=3)位置，8表示比较位为3的元素可以存放在  
  46.              * 7、6、5三个(8-5=3)位置  
  47.              */   
  48.             for  ( int  i =  1 ; i <  10 ; i++) {  
  49.                 count[i] += count[i - 1 ];  
  50.             }  
  51.   
  52.             /*  
  53.              * 注，这里只能从数组后往前循环，因为排序时还需保持以前的已排序好的 顺序，不应该打  
  54.              * 乱原来已排好的序，如果从前往后处理，则会把原来在前面会摆到后面去，因为在处理某个  
  55.              * 元素的位置时，位记数器是从大到到小（count[digit(arr[i], d)]--）的方式来处  
  56.              * 理的，即先存放索引大的元素，再存放索引小的元素，所以需从最后一个元素开始处理。  
  57.              * 如有这样的一个序列[212,213,312]，如果按照从第一个元素开始循环的话，经过第一轮  
  58.              * 后（个位）排序后，得到这样一个序列[312,212,213]，第一次好像没什么问题，但问题会  
  59.              * 从第二轮开始出现，第二轮排序后，会得到[213,212,312]，这样个位为3的元素本应该  
  60.              * 放在最后，但经过第二轮后却排在了前面了，所以出现了问题  
  61.              */   
  62.             for  ( int  i = arr.length -  1 ; i >=  0 ; i--) { //只能从最后一个元素往前处理   
  63.                 //for (int i = 0; i < arr.length; i++) {//不能从第一个元素开始循环   
  64.                 tmpArray[count[digit(arr[i], d)] - 1 ] = arr[i];  
  65.                 count[digit(arr[i], d)]--;  
  66.             }  
  67.   
  68.             System.arraycopy(tmpArray, 0 , arr,  0 , tmpArray.length);  
  69.         }  
  70.         return  arr;  
  71.     }  
  72.   
  73.     /**  
  74.      * 基数排序实现，以降序排序（下面程序中的位记录器count中，从第0个元素到第9个元素依次用来  
  75.      * 记录当前比较位是0的有多少个..是9的有多少个数，而降序时则从第0个元素到第9个元素依次用来  
  76.      * 记录当前比较位是9的有多少个..是0的有多少个数）  
  77.      * @param arr 待排序数组  
  78.      * @return  
  79.      */   
  80.     public   long [] radixSortDesc( long [] arr) {  
  81.         for  ( int  d =  1 ; d <= getMax(arr); d++) {  
  82.             long [] tmpArray =  new   long [arr.length];  
  83.             //位记数器，从第0个元素到第9个元素依次用来记录当前比较位是9的有多少个..是0的有多少个数   
  84.             int [] count =  new   int [ 10 ];  
  85.             //开始统计0有多少个，并存储在第9位，再统计1有多少个，并存储在第8位..依次统计   
  86.             //到9有多少个，并存储在第0位   
  87.             for  ( int  i =  0 ; i < arr.length; i++) {  
  88.                 count[9  - digit(arr[i], d)] +=  1 ;  
  89.             }  
  90.   
  91.             for  ( int  i =  1 ; i <  10 ; i++) {  
  92.                 count[i] += count[i - 1 ];  
  93.             }  
  94.   
  95.             for  ( int  i = arr.length -  1 ; i >=  0 ; i--) {  
  96.                 tmpArray[count[9  - digit(arr[i], d)] -  1 ] = arr[i];  
  97.                 count[9  - digit(arr[i], d)]--;  
  98.             }  
  99.   
  100.             System.arraycopy(tmpArray, 0 , arr,  0 , tmpArray.length);  
  101.         }  
  102.         return  arr;  
  103.     }  
  104.   
  105.     private   int  getMax( long [] array) {  
  106.         int  maxlIndex =  0 ;  
  107.         for  ( int  j =  1 ; j < array.length; j++) {  
  108.             if  (array[j] > array[maxlIndex]) {  
  109.                 maxlIndex = j;  
  110.             }  
  111.         }  
  112.         return  String.valueOf(array[maxlIndex]).length();  
  113.     }  
  114.   
  115.     public   static   void  main(String[] args) {  
  116.         long [] ary =  new   long [] {  123 ,  321 ,  132 ,  212 ,  213 ,  312 ,  21 ,  223  };  
  117.         RadixSort rs = new  RadixSort();  
  118.         System.out.println("升 - "  + Arrays.toString(rs.radixSortAsc(ary)));  
  119.   
  120.         ary = new   long [] {  123 ,  321 ,  132 ,  212 ,  213 ,  312 ,  21 ,  223  };  
  121.         System.out.println("降 - "  + Arrays.toString(rs.radixSortDesc(ary)));  
  122.     }  
  123. }  

时间复杂度与空间复杂度对比表

 

原文：http://jiangzhengjun.iteye.com/blog/547735

分享到：
| java常用排序算法总结<一>【转】
评论
1 楼 xiaoyun3982116 2012-05-30  
代码准确率再高点就很好了
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics