经典之希尔排序

希尔排序

希尔排序是插入排序的一种改进，用大O表示法，其算法时间复杂度为O（nlogn）
其基本思想是：
先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，接近O（n），因此希尔排序在时间效率上比插入排序有较大提高。

希尔排序java实现：

/**
 * shell sort is an improved insertion sort
 */
public class ArrayShell {
	private long[] a;
	private int nElement;
	public ArrayShell(int max) {
		this.a = new long[max];
		this.nElement = 0;
	}
	public void shellSort(){
		int outer,inner;
		//calculate the initial value of sort interval
		int h=1;
		while(h<=nElement/3){
			h=h*3+1;
		}
		while(h>0){
			for(outer=h;outer<nElement;outer++){
				long temp = a[outer];//挖走outer，放到temp里
				inner = outer;//初始化inner为outer索引
				while(inner>h-1 && a[inner-h]>temp){//增量h的左边那个大，
					a[inner] = a[inner-h];//把左边大的填到挖走的地方
					inner -= h;//把inner指向左边被挖走的大的地方
				}
				a[inner] = temp;//把temp填到左边被挖走的大的地方
			}
			h=(h-1)/3;//减小增量h
		}
	}
	public void insert(long v){
		a[nElement++]=v;
	}
	public void display(){
		for(int i=0;i<nElement;i++){
			System.out.print(a[i]+"\t");
		}
		System.out.print("\n");
	}
	
}

直接插入排序基本思想：
每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
直接插入排序java实现：

public class ArrayIns {
	private long[] a;
	private int nElement;
	public ArrayIns(int max) {
		a= new long[max];
		nElement = 0;
	}
	
	public void insertionSort(){
		int out,in;
		for(out=1;out<nElement;out++){
			if(a[out-1]>a[out]){
				long temp = a[out];
				for(in = out-1;in>=0 && temp<a[in];in--){
					a[in+1]=a[in];
				}
				a[in+1]=temp;
			}
		}
	}
	public void insert(long v){
		a[nElement++]=v;
	}
	public void display(){
		for(int i=0;i<a.length;i++){
			System.out.print(a[i]+"\t");
		}
		System.out.print("\n");
	}
}