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

（转）内部排序

 
阅读更多

http://justsee.iteye.com/blog/1098724

常见的内部排序：

下面介绍这十种常见内部排序（都是从小到大的排序）

直接选择排序

Java代码  收藏代码
  1. import  java.util.*;  
  2. //定义一个数据包装类   
  3. class  DataWrap  implements  Comparable<DataWrap>  
  4. {  
  5.     int  data;  
  6.     String flag;  
  7.     public  DataWrap( int  data, String flag)  
  8.     {  
  9.         this .data = data;  
  10.         this .flag = flag;  
  11.     }  
  12.     public  String toString()  
  13.     {  
  14.         return  data + flag;  
  15.     }  
  16.     //根据data实例变量来决定两个DataWrap的大小   
  17.     public   int  compareTo(DataWrap dw)  
  18.     {  
  19.         return   this .data > dw.data ?  1    
  20.             : (this .data == dw.data ?  0  : - 1 );  
  21.     }  
  22. }  
  23. public   class  SelectSort  
  24. {  
  25.     public   static   void  selectSort(DataWrap[] data)   
  26.     {  
  27.         System.out.println("开始排序" );  
  28.         int  arrayLength = data.length;  
  29.         //依次进行n－1趟比较, 第i趟比较将第i大的值选出放在i位置上。   
  30.         for  ( int  i =  0 ; i < arrayLength -  1  ; i++ )  
  31.         {  
  32.             int  minIndex = i ;  
  33.             //第i个数据只需和它后面的数据比较   
  34.             for  ( int  j = i +  1  ; j < arrayLength ; j++ )  
  35.             {                 
  36.                 //如果第i位置的数据 > j位置的数据, 交换它们   
  37.                 if  (data[i].compareTo(data[j]) >  0 )  
  38.                 {  
  39.                     DataWrap tmp = data[i];  
  40.                     data[i] = data[j];  
  41.                     data[j] = tmp;  
  42.                 }  
  43.             }  
  44.             System.out.println(java.util.Arrays.toString(data));  
  45.         }  
  46.     }  
  47.     public   static   void  main(String[] args)  
  48.     {  
  49.         DataWrap[] data = {  
  50.             new  DataWrap( 21  ,  "" ),  
  51.             new  DataWrap( 30  ,  "" ),  
  52.             new  DataWrap( 49  ,  "" ),  
  53.             new  DataWrap( 30  ,  "*" ),  
  54.             new  DataWrap( 16  ,  "" ),  
  55.             new  DataWrap( 9  ,  "" )  
  56.         };  
  57.         System.out.println("排序之前：\n"   
  58.             + java.util.Arrays.toString(data));  
  59.         selectSort(data);  
  60.         System.out.println("排序之后：\n"    
  61.             + java.util.Arrays.toString(data));  
  62.     }  
  63. }  

 优化后：

Java代码  收藏代码
  1. import  java.util.*;  
  2. class  DataWrap  implements  Comparable<DataWrap>  
  3. {  
  4.     int  data;  
  5.     String flag;  
  6.     public  DataWrap( int  data, String flag)  
  7.     {  
  8.         this .data = data;  
  9.         this .flag = flag;  
  10.     }  
  11.     public  String toString()  
  12.     {  
  13.         return  data + flag;  
  14.     }  
  15.     public   int  compareTo(DataWrap dw)  
  16.     {  
  17.         return   this .data > dw.data ?  1    
  18.             : (this .data == dw.data ?  0  : - 1 );  
  19.     }  
  20. }  
  21. public   class  SelectSort2  
  22. {  
  23.     public   static   void  selectSort(DataWrap[] data)   
  24.     {  
  25.         System.out.println("开始排序" );  
  26.         int  arrayLength = data.length;  
  27.         //依次进行n－1趟比较, 第i趟比较将第i大的值选出放在i位置上。   
  28.         for  ( int  i =  0 ; i < arrayLength -  1  ; i++ )  
  29.         {  
  30.             //minIndex永远保留本趟比较中最小值的索引   
  31.             int  minIndex = i ;  
  32.             //第i个数据只需和它后面的数据比较   
  33.             for  ( int  j = i +  1  ; j < arrayLength ; j++ )  
  34.             {  
  35.                 //如果第minIndex位置的数据 > j位置的数据   
  36.                 if  (data[minIndex].compareTo(data[j]) >  0 )  
  37.                 {  
  38.                     //将j的值赋给minIndex   
  39.                     minIndex = j;  
  40.                 }  
  41.             }  
  42.             //每趟比较最多交换一次   
  43.             if  (minIndex != i)  
  44.             {  
  45.                 DataWrap tmp = data[i];  
  46.                 data[i] = data[minIndex];  
  47.                 data[minIndex] = tmp;  
  48.             }  
  49.             System.out.println(java.util.Arrays.toString(data));  
  50.         }  
  51.     }  
  52.     public   static   void  main(String[] args)  
  53.     {  
  54.         DataWrap[] data = {  
  55.             new  DataWrap( 21  ,  "" ),  
  56.             new  DataWrap( 30  ,  "" ),  
  57.             new  DataWrap( 49  ,  "" ),  
  58.             new  DataWrap( 30  ,  "*" ),  
  59.             new  DataWrap( 16  ,  "" ),  
  60.             new  DataWrap( 9  ,  "" )  
  61.         };  
  62.         System.out.println("排序之前：\n"   
  63.             + java.util.Arrays.toString(data));  
  64.         selectSort(data);  
  65.         System.out.println("排序之后：\n"    
  66.             + java.util.Arrays.toString(data));  
  67.     }  
  68. }  
  69. //时间复杂度：n的平方   
  70. //空间复杂度：1   
  71. //稳定性：不稳定   

