疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

Java经典排序算法之希尔排序


 

 

 
一、希尔排序(Shell Sort)
希尔排序(Shell Sort)是一种插入排序算法,因D.L.Shell于1959年提出而得名。Shell排序又称作缩小增量排序。
 
 
二、希尔排序的基本思想
希尔排序的中心思想就是:将数据进行分组,然后对每一组数据进行排序,在每一组数据都有序之后
 ,就可以对所有的分组利用插入排序进行最后一次排序。这样可以显著减少交换的次数,以达到加快排序速度的目的。
     
希尔排序的中心思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
     该方法实质上是一种分组插入方法。
 
shell排序的算法实现:
[java] view plaincopy
void ShellPass(SeqList R,int d)  
   {//希尔排序中的一趟排序,d为当前增量  
     for(i=d+1;i<=n;i++) //将R[d+1..n]分别插入各组当前的有序区  
       if(R[i].key<R[i-d].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].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",以防下标越界。
 
 
三、希尔排序算法分析
 
1、增量序列的选择。
Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征如下:
a.最后一个增量必须为1。
b.应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量实验给出了目前最好的结果:当n较大时,比较和移动的次数大概在n^1.25到n^1.26之间。
 
2、Shell排序的时间性能优于直接插入排序。
希尔排序的时间性能优于直接排序的原因如下:
a.当文件初态基本有序时,直接插入排序所需的比较和移动次数均较少。
b.当n值较小时,n和n^2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n^2)差别不大。
c.在希尔排序开始时增量较大,分组较多,每组记录数目少,故每组内直接插入排序较快,后来增量d(i)逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按d(i-1)做为距离拍过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。因此,希尔排序在效率上较直接插入排序有较大的改进。
 
3、稳定性
希尔排序是不稳定的。
 
 
四、算法演练
 
假定待排序文件由10个记录,其关键字分别是:40、38、65、97、76、13、27、49、55、04。
增量序列取值依次为:5、3、1
 
 
五、代码实现
 
[java] view plaincopy
public class ShellSortTest {  
    private static void shellSort(int[] source) {  
        int j;  
        for (int gap = source.length / 2; gap > 0; gap /= 2) {  
            for (int i = gap; i < source.length; i++) {  
                int temp = source[i];  
                for (j = i; j >= gap && temp < source[j - gap]; j -= gap)  
                    source[j] = source[j - gap];  
                source[j] = temp;  
            }  
            System.out.print("增长序列:" + gap + " :");  
            printArray(source);  
        }  
    }  
  
    private static void printArray(int[] source) {  
        for (int i = 0; i < source.length; i++) {  
            System.out.print(" " + source[i]);  
        }  
        System.out.println();  
    }  
  
    public static void main(String[] args) {  
        int source[] = new int[] {49,38,65,97,76,13,27,49,55,04 };  
        System.out.print("原始序列:");  
        printArray(source);  
        System.out.println("");  
  
        shellSort(source);  
  
        System.out.print(" 最后结果:");  
        printArray(source);  
    }  
  
}  
 
 
运行结果为:
 
[java] view plaincopy
原始序列:   49  38  65  97  76  13  27  49  55  4  
  
增长序列:5 :    13  27  49  55  4   49  38  65  97  76  
增长序列:2 :    4   27  13  49  38  55  49  65  97  76  
增长序列:1 :    4   13  27  38  49  49  55  65  76  97  
  
  
最后结果:   4   13  27  38  49  49  55  65  76  97  
 
