高级排序--希尔排序

希尔排序：

 

实际上是基于插入排序的，在插入排序中相比较的是相邻的两个元素，但是如果一个很小的数在数组的最右端，而他本应该是在最左端的，这样的话所有中间的元素都要向右移动一位，并且执行了N次。希尔排序就是首先对大跨度的元素做比较并且进行移动，这样的久相对有序了，再在这个基础上进行普通的插入排序，效率就会高很多。

 

效率：

 

快速排序>希尔排序>简单排序

希尔排序在最坏的执行效率上和平均的执行效率上没有差很多。

 

<!--StartFragment --> 

 

public class ShellSort {
	
	public static void main(String[] args) {
		int[] arr = {4,5,9,3,2,1,6,18,11,15,10};
		
		ShellSort.display(arr);
		ShellSort.shellSort(arr);
		System.out.println("------------------------------");
		ShellSort.display(arr);
	}
	
	public static void display(int[] theArray){
		int nElems = theArray.length;
		System.out.println("A=");
		for(int j = 0; j < nElems; j++){
			System.out.println(theArray[j] + " ");
		}
		System.out.println(" ");
	}
	
	public static void shellSort(int[] theArray){
		int inner,outer;
		
		//临时变量
		int temp;
		
		//数组长度
		int nElems = theArray.length;
		
		//定义元素跨度数量
        int h=1;       

        //定义元素跨度基数   
        int n = 3;
        
        /**
         * 设置排序元素之间的位置 公式：h = h * n +1
         * 例：n=3 则元素跨度为(0,4),(1,5),(2,6)...
         *   n=4 -->(0,5),(1,6),(2,7)...
         */
        while(h<=nElems/n){
        	  h=h*n+1;    //1,4,13,40,121,...   
        }
         
        while (h>0){
        	
        	/**
        	 * 这里的for循环会执行2次
        	 * 第一次：  h=4 以元素跨度个数为4的情况下循环一次(0,4),(1,5),(2,6)
        	 * 第二次：  h=1 也就执行插入排序对相邻的元素进行比较
        	 */
	        for(outer=h;outer<nElems;outer++){
	        		
	        		/**
	        		 * 存储基数 outer = h 位置的元素，每次outer++，比较的元素
	        		 * 位置也就向后移动一位0,4),(1,5)
	        		 * 移动的次数  数组长度 - h;
	        		 */
	                temp=theArray[outer];   
	                inner=outer;   
	               
	              /**
	               * 如果已经替换条件成则立进行替换
	               */
	              while(inner>h-1&&theArray[inner-h]>=temp){   
	                theArray[inner]=theArray[inner-h];
	                
	                //已经替换后，变更inner值，为首元素（0,4）中的0，(1,5)中的1
	                inner-=h;   
	                }
	            //将换后的临时值替换位置
	            theArray[inner]=temp;   
	        }
	        
	        //关键：这里将元素基数变为1，也就将这个运算变为了插入排序。
            h=(h-1)/n;   
         }   
     }   
}