堆排序

建大堆求得从小到大的排序。每次建立大堆把大堆顶与数组最后一个元素交换。

Java代码  收藏代码
  1. import  java.util.*;  
  2. //定义一个数据包装类   
  3. class  DataWrap  implements  Comparable<DataWrap>  
  4. {  
  5.     int  data;  
  6.     String flag;  
  7.     public  DataWrap( int  data, String flag)  
  8.     {  
  9.         this .data = data;  
  10.         this .flag = flag;  
  11.     }  
  12.     public  String toString()  
  13.     {  
  14.         return  data + flag;  
  15.     }  
  16.     //根据data实例变量来决定两个DataWrap的大小   
  17.     public   int  compareTo(DataWrap dw)  
  18.     {  
  19.         return   this .data > dw.data ?  1    
  20.             : (this .data == dw.data ?  0  : - 1 );  
  21.     }  
  22. }  
  23. public   class  HeapSort  
  24. {  
  25.     public   static   void  heapSort(DataWrap[] data)   
  26.     {  
  27.         System.out.println("开始排序" );  
  28.         int  arrayLength = data.length;  
  29.         //循环建堆   
  30.         for  ( int  i =  0 ; i < arrayLength -  1  ; i++ ) //n-1次循环   
  31.         {  
  32.             //建堆   
  33.             builMaxdHeap(data , arrayLength - 1  - i);  
  34.             //交换堆顶和最后一个元素   
  35.             swap(data , 0  , arrayLength -  1  - i);  
  36.             System.out.println(java.util.Arrays.toString(data));  
  37.         }  
  38.     }  
  39.     //对data数组从0到lastIndex建大顶堆   
  40.     private   static   void  builMaxdHeap(DataWrap[] data ,  int  lastIndex)  
  41.     {  
  42.         //从lastIndex处节点（最后一个节点）的父节点开始   
  43.         for  ( int  i = (lastIndex -  1 ) /  2  ; i >=  0   ; i--)  
  44.         {  
  45.             //k保存当前正在判断的节点   
  46.             int  k = i;  
  47.             //如果当前k节点的子节点存在   
  48.             while  (k *  2  +  1  <= lastIndex)  
  49.             {  
  50.                 //k节点的左子节点的索引   
  51.                 int  biggerIndex =  2  * k  +  1 ;   
  52.                 //如果biggerIndex小于lastIndex，即biggerIndex + 1   
  53.                 //代表的k节点的右子节点存在   
  54.                 if  (biggerIndex < lastIndex)  
  55.                 {  
  56.                      //如果右子节点的值较大   
  57.                     if (data[biggerIndex].compareTo(data[biggerIndex +  1 ]) <  0 )  
  58.                     {  
  59.                         //biggerIndex总是记录较大子节点的索引   
  60.                         biggerIndex++;   
  61.                     }  
  62.                 }  
  63.                 //如果k节点的值小于其较大子节点的值   
  64.                 if (data[k].compareTo(data[biggerIndex]) <  0 )  
  65.                 {  
  66.                     //交换它们   
  67.                     swap(data , k , biggerIndex);  
  68.                     //将biggerIndex赋给k，开始while循环的下一次循环，   
  69.                     //重新保证k节点的值大于其左、右子节点的值。   
  70.                     k = biggerIndex;  
  71.                 }  
  72.                 else   
  73.                 {  
  74.                     break ;  
  75.                 }  
  76.             }  
  77.         }  
  78.     }  
  79.     //交换data数组中i、j两个索引处的元素   
  80.     private   static   void  swap(DataWrap[] data ,  int  i ,  int  j)  
  81.     {  
  82.         DataWrap tmp = data[i];  
  83.         data[i] = data[j];  
  84.         data[j] = tmp;  
  85.     }  
  86.     public   static   void  main(String[] args)  
  87.     {  
  88.         DataWrap[] data = {  
  89.             new  DataWrap( 21  ,  "" ),  
  90.             new  DataWrap( 30  ,  "" ),  
  91.             new  DataWrap( 49  ,  "" ),  
  92.             new  DataWrap( 30  ,  "*" ),  
  93.             new  DataWrap( 21  ,  "*" ),  
  94.             new  DataWrap( 16  ,  "" ),  
  95.             new  DataWrap( 9  ,  "" )  
  96.         };  
  97.         System.out.println("排序之前：\n"   
  98.             + java.util.Arrays.toString(data));  
  99.         heapSort(data);  
  100.         System.out.println("排序之后：\n"    
  101.             + java.util.Arrays.toString(data));  
  102.     }  
  103. }  
  104. //时间复杂度：nlog2n   
  105. //空间复杂度：1   
  106. //稳定性：不稳定   

 冒泡排序

