北大青鳥北京，通州北大青鳥校區學術部：Java的排序之“希爾排序”

北京北大青鳥通州校區學術部老師講解：什么是希爾排序？

北京北大青鳥專家解答：希爾排序就是對插入排序的優化， 他是把一個待排序的數組分段成有規律的的若干個數組排序，最后在進行總排序來完成排序的目的，

基本思想：先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取第二個增量d2北大青鳥校區）

（1）將等間距的數組元素按升序排列（北京北大青鳥校區）
view plaincopy to clipboardprint?
private static void incrementalInsertionSort(int[] array, int first,  
                      int last, int space)  
    {  
        int unsorted, index;  
        for (unsorted = first + space; unsorted <= last; unsorted += space)  
        {  
            int firstUnsorted = array[unsorted];  
            for (index = unsorted - space; (index >= first)   
                  && (firstUnsorted < array[index]); index -= space)  
            {  
                array[index+space] = array[index];  
            }  
            array[index+space] = firstUnsorted;  
        }  
    } 
private static void incrementalInsertionSort(int[] array, int first,
             int last, int space)
 {
  int unsorted, index;
  for (unsorted = first + space; unsorted <= last; unsorted += space)
  {
   int firstUnsorted = array[unsorted];
   for (index = unsorted - space; (index >= first)
         && (firstUnsorted < array[index]); index -= space)
   {
    array[index+space] = array[index];
   }
   array[index+space] = firstUnsorted;
  }
 }
2）設定索引間距序列（北京北大青鳥校區）
view plaincopy to clipboardprint?
public static void shellSort(int[] array, int first, int last)  
    {  
        int n = last-first + 1;  
        for (int space = n / 2; space > 0; space /= 2)  
        {  
            for (int begin = first; begin < first + space; begin++)  
            {  
                incrementalInsertionSort(array, begin, last, space);  
            }  
        }  
    } 
public static void shellSort(int[] array, int first, int last)
 {
  int n = last-first + 1;
  for (int space = n / 2; space > 0; space /= 2)
  {
   for (int begin = first; begin < first + space; begin++)
   {
    incrementalInsertionSort(array, begin, last, space);
   }
  }
 }
3）測試（北京北大青鳥校區）
view plaincopy to clipboardprint?
public static void main(String[] args)  
    {  
        // TODO Auto-generated method stub  
        Random random = new Random();  
        final int size = 10;  
        int i;  
        int[] array = new int[size];  
        for (i = 0; i < size; i++)  
        {  
            array[i] = random.nextInt(1000);  
        }  
        System.out.println("排序前數組");  
        for (i = 0; i < size; i++)  
        {  
            if((i+1) % 20 == 0)  
            {  
                System.out.println();  
            }  
            else 
            {  
                System.out.print(array[i] + "  ");  
            }  
        }  
        shellSort(array,0,size-1);  
        System.out.println("\n排序后數組");  
        for (i = 0; i < size; i++)  
        {  
            if((i+1) % 20 == 0)  
            {  
                System.out.println();  
            }  
            else 
            {  
                System.out.print(array[i] + "  ");  
            }  
        }  
 
    }

（北京北大青鳥校區）