希尔排序法

2018年04月09日 10:50 | 2923次浏览 作者原创 版权保护

概念

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

基本思想

先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量  =1(  <  …<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

算法稳定性

由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。


java代码实现

package com.wepayweb.weixin.util.paixu;
/***
 * 
 * @author www.vxzsk.com V型知识库
 *
 */
public class Shellsort {
	final int MAX=20;  
	   int num[]=new int[MAX];  
	   {  
	       System.out.print("排序前生成的随机数组是:");  
	       for(int i=0;i<20;i++){  
	           num[i]=(int)(Math.random()*100);  
	           System.out.print(num[i]+" ");  
	       }  
	       System.out.println();  
	   }  
	     
	
	/*--------------------------shell(希尔)排序法---------------------------- 
    Shell首先将间隔设定为n/2,然后跳跃进行插入排序,再来将间隔n/4,跳跃进行排序动作,再来 
    间隔设定为n/8、n/16,直到间隔为1之后的最后一次排序终止,由于上一次的排序动作都会将 
    固定间隔内的元素排序好,所以当间隔越来越小时,某些元素位于正确位置的机率越高,因此 
    最后几次的排序动作将可以大幅减低。 
    ---------------------------------------------------------------------*/  
   public void shellsort(int number[]) {  
        int i, j, k, gap, temp;  
        long start,end;  
          
        start=System.nanoTime();  
        gap = MAX / 2;  
        while(gap > 0) {  
            for(k = 0; k < gap; k++) {  
                for(i = k+gap; i < MAX; i+=gap) {  
                    for(j = i - gap; j >= k; j-=gap) {  
                        if(number[j] > number[j+gap]) {  
                            temp=number[j];  
                            number[j]=number[j+gap];  
                            number[j+gap]=temp;  
                        }else{  
                            break;  
                        }  
                    }  
                }  
            }  
            gap /= 2;  
        }  
        end=System.nanoTime();  
          
        System.out.println("-----------------shell(希尔)排序法(改进的插入排序法)------------------");  
        System.out.print("排序后是:");  
        for(i=0;i<=MAX-1;i++){  
            System.out.print(number[i]+" ");  
        }  
        System.out.println();  
        System.out.println("排序使用时间:"+(end-start)+" ns");  
   }  
     

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Shellsort s = new Shellsort();
		s.shellsort(s.num.clone());                        //希尔排序
	}

}

执行main方法即可观察效果



小说《我是全球混乱的源头》
此文章本站原创,地址 https://www.vxzsk.com/770.html   转载请注明出处!谢谢!

感觉本站内容不错,读后有收获?小额赞助,鼓励网站分享出更好的教程