北大青鸟北京，通州北大青鸟校区学术部：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] + "  ");  
            }  
        }  
 
    }

（北京北大青鸟校区）