数据结构——希尔排序原理及Java实现

 

    　希尔排序(Shell Sort)是插入排序的一种。因D．L．Shell于1959年提出而得名。

希尔排序基本思想

  基本思想：
　    先取一个小于n的整数d₁作为第一个增量，把文件的全部记录分成d₁个组。所有距离为d_l的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d₂1重复上述的分组和排序，直至所取的增量d_t=1(d_tt-l<…21)，即所有记录放在同一组中进行直接插入排序为止。
    　该方法实质上是一种分组插入方法。

时间复杂度（from O(N^3/2) down to O(N^7/6).）

shell排序的算法实现

  void ShellPass(SeqList R，int d)
   {//希尔排序中的一趟排序，d为当前增量
     for(i=d+1;i<=n；i++) //将R[d+1．．n]分别插入各组当前的有序区
       if(R[i].key         R[0]=R[i];j=i-d； //R[0]只是暂存单元，不是哨兵
         do {//查找R[i]的插入位置
            R[j+d]；=R[j]； //后移记录
            j=j-d； //查找前一记录
         }while(j>0&&R[0].key         R[j+d]=R[0]； //插入R[i]到正确的位置上
       } //endif
   } //ShellPass

  void  ShellSort(SeqList R)
   {
    int increment=n； //增量初值，不妨设n>0
    do {
          increment=increment/3+1； //求下一增量
          ShellPass(R，increment)； //一趟增量为increment的Shell插入排序
       }while(increment>1)
    } //ShellSort
  注意：
　    当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0"，以防下标越界。

 

 

 

源码:

 

package zieckey.datastructure.study.sort;

/**
 * 希尔排序
 * 演示地址：
 *
 * 基本思想： 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。
 * 所有距离为dl的倍数的记录放在同一个组中。
 * 先在各组内进行直接插人排序；然后，取第二个增量d2 * 直至所取的增量dt=1(dt * 该方法实质上是一种分组插入方法。
 *
 * @author zieckey
 * @version 2008/3/15
 */
public class ShellSort
{
    private int[]    intArray;            // 待排序的数组

    private int        nItems;                // 数组内元素个数

    private int        maxItems;            // 数组大小

    private int[]    intervalSequence;    // 增量数组序列


    // 构造函数

    public ShellSort( int maxItems, int[] intervalSequence )
    {
        this.intArray = new int[maxItems];
        this.maxItems = maxItems;
        this.nItems = 0;// 还没有元素

        this.intervalSequence = intervalSequence;
    }

    /**
     * 49 38 65 97 76 13 27 49 55 4
     *
     * 希尔排序算法，从小到大
     */
    public void shellSortMethod()
    {
        int h = 0;//为增量

        for ( int iIntervalLength = 0; iIntervalLength < intervalSequence.length; iIntervalLength++ )//最外层循环，由增量序列元素个数决定

        {
            h = intervalSequence[iIntervalLength];//h为index增量

            int sizeInterArray;//每次内部插入排序的元素个数

            if ( 0 == nItems % h )
            {
                sizeInterArray = nItems/h;
            } else
            {
                sizeInterArray = nItems/h + 1;
            }
            for ( int jZeroToH = 0; jZeroToH < h; jZeroToH++ )//index从 0->h-1 共h-1次循环

            {
                int temp = 0;
                int out = 0,in = 0;
                
                /**
                 * 例如：
                 * 当h=3,intArray.lenght=10时，sizeInterArray初始化为4，
                 * 当jZeroToH=1，此时的内部插入排序元素index=1,4,7，为3个元素，
                 * 所以应该进行判断，以适应内部插入排序元素减少的情况
                 */
                if ( jZeroToH+(sizeInterArray-1)*h >= nItems )
                {
                    sizeInterArray--;
                }
                
                // 内部用插入排序

                // 最大有sizeInterArray个元素有待排序

                for ( int i = 1; i < sizeInterArray; i++ )// 总共有sizeInterArray个元素有待排序，所以循环sizeInterArray次

                {
                    out = jZeroToH + i * h;
                    temp = intArray[out];
                    in = out;
                    while ( in > h-1 && intArray[in - h] > temp )
                    {
                        intArray[in] = intArray[in-h];
                        in = in - h;
                    }
                    intArray[in] = temp;
                }
            }
            System.out.print(iIntervalLength + " : h=" + h + " ");
            this.displayArray();
        }
    }

    // 插入一个元素到待排序数组

    public void insert( int value )
    {
        if ( nItems < maxItems )
        {
            intArray[nItems] = value;
            nItems++ ;
        } else
        {
            System.out.println( "The array is full!" );
        }
    }
    
    //初始化待排序数组

    public void initArray( int[] array )
    {
        for ( int i = 0; i < array.length; i++ )
        {
            intArray[i] = array[i];
        }
        nItems = array.length;
    }
    
    //用随机数初始化

    public void initRandom()
    {
        nItems = 0;
        for ( int i = 0; i < maxItems; i++ )
        {
            int n = (int) ( java.lang.Math.random( ) * maxItems );
            insert( n );
        }
    }

    // 显示数组内容

    public void displayArray()
    {
        System.out.print( "\t" );
        for ( int i = 0; i < nItems; i++ )
        {
            System.out.print( intArray[i] + " " );
        }
        System.out.println( "" );
    }

}


测试程序：

package zieckey.datastructure.study.sort;

public class ShellSortApp
{

    /**
     * @param args
     */
    public static void main( String[] args )
    {
        int[] intervalSequence = { 5, 3, 1 };
        int[] array = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };
        ShellSort ss = new ShellSort( array.length, intervalSequence );
        ss.initArray( array );//初始化待排序数组


        
        System.out.print("Init array: ");
        ss.displayArray();
        ss.shellSortMethod();//排序

        System.out.print("Sorted array: ");
        ss.displayArray();
    }

}


运行结果：

Init array: 49 38 65 97 76 13 27 49 55 4
0 : h=5 13 27 49 55 4 49 38 65 97 76
1 : h=3 13 4 49 38 27 49 55 65 97 76
2 : h=1 4 13 27 38 49 49 55 65 76 97
Sorted array: 4 13 27 38 49 49 55 65 76 97