希尔排序

希尔排序

希尔排序的思想是分组的直接插入排序。由直接插入排序可知，若数据序列越接近有序，则时间效率越高；再者，当n越小时，时间效率越高。希尔排序就是基于这两点对直接插入排序进行改进的。

希尔排序算法描述如下：
1.将一个数据序列分成若干组，每组由若干相隔一段距离的元素组成，这段距离称为增量，在一个组内采用直接插入排序算法进行排序。
2.增量的初值通常为数据序列长度的一半，以后每趟增量逐渐缩小，最后为1.随着增量的逐渐减小，组数也减少，组内元素个数增加，整个序列接近有序。当增量为1时，只有一组，元素是整个序列，在进行一次直接插入排序即可。

package com.shellsort.yy;

/**
 * 希尔排序，也叫做缩减增量排序，是插入排序的一种， 是针对直接插入排序的改进
 * 
 * @author yuyang_csu
 *@data 2013-4-5
 */
public class ShellSort {
	private int[] arr;

	public ShellSort(int[] arr) {
		this.arr = arr;
	}
	
	public void shellSort(){
		// 设置增量为数组长度的一半，并每次以1/2递减增量,直到以1为增量为止
		for(int gap = arr.length/2;gap>0;gap/=2){
			//将原数组拆分为i个小数组
			for(int i = gap;i<arr.length;i++)
			{
				//待插入的元素
				int tmp = arr[i];
				//直接插入排序
				for(int j =i;j>=gap&&tmp<arr[j-gap];j-=gap){
					arr[j]=arr[j-gap];
					arr[j-gap] = tmp;
				}
			}
		}
	}
	
	//显示数组元素的方法
	public void display(){
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	public static void main(String[] args) {
		int[] arr = {1,9,2,10,3,11,4,12,5,13,6,14,7,15,8,16};
		ShellSort ss = new ShellSort(arr);
		ss.shellSort();
		ss.display();
	}
}

希尔排序的时间复杂度：查阅了好多资料，好像希尔排序的时间复杂度跟所给的序列有序程度有关，希尔排序的时间复杂度大概在O(NlogN)~~O(N^2)


希尔排序的稳定性：我们知道插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。