`
samsongbest
  • 浏览: 172675 次
  • 性别: 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. }  
 

 

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

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

相关推荐

    C语言数据结构内部排序算法及比较

    本文将深入探讨“C语言数据结构内部排序算法及比较”这一主题，结合个人课程作业的经验，对一些核心概念进行阐述，并对常见的内部排序算法进行比较。 首先，数据结构是组织和管理数据的方式，它包括数组、链表、树...

    【排序结构5】 基于比较的内部排序总结

    【排序结构5】基于比较的内部排序总结 在计算机科学中，排序是将一组数据按照特定顺序排列的过程。内部排序，或称为内存排序，是指数据记录在内存中进行的排序，与外部排序（数据量太大无法全部装入内存）相对。本...

    常用的排序算法总结（各种内部排序算法和外部排序算法）

    本文将对几种常见的内部排序算法和外部排序算法进行详细总结。 首先，排序的基本定义是：给定一个包含n个记录的序列，其关键字序列分别为K1, K2, ..., Kn，如果存在一个排列p1, p2, p3, ..., pn，使得关键字满足非...

    内部排序算法比较、哈希表设计

    内部排序指的是数据在内存中进行的排序过程，常见的内部排序算法有以下几种： 1. **冒泡排序**：是最简单的排序方法，通过多次遍历数组，每次比较相邻元素并交换位置来实现排序。虽然效率较低，但易于理解和实现。 ...

    内部排序，主要是内部排序的讲解，课件

    内部排序是计算机科学中一种重要的数据处理方法，它是指数据记录在计算机内存中进行排序的过程。这个主题主要涵盖了多种不同的排序算法，每种都有其独特的特性和适用场景。以下是关于这些排序算法的详细讲解： 1. *...

    数据结构课件：第10章 内部排序.ppt

    【内部排序】是计算机科学中数据处理的重要环节，它的目标是将无序的数据序列转换为有序的序列。在计算机内存中直接完成的排序过程被称为内部排序，与之相对的是外部排序，后者通常处理的数据量巨大，无法一次性装入...

    内部排序算法

    **内部排序算法**是计算机科学中处理数据组织和管理的核心技术之一，特别是在数据结构课程中，它是不可或缺的一部分。本项目旨在深入理解并实践各种内部排序算法，通过编写源代码进行对比分析，帮助学习者掌握其原理...

    设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。

    设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 在本文中，我们将设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数，以取得直观感受。内部排序算法是指在内存中...

    数据结构 插入排序、快速排序、选择排序、选择排序

    在本文中，我们将深入探讨四种常见的内部排序方法：插入排序、快速排序、选择排序以及再次提到的选择排序。这四种排序方法在不同的场景下各有优劣，理解它们的工作原理和性能特性对于优化算法至关重要。 **1. 插入...

    第9章_内部排序.zip

    在计算机科学领域，内部排序是数据处理中一个关键的概念，特别是在大数据处理和信息管理中。这一章的主题聚焦于“内部排序”，即数据在内存中进行的排序过程，区别于外部排序，后者涉及到大到无法一次性装入内存的...

    数据结构内部排序答案PPT学习教案.pptx

    数据结构中的内部排序是指在排序过程中不依赖外部存储器，完全在内存中完成的排序方法。内部排序有多种实现方式，根据不同的策略和操作特点，可以分为不同的类别。以下是内部排序的一些主要知识点： 1. **排序定义*...

    数据结构-排序PPT课件.pptx

    本资源是关于数据结构中排序算法的PPT课件，全文共118页，详细介绍了排序的概念、内部排序和外部排序、内部排序方法的分类、插入排序、快速排序、堆排序、归并排序、基数排序等内容。 1. 排序的概念：排序是计算机...

    数据结构教学课件：第九讲 内部排序2.ppt

    数据结构教学课件的第九讲主要探讨了内部排序方法，特别是希尔排序和堆排序两种算法。内部排序是指数据在内存中进行的排序过程，对于大量数据处理至关重要。 首先，希尔排序（Shell Sort）是一种基于插入排序的算法...

    易语言excel多列排序

    易语言可以通过内部函数或自定义算法来实现这种转换。 6. **用户界面**：如果这是一个交互式的程序，那么还需要设计一个用户友好的界面，让用户可以选择要排序的列、排序顺序以及输入关键词等。 7. **错误处理**：...

    数据结构 排序算法的比较

    在上述课程设计中，通过生成随机数并使用四种基本排序算法（冒泡排序、选择排序、直接插入排序和快速排序）进行排序，然后记录每种算法的执行时间和比较次数，以直观地比较它们的效率。此外，程序还需要具有友好的...

    Verilog实现冒泡排序

    首先，我们定义了一个模块sort，其中包含了必要的输入输出端口、时钟信号（clk）、复位信号（reset）、内部标志位（int1）以及用于存储待排序数据的内存（memo），还包括了长度参数（length和weikuan）。 在Verilog...

    数据结构教程（第5版）课后题参考答案，第十章内排序

    本部分内容源自《数据结构教程（第5版）》课后题参考答案的第十章“内排序”，该章节主要讨论了各种内部排序算法的实现原理和性能分析，包括直接插入排序、希尔排序、折半插入排序、快速排序等，还涉及到了排序算法...

    数据结构-排序.ppt

    如果待排序记录都在内存中，整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；否则，称此类排序问题为外部排序。 内部排序的方法可以分为四种：插入类、交换类、选择类和归并类。插入类排序的基本...

    js排序表格，实现按列排序

    常见的排序算法如冒泡排序、插入排序或快速排序都可以应用在这里，但考虑到性能，更常见的是使用稳定且效率较高的排序算法，如归并排序或计数排序。 在排序过程中，需要注意以下几点： 1. 数据类型：表格中的数据...

    StringGrid部分行按列排序

    `SortGrid`函数内部调用了`QuickSort`函数实现快速排序算法。`QuickSort`函数接受一个整型数组`List`作为参数，这个数组包含了待排序的行号列表。此外还有最小值`min`、最大值`max`、排序列号`sortCol`、数据类型`...

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