Java代码  收藏代码
  1. import  java.util.*;  
  2. //定义一个数据包装类   
  3. class  DataWrap  implements  Comparable<DataWrap>  
  4. {  
  5.     int  data;  
  6.     String flag;  
  7.     public  DataWrap( int  data, String flag)  
  8.     {  
  9.         this .data = data;  
  10.         this .flag = flag;  
  11.     }  
  12.     public  String toString()  
  13.     {  
  14.         return  data + flag;  
  15.     }  
  16.     //根据data实例变量来决定两个DataWrap的大小   
  17.     public   int  compareTo(DataWrap dw)  
  18.     {  
  19.         return   this .data > dw.data ?  1    
  20.             : (this .data == dw.data ?  0  : - 1 );  
  21.     }  
  22. }  
  23. public   class  BubbleSort  
  24. {  
  25.     public   static   void  bubbleSort(DataWrap[] data)   
  26.     {  
  27.         System.out.println("开始排序" );  
  28.         int  arrayLength = data.length;  
  29.         //依次进行n－1趟比较, 第i趟把第i大的值选出放在arrayLength-1-i位置上。   
  30.         for  ( int  i =  0 ; i < arrayLength -  1  ; i++ )  
  31.         {  
  32.             boolean  flag =  false ;  
  33.             for  ( int  j =  0 ; j < arrayLength -  1  - i ; j++ )  
  34.             {  
  35.                 //如果j索引处的元素大于j+1索引处的元素   
  36.                 if  (data[j].compareTo(data[j +  1 ]) >  0 )  
  37.                 {  
  38.                     //交换它们   
  39.                     DataWrap tmp = data[j + 1 ];  
  40.                     data[j + 1 ] = data[j];  
  41.                     data[j] = tmp;  
  42.                     flag = true ;  
  43.                 }  
  44.             }  
  45.             System.out.println(java.util.Arrays.toString(data));  
  46.             //如果某趟没有发生交换，则表明已处于有序状态   
  47.             if  (!flag)  
  48.             {  
  49.                 break ;  
  50.             }  
  51.         }  
  52.     }  
  53.     public   static   void  main(String[] args)  
  54.     {  
  55.         DataWrap[] data = {  
  56.             new  DataWrap( 9  ,  "" ),  
  57.             new  DataWrap( 16  ,  "" ),  
  58.             new  DataWrap( 21  ,  "*" ),  
  59.             new  DataWrap( 23  ,  "" ),  
  60.             new  DataWrap( 30  ,  "" ),  
  61.             new  DataWrap( 49  ,  "" ),  
  62.             new  DataWrap( 21  ,  "" ),  
  63.             new  DataWrap( 30  ,  "*" )  
  64.         };  
  65.         System.out.println("排序之前：\n"   
  66.             + java.util.Arrays.toString(data));  
  67.         bubbleSort(data);  
  68.         System.out.println("排序之后：\n"    
  69.             + java.util.Arrays.toString(data));  
  70.     }  
  71. }  
  72. //时间复杂度：   
  73. //空间复杂度：1   
  74. //稳定性：稳定   

快速排序

用到了递归。注意分界值是和 j交换来建立从小到大的排序。

Java代码  收藏代码
  1. import  java.util.*;  
  2. //定义一个数据包装类   
  3. class  DataWrap  implements  Comparable<DataWrap>  
  4. {  
  5.     int  data;  
  6.     String flag;  
  7.     public  DataWrap( int  data, String flag)  
  8.     {  
  9.         this .data = data;  
  10.         this .flag = flag;  
  11.     }  
  12.     public  String toString()  
  13.     {  
  14.         return  data + flag;  
  15.     }  
  16.     //根据data实例变量来决定两个DataWrap的大小   
  17.     public   int  compareTo(DataWrap dw)  
  18.     {  
  19.         return   this .data > dw.data ?  1    
  20.             : (this .data == dw.data ?  0  : - 1 );  
  21.     }  
  22. }  
  23. public   class  QuickSort  
  24. {  
  25.     //将指定数组的i和j索引处的元素交换   
  26.     private   static   void  swap(DataWrap[] data,  int  i,  int  j)  
  27.     {  
  28.         DataWrap tmp;  
  29.         tmp = data[i];  
  30.         data[i] = data[j];  
  31.         data[j] = tmp;  
  32.     }  
  33.     //对data数组中从start～end索引范围的子序列进行处理   
  34.     //使之满足所有小于分界值的放在左边，所有大于分界值的放在右边   
  35.     private   static   void  subSort(DataWrap[] data  
  36.         , int  start ,  int  end)  
  37.     {  
  38.         //需要排序   
  39.         if  (start < end)  
  40.         {  
  41.             //以第一个元素作为分界值   
  42.             DataWrap base = data[start];  
  43.             //i从左边搜索，搜索大于分界值的元素的索引   
  44.             int  i = start;  
  45.             //j从右边开始搜索，搜索小于分界值的元素的索引   
  46.             int  j = end +  1 ;  
  47.             while ( true )  
  48.             {  
  49.                 //找到大于分界值的元素的索引，或i已经到了end处   
  50.                 while (i < end && data[++i].compareTo(base) <=  0 );  
  51.                 //找到小于分界值的元素的索引，或j已经到了start处   
  52.                 while (j > start && data[--j].compareTo(base) >=  0 );  
  53.                 if  (i < j)  
  54.                 {  
  55.                     swap(data , i , j);  
  56.                 }  
  57.                 else   
  58.                 {  
  59.                     break ;  
  60.                 }  
  61.             }  
  62.             swap(data , start , j);  
  63.             //递归左子序列   
  64.             subSort(data , start , j - 1 );  
  65.             //递归右边子序列   
  66.             subSort(data , j + 1 , end);  
  67.         }  
  68.     }  
  69.     public   static   void  quickSort(DataWrap[] data)   
  70.     {  
  71.         subSort(data , 0  , data.length -  1 );  
  72.     }  
  73.     public   static   void  main(String[] args)  
  74.     {  
  75.         DataWrap[] data = {  
  76.             new  DataWrap( 9  ,  "" ),  
  77.             new  DataWrap(- 16  ,  "" ),  
  78.             new  DataWrap( 21  ,  "*" ),  
  79.             new  DataWrap( 23  ,  "" ),  
  80.             new  DataWrap(- 30  ,  "" ),  
  81.             new  DataWrap(- 49  ,  "" ),  
  82.             new  DataWrap( 21  ,  "" ),  
  83.             new  DataWrap( 30  ,  "*" ),  
  84.             new  DataWrap( 13  ,  "*" )  
  85.         };  
  86.         System.out.println("排序之前：\n"   
  87.             + java.util.Arrays.toString(data));  
  88.         quickSort(data);  
  89.         System.out.println("排序之后：\n"    
  90.             + java.util.Arrays.toString(data));  
  91.     }  
  92. }  
  93. //时间复杂度：n的平方   
  94. //空间复杂度：1   
  95. //稳定性：稳定   

