希尔排序

希尔排序

 *尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。
 *排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，
 *重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。
 *
 *希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，
 *速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。
 *所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，
 *不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，
 *最后其稳定性就会被打乱，所以shell排序是不稳定的。

 

package com.algorithm;

/**
 * 希尔排序
 * @author lenovo
 *尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。
 *排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，
 *重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。
 *
 *希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，
 *速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。
 *所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，
 *不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，
 *最后其稳定性就会被打乱，所以shell排序是不稳定的。
 */
public class ShellSort {

	/**
	 * 排序方法
	 */
	public static void sort(long[] attr){
		//初始化一个间隔
		int h=1;
		//计算最大间隔
		while (h<attr.length/3) {
			h=h*3+1;
		}
		while(h>0){
			//进行插入排序
			long temp=0;
			for (int i = h; i < attr.length; i++) {
				temp =attr[i];
				int j=i;
				while (j>h-1&&attr[j-h]>=temp) {
					attr[j]=attr[j-h];
					j =j-h;
				}
				attr[j]=temp;
			}
			//减小间隔
			h=(h-1)/3;
		}
	}
	
	public static void main(String[] args) {
		long[] attr = new long[5];
		attr[0]=34;
		attr[1]=23;
		attr[2]=2;
		attr[3]=55;
		attr[4]=1;
		
		System.out.print("{");
		for (int i = 0; i < attr.length; i++) {
			System.out.print(attr[i]+" ");
		}
		System.out.println("}\n");
		
		sort(attr);
		
		System.out.print("{");
		for (int i = 0; i < attr.length; i++) {
			System.out.print(attr[i]+" ");
		}
		System.out.println("}\n");
	}
}