学步园

 

问题

    有一数组，长度为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[i];
                for(j = i - gap; j >= 0; j -= gap) {
                    if(tmp < array[j]) {
                        array[j + gap] = array[j];
                    } else {
                        break;
                    }
                }
                array[j + gap] = tmp;
            }
        }
    }

 

全部代码

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[i];
                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[i];
                j = i;
                while (j >= gap && array[j - gap] > temp)
                {
                    array[j] = array[j - gap];
                    j = j - gap;
                }
                array[j] = temp;
            }
        }
    }

}