直接插入排序

Java代码  收藏代码
  1. import  java.util.*;  
  2. //定义一个数据包装类   
  3. class  DataWrap  implements  Comparable<DataWrap>  
  4. {  
  5.     int  data;  
  6.     String flag;  
  7.     public  DataWrap( int  data, String flag)  
  8.     {  
  9.         this .data = data;  
  10.         this .flag = flag;  
  11.     }  
  12.     public  String toString()  
  13.     {  
  14.         return  data + flag;  
  15.     }  
  16.     //根据data实例变量来决定两个DataWrap的大小   
  17.     public   int  compareTo(DataWrap dw)  
  18.     {  
  19.         return   this .data > dw.data ?  1    
  20.             : (this .data == dw.data ?  0  : - 1 );  
  21.     }  
  22. }  
  23. public   class  InsertSort  
  24. {  
  25.     public   static   void  insertSort(DataWrap[] data)   
  26.     {  
  27.         System.out.println("直接插入排序\n开始排序：\n" );  
  28.         int  arrayLength = data.length;  
  29.         for  ( int  i =  1  ; i < arrayLength ; i++ )  
  30.         {  
  31.             //当整体后移时，保证data[i]的值不会丢失   
  32.             DataWrap tmp = data[i];  
  33.             //i索引处的值已经比前面所有值都大，表明已经有序，无需插入   
  34.             //（i-1索引之前的数据已经有序的，i-1索引处元素的值就是最大值）   
  35.             if  (data[i].compareTo(data[i -  1 ]) <  0 )  
  36.             {  
  37.                 int  j = i -  1 ;  
  38.                 //整体后移一格   
  39.                 for  ( ; j >=  0  && data[j].compareTo(tmp) >  0  ; j--)  
  40.                 {  
  41.                     data[j + 1 ] = data[j];  
  42.                 }  
  43.                 //最后将tmp的值插入合适位置   
  44.                 data[j + 1 ] = tmp;  
  45.             }  
  46.             System.out.println(java.util.Arrays.toString(data));  
  47.         }  
  48.     }  
  49.     public   static   void  main(String[] args)  
  50.     {  
  51.         DataWrap[] data = {  
  52.             new  DataWrap( 9  ,  "" ),  
  53.             new  DataWrap(- 16  ,  "" ),  
  54.             new  DataWrap( 21  ,  "*" ),  
  55.             new  DataWrap( 23  ,  "" ),  
  56.             new  DataWrap(- 30  ,  "" ),  
  57.             new  DataWrap(- 49  ,  "" ),  
  58.             new  DataWrap( 21  ,  "" ),  
  59.             new  DataWrap( 30  ,  "*" ),  
  60.             new  DataWrap( 30  ,  "" )  
  61.         };  
  62.         System.out.println("排序之前：\n"   
  63.             + java.util.Arrays.toString(data));  
  64.         insertSort(data);  
  65.         System.out.println("排序之后：\n"    
  66.             + java.util.Arrays.toString(data));  
  67.     }  
  68. }  

折半插入排序

Java代码  收藏代码
  1. import  java.util.*;  
  2. //定义一个数据包装类   
  3. class  DataWrap  implements  Comparable<DataWrap>  
  4. {  
  5.     int  data;  
  6.     String flag;  
  7.     public  DataWrap( int  data, String flag)  
  8.     {  
  9.         this .data = data;  
  10.         this .flag = flag;  
  11.     }  
  12.     public  String toString()  
  13.     {  
  14.         return  data + flag;  
  15.     }  
  16.     //根据data实例变量来决定两个DataWrap的大小   
  17.     public   int  compareTo(DataWrap dw)  
  18.     {  
  19.         return   this .data > dw.data ?  1    
  20.             : (this .data == dw.data ?  0  : - 1 );  
  21.     }  
  22. }  
  23. public   class  BinaryInsertSort  
  24. {  
  25.     public   static   void  binaryInsertSort(DataWrap[] data)  
  26.     {  
  27.         System.out.println("开始排序：\n" );  
  28.         int  arrayLength = data.length;  
  29.         for ( int  i =  1  ; i < arrayLength ; i++)  
  30.         {  
  31.             //当整体后移时，保证data[i]的值不会丢失   
  32.             DataWrap tmp = data[i];  
  33.             int  low =  0 ;  
  34.             int  high = i -  1 ;  
  35.             while (low <= high)  
  36.             {  
  37.                 //找出low、high中间的索引   
  38.                 int  mid = (low + high) /  2 ;  
  39.                 //如果tmp值大于low、high中间元素的值   
  40.                 if (tmp.compareTo(data[mid]) >  0 )  
  41.                 {  
  42.                     //限制在索引大于mid的那一半中搜索   
  43.                     low = mid + 1 ;  
  44.                 }   
  45.                 else   
  46.                 {  
  47.                     //限制在索引小于mid的那一半中搜索   
  48.                     high = mid - 1 ;  
  49.                 }  
  50.             }  
  51.             //将low到i处的所有元素向后整体移一位   
  52.             for ( int  j = i ; j > low ; j--)  
  53.             {  
  54.                 data[j] = data[j - 1 ];  
  55.             }  
  56.             //最后将tmp的值插入合适位置   
  57.             data[low] = tmp;  
  58.             System.out.println(java.util.Arrays.toString(data));  
  59.         }  
  60.     }  
  61.     public   static   void  main(String[] args)  
  62.     {  
  63.         DataWrap[] data = {  
  64.             new  DataWrap( 9  ,  "" ),  
  65.             new  DataWrap(- 16  ,  "" ),  
  66.             new  DataWrap( 21  ,  "*" ),  
  67.             new  DataWrap( 23  ,  "" ),  
  68.             new  DataWrap(- 30  ,  "" ),  
  69.             new  DataWrap(- 49  ,  "" ),  
  70.             new  DataWrap( 21  ,  "" ),  
  71.             new  DataWrap( 30  ,  "*" ),  
  72.             new  DataWrap( 30  ,  "" )  
  73.         };  
  74.         System.out.println("排序之前：\n"   
  75.             + java.util.Arrays.toString(data));  
  76.         binaryInsertSort(data);  
  77.         System.out.println("排序之后：\n"    
  78.             + java.util.Arrays.toString(data));  
  79.     }  
  80. }  