发现增长序列是5,2,1  和题目要求的5,3,1不同。通过分析要排序的文件由10个记录,10/2=5,5-2=3,3-2=1。刚好符合要求,因此将上面的代码稍作修改即可改变增长序列的值。
将shellSort(int[] source) 方法里的下面这行代码
[java] view plaincopy
for (int gap = source.length / 2; gap > 0; gap /= 2) {  
改为:
[java] view plaincopy
for (int gap = source.length / 2; gap > 0; gap -= 2) {  
然后重新运行程序,打印结果如下:
[java] view plaincopy
原始序列:   49  38  65  97  76  13  27  49  55  4  
  
增长序列:5 :    13  27  49  55  4   49  38  65  97  76  
增长序列:3 :    13  4   49  38  27  49  55  65  97  76  
增长序列:1 :    4   13  27  38  49  49  55  65  76  97  
  
  
最后结果:   4   13  27  38  49  49  55  65  76  97  
 
 
=================================================================
如果想使用指定的增长序列来对指定的数组进行希尔排序,可以对上面的程序修改,修改后代码如下:
[java] 
public class ShellSortTest2 {  
    /** 
     * 待排序的数组 
     */  
    private int[] sources;  
    /** 
     * 数组内元素个数 
     */  
    private int itemsNum;  
    /** 
     * 增量数组序列 
     */  
    private int[] intervalSequence;  
  
    /** 
     * @param maxItems 
     *            数组大小 
     * @param intervalSequence 
     *            增量数组序列 
     */  
    public ShellSortTest2(int[] source, int[] intervalSequence) {  
        this.sources = new int[source.length];  
        this.itemsNum = 0;// 还没有元素  
        this.intervalSequence = intervalSequence;  
    }  
  
    /** 
     * 希尔排序算法 
     */  
    public void shellSort() {  
        int gap = 0;// 为增量  
        for (int iIntervalLength = 0; iIntervalLength < intervalSequence.length; iIntervalLength++)// 最外层循环,由增量序列元素个数决定  
        {  
            gap = intervalSequence[iIntervalLength]; // 从增量数组序列取出相应的增长序列  
            int innerArraySize;// 每次内部插入排序的元素个数  
            if (0 == itemsNum % gap) {  
                innerArraySize = itemsNum / gap;  
            } else {  
                innerArraySize = itemsNum / gap + 1;  
            }  
            for (int i = 0; i < gap; i++) {  
                int temp = 0;  
                int out = 0, in = 0;  
                if (i + (innerArraySize - 1) * gap >= itemsNum) {  
                    innerArraySize--;  
                }  
                // 内部用插入排序  
                for (int j = 1; j < innerArraySize; j++) {  
                    out = i + j * gap;  
                    temp = sources[out];  
                    in = out;  
                    while (in > gap - 1 && sources[in - gap] > temp) {  
                        sources[in] = sources[in - gap];  
                        in = in - gap;  
                    }  
                    sources[in] = temp;  
                }  
            }  
            System.out.print("增长序列为:  " + gap + " ");  
            this.displayArray();  
        }  
    }  
  
    /** 
     * 初始化待排序数组 
     */  
    public void initArray(int[] array) {  
        for (int i = 0; i < array.length; i++) {  
            sources[i] = array[i];  
        }  
        itemsNum = array.length;  
    }  
  
    /** 
     * 显示数组内容 
     */  
    public void displayArray() {  
        for (int i = 0; i < itemsNum; i++) {  
            System.out.print(" " + sources[i] + " ");  
        }  
        System.out.println(" ");  
    }  
  
    public static void main(String[] args) {  
        int[] intervalSequence = { 5, 3, 1 };  
        int[] source = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };  
        ShellSortTest2 ss = new ShellSortTest2(source, intervalSequence);  
        // 初始化待排序数组  
        ss.initArray(source);  
        System.out.print("原始序列: ");  
        ss.displayArray();  
        // 希尔排序  
        ss.shellSort();  
  
        System.out.print("最后结果: ");  
        ss.displayArray();  
    }  
}  
 
运行结果如下:
[java] 
原始序列:   49  38  65  97  76  13  27  49  55  4   
  
增长序列为:  5   13  27  49  55  4   49  38  65  97  76   
  
增长序列为:  3   13  4   49  38  27  49  55  65  97  76   
  
增长序列为:  1   4   13  27  38  49  49  55  65  76  97   
  
最后结果:   4   13  27  38  49  49  55  65  76  97