Go语言视频零基础入门到精通

javalearner

问题     有一数组，长度为n，把数组中的元素从小到大重新排列。  思路     希尔排序把n个元素按一定的间隔分成几组，然后按组为单位进行插入排序。     先将间隔设定为n/2，然后对每组进行插入排序，再来将间隔n/4，对每组进行插入 排序，再来将间隔设定为n/8、n/16，直到间隔为1，进行最后一次排序。     例如对10，-3，5，34，-34，5，0，9进行排序。     初始间隔为8/2 = 4。（10、-34），（-3、5），（5、0），（34，9）分别进行 插入排序。   图1、间隔为4      第二次间隔为4/2 = 2。（34，0，10，5），（-3，9，5，34）分别进行插入排 序。 图2、间隔为2      最后进行间隔为1的排序，但这次很幸运，已经完全不用执行移动操作了。 图3、间隔为1  说明     希尔排序是改良后的插入排序。希尔排序的原则是让后一次排序利用上一次排序的结 果，由于上一次的排序动作都会将固定间隔内的元素排序好，所以当间隔越来越小时，某些 元素位于正确位置的机率越高，因此最后几次的排序动作将可以大幅减低。     间隔设定为n/2并不能得到最佳的效率，有特殊的公式可求最佳的间隔，有兴趣的朋 友可在网上找到这方面的资料。     插入排序可见本人的另一篇文章经典算法之插入排序。 核心代码  
   
     
    static
     
    void
     sort(
    int
    [] array) {
         
    int
     l
    =
     array.length;
         
    int
     gap,i,j,tmp;
         
    //
    1.设定间隔
   

            
    for
    (gap
    =
     l
    /
    2
    ; gap
    >
     
    0
    ; gap
    /=
     
    2
    ) {
            
    //
    2.插入排序
   

               
    for
    (i
    =
     gap;i
    <
     l; i
    ++
    ) {
                 tmp
    =
     array;
                 
    for
    (j
    =
     i
    -
     gap; j
    >=
     
    0
    ; j
    -=
     gap) {
                     
    if
    (tmp
    <
     array[j]) {
                         array[j
    +
     gap]
    =
     array[j];
                     }
    else
     {
                        
    break
    ;
                     }
                 }
                 array[j
    +
     gap]
    =
     tmp;
             }
         }
     }
    全部代码  
   
   
   
    Code
   

      package com.icescut.classic.algorithm;

public class ShellSort {

     public static void main(String[] args) {
         int[] array = { 10, -3, 5, 34, -34, 5, 0, 9 }; // test data
         sort(array);
         for (int el : array) {
             System.out.print(el + " ");
         }
     }

     static void sort(int[] array) {
         int l = array.length;
         int gap,i,j,tmp;
         //1.设定间隔
         for(gap = l/2; gap > 0; gap /= 2) {
             //2.插入排序
             for(i = gap;i < l; i ++) {
                 tmp = array;
                 for(j = i - gap; j >= 0; j -= gap) {
                     if(tmp < array[j]) {
                         array[j + gap] = array[j];
                     } else {
                         break;
                     }
                 }
                 array[j + gap] = tmp;
             }
         }
     }
     
     //使用优化的间隔
     static void sortUseGaps(int[] array)         
     {
         int l = array.length;
         int i, j, k, temp, gap;
         int[] gaps = { 1,5,13,43,113,297,815,1989,4711,11969,27901,84801,
                    213331,543749,1355339,3501671,8810089,21521774,
                    58548857,157840433,410151271,1131376761,2147483647 };
         for (k = 0; gaps[k] < l; k++) ;
         while (--k >= 0)
         {
             gap = gaps[k];                  
             for (i = gap; i < l; i++)
             {
                 temp = array;
                 j = i;
                 while (j >= gap && array[j - gap] > temp)
                 {
                     array[j] = array[j - gap];
                     j = j - gap;
                 }
                 array[j] = temp;
             }
         }
     }

}

     
   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/11/000329359.zip