Shell排序

在进行排序时的数据项之间的间隔被称为增量，习惯上用h 表示。 h 序列从 1 开始，通过 h=3*h+1 计算产生（其实直接插入排序是 Shell 排序的一种特例：直接使用增量为 1 的 Shell

排序。）

Java代码  收藏代码
  1. import  java.util.*;  
  2. //定义一个数据包装类   
  3. class  DataWrap  implements  Comparable<DataWrap>  
  4. {  
  5.     int  data;  
  6.     String flag;  
  7.     public  DataWrap( int  data, String flag)  
  8.     {  
  9.         this .data = data;  
  10.         this .flag = flag;  
  11.     }  
  12.     public  String toString()  
  13.     {  
  14.         return  data + flag;  
  15.     }  
  16.     //根据data实例变量来决定两个DataWrap的大小   
  17.     public   int  compareTo(DataWrap dw)  
  18.     {  
  19.         return   this .data > dw.data ?  1    
  20.             : (this .data == dw.data ?  0  : - 1 );  
  21.     }  
  22. }  
  23. public   class  ShellSort  
  24. {  
  25.     public   static   void  shellSort(DataWrap[] data)   
  26.     {  
  27.         System.out.println("Shell\n开始排序：" );  
  28.         int  arrayLength = data.length;  
  29.         //h变量保存可变增量   
  30.         int  h =  1 ;  
  31.         //按h * 3 + 1得到增量序列的最大值   
  32.         while (h <= arrayLength /  3 )  
  33.         {  
  34.             h = h * 3  +  1 ;  
  35.         }  
  36.         while (h >  0 )  
  37.         {  
  38.             System.out.println("===h的值:"  + h +  "===" );  
  39.             for  ( int  i = h ; i < arrayLength ; i++ )  
  40.             {  
  41.                 //当整体后移时，保证data[i]的值不会丢失   
  42.                 DataWrap tmp = data[i];  
  43.                 //i索引处的值已经比前面所有值都大，表明已经有序，无需插入   
  44.                 //（i-1索引之前的数据已经有序的，i-1索引处元素的值就是最大值）   
  45.                 if  (data[i].compareTo(data[i - h]) <  0 )  
  46.                 {  
  47.                     int  j = i - h;  
  48.                     //整体后移h格   
  49.                     for  ( ; j >=  0  && data[j].compareTo(tmp) >  0  ; j-=h)  
  50.                     {  
  51.                         data[j + h] = data[j];  
  52.                     }  
  53.                     //最后将tmp的值插入合适位置   
  54.                     data[j + h] = tmp;  
  55.                 }  
  56.                 System.out.println(java.util.Arrays.toString(data));  
  57.             }  
  58.             h = (h - 1 ) /  3 ;  
  59.         }  
  60.     }  
  61.     public   static   void  main(String[] args)  
  62.     {  
  63.         DataWrap[] data = {  
  64.             new  DataWrap( 9  ,  "" ),  
  65.             new  DataWrap(- 16  ,  "" ),  
  66.             new  DataWrap( 21  ,  "*" ),  
  67.             new  DataWrap( 23  ,  "" ),  
  68.             new  DataWrap(- 30  ,  "" ),  
  69.             new  DataWrap(- 49  ,  "" ),  
  70.             new  DataWrap( 21  ,  "" ),  
  71.             new  DataWrap( 30  ,  "*" ),  
  72.             new  DataWrap( 30  ,  "" ),  
  73.         };  
  74.         System.out.println("排序之前：\n"   
  75.             + java.util.Arrays.toString(data));  
  76.         shellSort(data);  
  77.         System.out.println("排序之后：\n"    
  78.             + java.util.Arrays.toString(data));  
  79.     }  
  80. }  
  81. //时间复杂度：   
  82. //空间复杂度：1   
  83. //稳定性：稳定   

归并排序

他是将两个有序的数据序列合并成一个新的有序序列。

 

