java 希尔排序算法（自己写）

希尔排序算法是对插入算法的应用吧，就是多次的使用了插入算法多排序的数组进行排序。

 

1.效率问题

 

   希尔算法的效率到现在还没有理论上的正确答案，但是在实际的测试中的实际复杂度是 N^(3/2)--N^(7/6)之间。空间复杂度是1，它的辅助空间并没有因为数组的大小而改变。

 

2.插入算法的代码

 

    为了清楚的和希尔排序进行比较，先来看下插入算法的排序

     /**

 * 插入排序在大多数的情况是比冒泡算法和选择排序好要的，比冒泡算法要快一倍，比选择排序是快一点
 * 尽管算法比其他的两个要麻烦一点，但是它的想法不复杂，即使它的时间复杂度也是n^2。
 * 插入排序经过被用于在比较复杂的排序算法的最后，快速排序要用到插入排序的
 * ta会出现局部有序，就是在数组的左边的序列是局部的有序的，这样的情况是其他两个没有出现的
 */
	public void sort() {
		
		int out, in ;
        long value = 0l ;
		for (out=1; out < this.nElems-1; out++) { //从1开始，因为第一个已经排序好了的                              
			
			 value = a[out] ;
             in = out ;
             while (in > 0 && a[in] >= value) {
            	 
              a[in] = a[in - 1] ;
              in-- ;
              
             }
             
            a[in] = value ;
              
		}
	}   

 

3.希尔算法的代码

    package endual;

public class ShellSort {

	private long[] theArray ; //待排序的数组
	private int nElems ; //个数
	
	public ShellSort(long[] theArray, int n) {
		
		this.theArray = theArray ;
		this.nElems = n ;
	}
	/**
	 * 打印数列
	 */
	public void displayArray() {
		
		for(int i=0;i<this.theArray.length;i++){
			
			System.out.println(this.theArray[i]);
		}
		
	}
	//下面是希尔算法的排序
	public void shell() {
		
		int inner ;
		int outer ;
		long temp ;
		
		int h = 1 ; //初始的h的值
		while(h <= nElems/3) {
			
			h = h*3 + 1 ;
		}//求出最大的h是多数喽	
			while(h > 0) {
				
				//>>>>>>>>>>>>>>>>>>>>将h改成1那就是插入算法了>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
	
				for(outer = h; outer < this.nElems; outer++) {
					temp = theArray[outer] ;
					inner = outer ;
			
					while(inner > h-1 && theArray[inner-h] >= temp) {
						
						theArray[inner] = theArray[inner-h] ;
						inner = inner - h ;
					
					} // end while
					theArray[inner] = temp ;
					
				} // end for
				//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
				h = (h-1) / 3 ; //然后按照公式将h递减到1形成排序就OK了
				
			} // end whlie (h>0)_

	} //end shell
	
	
}

   测试类代码

package endual;

public class ShellMainApp {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		long[] theArray = {9,32,6,4,2,78,1};
		int n = theArray.length;
		ShellSort ss = new ShellSort(theArray, n) ;
		ss.shell() ;
		ss.displayArray();
	}

}

 

4.希尔算法的一些理论资料

希尔排序是计算机科学家Shell发明的，是基于插入排序的，对插入排序进行改进的。
依靠这个特别的实现机制，希尔排序对于多达几千个数据项，中等大小规模的数组排序表现良好。
希尔排序不像快速排序和归并排序一样，时间复杂度是NlogN的排序算法快，因此对非常大的文件排序并不是最优的选择。
但是希尔排序比选择排序和插入排序这种时间复杂度为N^2的算法速度要快的多了

插入排序：复制的次数太多

插入排序执行到一半的时候，标记符号左边这部分数据项是排序过的，这些数据项中间是有序的，而标记右边的数据项则没有排序过的。
这个算法取出标记符号所指向的数据项，把它存储在一个临时变量里。接着，从刚刚被移除的数据项左边第一个单元开始，每次把有序的
数据项右移动一个单元，直到存储在临时变量里的数据项能够有序回插

插入算法中出现一个特例：
假设一个很小得数据项是很靠近右端位子上，这里本来应该是值比较大的数据项多在的位子。把这个小数据项移动到左边的正确位子上，
所有中间数据项 这个数据项原来所在的位子和它应该移动到位子之间的数据项都必须移动一位。这个步骤对每个数据项都执行了大概N次的复制
虽然不是所有的数据项都要移动N个位子，但是平均移动了N/2次。插入算法的效率是N^2
如果能以一种方式不必一个一个地移动所有中间的数据项，就能把较小的数据项移动到左边。那么这个算法的执行效率就会有很大的改进了

n-增量排序
  希尔排序通过加入插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能大跨度地移动。
  当这些数据项排过一趟后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去。进行这些排序时数据项之间的间隔被
  称为增量，并且习惯用小写的字母h表示。
  这里的增量是排序数据项的间隔大小，然后对这个间隔的数据项归为一组 对其在数组中进行排序 交换位子
 
 经过这个增量的加入，然后排序过以后，新数列有新的特点了，那就是小的数据是在左边，大的数据是在有边，不大不小的数据是在中间了
 但是没有完全的进行好了排序 。这也是希尔排序的奥秘所在。

插入排序对基本有序的数组是非常有效的，如果插入排序值需要把数据项移动一位或者两位，那么算法大概需要N时间复杂度。当数组完成增量为
4的排序之后，可以进行普通的插入排序。
减小间隔
对于更大的数组，开始的间隔应该大写，然后间隔不断变小，直到间隔为0
举例来说把，对于 含有1000个数据项的数组，可能先以264为增量，然后用121为增量，然后用40为增量，然后用13然后用4最后用1为增量进行希尔排序。
用来间隔的数组成的列称为 间隔数列。
    h = 3*h + 1 (h从1开始)
可以这样来取
排序算法中，首先在一个短小的循环中使用序列的生成公式来计算出最初的间隔。h值最初赋值为1，然后用公式生成4 13 40等等，当间隔
大于数组大小的时候停止h的迭代。
对于含有1000个数据项的，1093就是太大了，那样用364就够了。然后倒即