A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 胡永城 高级黑马   /  2013-12-7 23:07  /  1162 人查看  /  3 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 胡永城 于 2017-2-21 21:32 编辑

【已重置】

3 个回复

倒序浏览
package Utils.Sort;

/**

*希尔排序,要求待排序的数组必须实现Comparable接口

*/

public class ShellSort implements SortStrategy

{

       private int[] increment;

       /**

       *利用希尔排序算法对数组obj进行排序

       */

       public void sort(Comparable[] obj)

       {

              if (obj == null)

              {

                     throw new NullPointerException("The argument can not be null!");

              }



              //初始化步长

              initGap(obj);

  

              //步长依次变化(递减)

              for (int i = increment.length - 1 ;i >= 0 ;i-- )

              {

                     int step = increment[i];                    

                     //由步长位置开始


                     for (int j = step ;j < obj.length ;j++ )

                     {

                            Comparable tmp;

                           

                            //如果后面的小于前面的(相隔step),则与前面的交换

                            for (int m = j ;m >= step ;m = m - step )

                            {

                                   if (obj[m].compareTo(obj[m - step]) < 0)

                                   {

                                          tmp = obj[m - step];

                                          obj[m - step] = obj[m];

                                          obj[m] = tmp;

                                   }

                                   //因为之前的位置必定已经比较过,所以这里直接退出循环

                                   else

                                   {

                                          break;

                                   }

                            }

                     }

              }

       }





       /**

       *根据数组的长度确定求增量的公式的最大指数,公式为pow(4, i) - 3 * pow(2, i)

+ 1和9 * pow(4, i) - 9 * pow(2, i) + 1

       *@return int[] 两个公式的最大指数

       *@param length 数组的长度

       */

       private int[] initExponent(int length)

       {

              int[] exp = new int[2];

              exp[0] = 1;

              exp[1] = -1;

              int[] gap = new int[2];

              gap[0] = gap[1] = 0;

              

              //确定两个公式的最大指数

              while (gap[0] < length)

              {

                     exp[0]++;

                     gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1);                     

              }

              exp[0]--;



              while (gap[1] < length)

              {

                     exp[1]++;

                     gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1);                       

              }

              exp[1]--;

              return exp;

       }



       private void initGap(Comparable[] obj)

       {

              //利用公式初始化增量序列

              int exp[] = initExponent(obj.length);

              int[] gap = new int[2];



               increment = new int[exp[0] + exp[1]];              













              //将增量数组由大到小赋值

              for (int i = exp[0] + exp[1] - 1 ;i >= 0 ;i-- )

              {

                     gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1);

                     gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1);



                     //将大的增量先放入增量数组,这里实际上是一个归并排序

                     //不需要考虑gap[0] == gap[1]的情况,因为不可能出现相等。

                     if (gap[0] > gap[1])

                     {

                            increment[i] = gap[0];

                            exp[0]--;

                     }

                     else

                     {

                            increment[i] = gap[1];

                            exp[1]--;

                     }

              }            

       }

}

评分

参与人数 2技术分 +1 黑马币 +6 收起 理由
狼王 + 1 + 3 赞一个!
胡永城 + 3 多谢,很不错。

查看全部评分

回复 使用道具 举报
本帖最后由 天下 于 2013-12-8 10:39 编辑

献丑了:


  1. /**希尔排序的原理:根据需求,如果你想要结果从大到小排列,它会首先将数组进行分组,然后将较大值移到前面,较小值
  2. * 移到后面,最后将整个数组进行插入排序,这样比起一开始就用插入排序减少了数据交换和移动的次数,可以说希尔排序是加强
  3. * 版的插入排序
  4. * 拿数组5, 2, 8, 9, 1, 3,4来说,数组长度为7,当increment为3时,数组分为两个序列
  5. * 5,2,8和9,1,3,4,第一次排序,9和5比较,1和2比较,3和8比较,4和比其下标值小increment的数组值相比较
  6. * 此例子是按照从大到小排列,所以大的会排在前面,第一次排序后数组为9, 2, 8, 5, 1, 3,4
  7. * 第一次后increment的值变为3/2=1,此时对数组进行插入排序,
  8. */  
  9. public class ShellSort {  
  10.     public static void shellSort(int[] arr) {  
  11.         int j = 0;  
  12.         int temp = 0;  
  13.         for (int increment = arr.length / 2; increment > 0; increment /= 2) {
  14.                
  15.             for (int i = increment; i < arr.length; i++) {  
  16.                 temp = arr[i];  
  17.                 for (j = i; j >= increment; j -= increment) {  
  18.                     if(temp > arr[j - increment]){  
  19.                             arr[j] = arr[j - increment];  
  20.                     }else{  
  21.                         break;  
  22.                     }  
  23.                 }   
  24.                 arr[j] = temp;  
  25.             }  
  26.         }  
  27.     }  
  28.   
  29.     public static void main(String[] args) {  
  30.         int[] arr = new int[] {5, 2, 8, 9, 1, 3,4};  
  31.         int[] arr1=new int[]{ 5, 2, 8, 6, 9, 7, 1, 3, 10, 4};
  32.         System.out.println("未排序前");  
  33.       
  34.         print(arr);
  35.         System.out.println();
  36.         print(arr1);
  37.            
  38.         shellSort(arr);
  39.         shellSort(arr1);  
  40.          
  41.         System.out.println("\n排序后");  
  42.         print(arr);
  43.         System.out.println();
  44.         print(arr1);
  45.         
  46.     }  
  47.     public static void print(int[] arr){
  48.             for(int i: arr){
  49.                     System.out.print(i+" ");
  50.             }
  51.     }
  52.   
  53. }  
  54. 打印结果:
  55. 未排序前
  56. 5 2 8 9 1 3 4
  57. 5 2 8 6 9 7 1 3 10 4
  58. 排序后
  59. 9 8 5 4 3 2 1
  60. 10 9 8 7 6 5 4 3 2 1
复制代码


评分

参与人数 2技术分 +1 黑马币 +6 收起 理由
狼王 + 1 + 3 很给力!
胡永城 + 3 多谢,不过代码间最好也有详细的注释.

查看全部评分

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马