Java代码  收藏代码
  1. class  DataWrap  implements  Comparable<DataWrap>  
  2. {  
  3.     int  data;  
  4.     String flag;  
  5.     public  DataWrap( int  data, String flag)  
  6.     {  
  7.         this .data = data;  
  8.         this .flag = flag;  
  9.     }  
  10.     public  String toString()  
  11.     {  
  12.         return  data + flag;  
  13.     }  
  14.     //根据data实例变量来决定两个DataWrap的大小   
  15.     public   int  compareTo(DataWrap dw)  
  16.     {  
  17.         return   this .data > dw.data ?  1    
  18.             : (this .data == dw.data ?  0  : - 1 );  
  19.     }  
  20. }  
  21. public   class  MergeSort   
  22. {  
  23.     //利用归并排序算法对数组data进行排序    
  24.     public   static   void  mergeSort(DataWrap[] data)   
  25.     {  
  26.         //归并排序    
  27.         sort(data , 0  , data.length -  1 );  
  28.     }  
  29.     /**   
  30.      * 将索引从left到right范围的数组元素进行归并排序   
  31.      * @param data 待排序的数组  
  32.      * @param left 待排序的数组的第一个元素索引   
  33.      * @param right 待排序的数组的最后一个元素的索引   
  34.      */    
  35.     private   static   void  sort(DataWrap[] data  
  36.          , int  left,  int  right)   
  37.     {   
  38.         if  (left < right)   
  39.         {  
  40.             //找出中间索引   
  41.             int  center = (left + right) /  2 ;  
  42.             //对左边数组进行递归   
  43.             sort(data, left, center);   
  44.             //对右边数组进行递归   
  45.             sort(data, center + 1 , right);   
  46.             //合并   
  47.             merge(data, left, center, right);   
  48.         }   
  49.     }   
  50.     /**   
  51.      * 将两个数组进行归并，归并前两个数组已经有序，归并后依然有序。   
  52.      * @param data 数组对象   
  53.      * @param left 左数组的第一个元素的索引   
  54.      * @param center 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引  
  55.      * @param right 右数组的最后一个元素的索引   
  56.      */    
  57.     private   static   void  merge(DataWrap[] data  
  58.         , int  left,  int  center,  int  right)   
  59.     {  
  60.         //定义一个与待排序序列长度相同的临时数组    
  61.         DataWrap[] tmpArr = new  DataWrap[data.length];  
  62.         int  mid = center +  1 ;  
  63.         //third记录中间数组的索引   
  64.         int  third = left;   
  65.         int  tmp = left;   
  66.         while  (left <= center && mid <= right)   
  67.         {   
  68.             //从两个数组中取出小的放入中间数组    
  69.             if  (data[left].compareTo(data[mid]) <=  0 )   
  70.             {   
  71.                 tmpArr[third++] = data[left++];   
  72.             }   
  73.             else   
  74.             {  
  75.                 tmpArr[third++] = data[mid++];   
  76.             }  
  77.         }   
  78.         //剩余部分依次放入中间数组    
  79.         while  (mid <= right)   
  80.         {   
  81.             tmpArr[third++] = data[mid++];   
  82.         }   
  83.         while  (left <= center)   
  84.         {   
  85.             tmpArr[third++] = data[left++];   
  86.         }   
  87.         //将中间数组中的内容复制拷回原数组   
  88.         //(原left～right范围的内容复制回原数组)    
  89.         while  (tmp <= right)  
  90.         {  
  91.             data[tmp] = tmpArr[tmp++];   
  92.         }  
  93.     }   
  94.     public   static   void  main(String[] args)  
  95.     {  
  96.         DataWrap[] data = {  
  97.             new  DataWrap( 9  ,  "" ),  
  98.             new  DataWrap(- 16  ,  "" ),  
  99.             new  DataWrap( 21  ,  "*" ),  
  100.             new  DataWrap( 23  ,  "" ),  
  101.             new  DataWrap(- 30  ,  "" ),  
  102.             new  DataWrap(- 49  ,  "" ),  
  103.             new  DataWrap( 21  ,  "" ),  
  104.             new  DataWrap( 30  ,  "*" ),  
  105.             new  DataWrap( 30  ,  "" )  
  106.         };  
  107.         System.out.println("排序之前：\n"   
  108.             + java.util.Arrays.toString(data));  
  109.         mergeSort(data);  
  110.         System.out.println("排序之后：\n"    
  111.             + java.util.Arrays.toString(data));  
  112.     }  
  113. }  
  114. //时间复杂度：   
  115. //空间复杂度：   
  116. //稳定性：稳定   
桶式排序

桶式排序的特征：

待排序列的所有值处于一个可枚举范围内；

待排序列所在的这个可枚举范围不应该太大，否则排序开销太大。

Java代码  收藏代码
  1. import  java.util.Arrays;  
  2. class  DataWrap  implements  Comparable<DataWrap>  
  3. {  
  4.     int  data;  
  5.     String flag;  
  6.     public  DataWrap( int  data, String flag)  
  7.     {  
  8.         this .data = data;  
  9.         this .flag = flag;  
  10.     }  
  11.     public  String toString()  
  12.     {  
  13.         return  data + flag;  
  14.     }  
  15.     //根据data实例变量来决定两个DataWrap的大小   
  16.     public   int  compareTo(DataWrap dw)  
  17.     {  
  18.         return   this .data > dw.data ?  1    
  19.             : (this .data == dw.data ?  0  : - 1 );  
  20.     }  
  21. }  
  22. public   class  BucketSort  
  23. {  
  24.     public   static   void  bucketSort(DataWrap[] data   
  25.         , int  min ,  int  max)  
  26.     {  
  27.         System.out.println("开始排序：" );  
  28.         //arrayLength记录待排序数组的长度   
  29.         int  arrayLength = data.length;  
  30.         DataWrap[] tmp = new  DataWrap[arrayLength];  
  31.         //buckets数组相当于定义了max - min个桶，   
  32.         //buckets数组用于记录待排序元素的信息   
  33.         int [] buckets =  new   int [max - min];   
  34.         //计算每个元素在序列出现的次数   
  35.         for ( int  i =  0  ; i < arrayLength ; i++)  
  36.         {  
  37.             //buckets数组记录了DataWrap出现的次数   
  38.             buckets[data[i].data - min]++;  
  39.         }  
  40.         System.out.println( Arrays.toString(buckets));  
  41.         //计算“落入”各桶内的元素在有序序列中的位置   
  42.         for ( int  i =  1  ; i < max - min; i++)  
  43.         {  
  44.             //前一个bucket的值 + 当前bucket的值 -> 当前bucket新的值   
  45.             buckets[i] = buckets[i] + buckets[i - 1 ];  
  46.         }  
  47.         //循环结束后，buckets数组元素记录了“落入”前面所有桶和    
  48.         //“落入”当前bucket中元素的总数，   
  49.         //也就说：buckets数组元素的值代表了“落入”当前桶的元素在有序序列中的位置   
  50.         System.out.println( Arrays.toString(buckets));  
  51.         //将data数组中数据完全复制到tmp数组中缓存起来。   
  52.         System.arraycopy(data, 0 , tmp,  0 , arrayLength);  
  53.         //根据buckets数组中的信息将待排序列的各元素放入相应的位置。   
  54.         for ( int  k = arrayLength -  1  ; k >=   0  ; k--) //从高位开始可以保证排序的稳定性   
  55.         {  
  56.             data[--buckets[tmp[k].data - min]] = tmp[k];  
  57.         }  
  58.     }  
  59.     public   static   void  main(String[] args)  
  60.     {  
  61.         DataWrap[] data = {  
  62.             new  DataWrap( 9  ,  "" ),  
  63.             new  DataWrap( 5 ,  "" ),  
  64.             new  DataWrap(- 1 ,  "" ),  
  65.             new  DataWrap( 8  ,  "" ),  
  66.             new  DataWrap( 5  ,  "*" ),  
  67.             new  DataWrap( 7  ,  "" ),  
  68.             new  DataWrap( 3  ,  "" ),  
  69.             new  DataWrap(- 3 ,  "" ),  
  70.             new  DataWrap( 1  ,  "" ),  
  71.             new  DataWrap( 3  ,  "*" )  
  72.         };  
  73.         System.out.println("排序之前：\n"   
  74.             + java.util.Arrays.toString(data));  
  75.         bucketSort(data , -3  ,  10 );  
  76.         System.out.println("排序之后：\n"    
  77.             + java.util.Arrays.toString(data));  
  78.     }  
  79. }  
  80. //时间复杂度：小   
  81. //空间复杂度：大   
  82. //稳定性：稳定   
 基数排序

基数排序必须依赖于另外的排序方法。基数排序的总体思想就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。

多关键字排序解决方案：

最高位优先法MSD ；

最低位优先法LSD 。

基数排序对任一子关键字排序时必须借助于另外一个排序方法，而且这种排序方法必须是稳定的，一般用通式排序。

Java代码  收藏代码
  1. import  java.util.Arrays;  
  2. public   class  MultiKeyRadixSort  
  3. {     
  4.     /**  
  5.      * @param data 待排序的数组     
  6.      * @param radix  指定关键字拆分的进制。如radix=10，表明按10进制拆分  
  7.      * @param d 指定将关键字拆分成几个子关键字  
  8.      */   
  9.     public   static   void  radixSort( int [] data,  int  radix,  int  d)   
  10.     {  
  11.         System.out.println("开始排序：" );  
  12.         int  arrayLength = data.length;  
  13.         //需要一个临时数组   
  14.         int [] tmp =  new   int [arrayLength];  
  15.         //buckets数组是桶式排序必须buckets数组   
  16.         int [] buckets =  new   int [radix];  
  17.         //依次从最高位的子关键字对待排数据进行排序   
  18.         //下面循环中rate用于保存当前计算的位（比如十位时rate=10）   
  19.         for ( int  i =  0  , rate =  1  ; i < d ; i++)  
  20.         {  
  21.             //重置count数组，开始统计第二个关键字   
  22.             Arrays.fill(buckets, 0 );  
  23.             //将data数组的元素复制到temporary数组中进行缓存   
  24.             System.arraycopy(data, 0 , tmp,  0 , arrayLength);  
  25.             //计算每个待排序数据的子关键字   
  26.             for ( int  j =  0  ; j < arrayLength ; j++)  
  27.             {  
  28.                 //计算数据指定位上的子关键字   
  29.                 int  subKey = (tmp[j] / rate) % radix;  
  30.                 buckets[subKey]++;  
  31.             }  
  32.             for ( int  j =  1  ; j < radix ; j++)  
  33.             {  
  34.                 buckets[j] = buckets[j] + buckets[j-1 ];  
  35.             }  
  36.             //按子关键字对指定数据进行排序   
  37.             for ( int  m = arrayLength -  1  ; m >=  0  ; m--)  
  38.             {  
  39.                 int  subKey = (tmp[m] / rate) % radix;  
  40.                 data[--buckets[subKey]] = tmp[m];  
  41.             }  
  42.             System.out.println("对"  + rate +  "位上子关键字排序："    
  43.                 + java.util.Arrays.toString(data));  
  44.             rate *= radix;  
  45.         }  
  46.     }  
  47.     public   static   void  main(String[] args)  
  48.     {  
  49.         int [] data = { 1100  ,  192  ,  221  ,  12  ,  13 };  
  50.         System.out.println("排序之前：\n"   
  51.             + java.util.Arrays.toString(data));  
  52.         radixSort(data , 10  ,  4 );  
  53.         System.out.println("排序之后：\n"    
  54.             + java.util.Arrays.toString(data));  
  55.     }  
  56. }  
 

 

分享到：
| 面试需要准备到的几个点
评论
发表评论

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

相关推荐

    Leetcode 搜索旋转排序数组.m

    LeetCode 问题 33 是一个关于在旋转排序数组中搜索一个给定目标值的问题。如果目标值存在返回它的索引，否则返回 -1。数组可能在某个未知的轴心上进行了旋转（例如 [0,1,2,4,5,6,7] 可能变成 [4,5,6,7,0,1,2]）。你...

    ACM 内部预定函数

    5.射向法判断点是否在多边形内部 6.判断点是否在线段上 7.判断两线段是否相交 8.判断线段与直线是否相交 9.点到线段最短距离 10.求两直线的交点 11.判断一个封闭图形是凹集还是凸集 12.Graham扫描法寻找凸包 13.求两...

    计算机专业数据结构设计课件

    计算机专业所需，C语言编写，富含例题一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.... 3....二、栈、队列和数组 （一）栈和队列的基本概念 ...（十一）内部排序算法的应用

    lua-tuple:Lua 元组。 Lua 的可变和内部元组表。 元组可以按字典顺序排序并默认连接

    元组可以按字典顺序排序并默认连接。 安装 将文件tuple.lua复制到 LUA_PATH。 用 Lua-Tuple 允许在 Lua 中声明 in-mutable 和 interned tuples。 由于内部化，元组的创建是一项耗时的操作，但是，由于这一点，它们...

    公共交通方式转移价格的排序选择模型 (2011年)

    基于排序选择模型，分别建立了基于排序Probit和排序Logil的公共交通内部方式转移价格阈值模型，并对模型进行局部效应分析.结果表明：性别、职业、收入、公交出行时间、公交出行费用及地铁与公交出行时间比对公共交通...

    Java基础知识点.html

    Date类 自动拆箱和自动装箱 Arrays 类和接口的关系 内部类 成员内部类 局部内部类 匿名内部类 抽象类 接口 多态 封装 类和对象 方法 StringBuilder类 String类 static for循环 final 权限修饰符 跳转控制语句 while...

    java培训机构内部预习文档

    数组 一维数组、数组参数、数组返回值、数组增删、扩容、排序、二维数组 chp6.面向对象 类和对象、实例变量、构造方法、方法重载、引用的概念、this关键字 chp7.面向对象三大特性 封装、继承、多态、对象创建过程、...

    数据结构(C语言版）

    10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换一选择排序 11.5 最佳归并树 第12章 文件 12.1 有关文件的基本概念 12.2 顺序文件 ...

    数据结构 c语言版

    10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换一选择排序 11.5 最佳归并树 第12章 文件 12.1 有关文件的基本概念 12.2 ...

    mv-sorter：使内容可排序的自定义元素

    允许在项目周围和内部选择文本 处理不同大小的元素 支持在页面上任何位置放置元素，找到最接近的可用放置区域 处理拖放区的可见性变化 可选的拖动手柄 支持多个和嵌套的可排序容器 每个容器可配置的放置区。 调度...

    文本批量转码UTF8

    软件说明： 编写语言：JAVA 运行环境：XP 或 WIN7, JRE1.6 含以及以上版本 作为一个初级程序猿来说：最苦恼的莫过于“兴冲冲得搞到了一批感兴趣的代码”，结果...“各种内部排序代码实现.rar”文件样本，供转换参考；

    智能归并排序

    文中详细介绍并分析了归并排序算法的优缺点，针对归并算法的强制把数据划分两份进行了改进，提出按照数据本身具有的规律进行智能归并排序划分的方法。该方法将局部有序的记录块作为一组，避免对已经有序的数据划分再...

    《数据结构》（C语言版）严蔚敏

    10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换一选择排序 11.5 最佳归并树 第12章 文件 12.1 有关文件的基本概念 12.2 顺序文件 ...

    数据结构(C语言版)[严蔚敏]

    10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换一选择排序 11.5 最佳归并树 第12章 文件 12.1 有关文件的基本概念 12.2 顺序文件 ...

    数据结构讲义(严蔚敏版)(含算法源码)

    9. 内部排序 直接插入排序（A） 折半插入排序（A，P） 希尔排序（A） 起泡排序（A） 快速排序（A，P，O） 简单选择排序（P，A，O） 堆的概念，调整成堆（A），堆排序（A，O） 归并排序（A，O） 链式基数排序（A，O）...

    严蔚敏：数据结构题集(C语言版)

    10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换-选择排序 11.5 最佳归并树 第12章 文件 12.1 有关文件的基本概念 12.2 顺序文件...

    [数据结构(C语言版)].严蔚敏_吴伟民.高清扫描版.rar

    10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换一选择排序 11.5 最佳归并树 第12章 文件 12.1 有关文件的基本概念 12.2 顺序文件 ...

    oracle公司内部的培训资料

    Les02 : 过滤和排序数据[where / order by] Les03 : 单行函数[字符/数值/日期/转换/通用] Les04 : 多表查询 Les05 : 分组函数 Les06 : 子查询 Les07 : iSQL*Plus Les08 : 处理数据[DML:UPDATE/INSERT INTO/DELETE ...

    Javaw基础课程笔记.zip

    Java 视频教程目录： day01、Java 语言发展史_JDK的安装_HelloWorld程序的编写_关键字_标识符_基本数据类型。 day02、Java 数据类型转换_...day11：Java final 关键字_内部类_成员内部类_局部内部类_匿名内部类。

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