希尔排序

 

排序有基本可以划分为简单排序和高级排序，简单排序有冒泡排序，选择排序，插入排序。高级排序有希尔排序和基于划分思想的快速排序。

希尔排序是基于插入排序的，通过加大插入排序中元素之间的间隔，并在有间隔的元素中进行插入排序，从而使数据项能大跨度的移动。经过一趟排序后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去。

       首先是插入排序的代码

 

public class InsertSort {

	public static void main(String[] args) {
		
		int[] a = {2,4,1,8,5,3,9};
		System.out.println("排序前：");
		for(int i:a)
		{
			System.out.print(i);
		}
		System.out.println();
		
		int out;//需要插入的元素下标
		int in;
		for(out=1;out<a.length;out++)
		{
			int temp = a[out];
			in = out;
			//逐步比较，若是数组的元素大于需要插入的元素则向左移动。
			while(in>0&&a[in-1]>=temp)
			{
				a[in] = a[in-1];
				--in;
			}
			a[in] = temp;
		}
		System.out.println("排序后：");
		for(int i:a)
		{
			System.out.print(i);
		}
	}
}

 接下来就是希尔排序的代码，只是在插入排序上面做了很少的更改。

public class ShellSort {

	public static void main(String[] args) {
		int[] a = {2,4,1,8,5,3,9};
		System.out.println("排序前：");
		for(int i:a)
		{
			System.out.print(i);
		}
		System.out.println();
		
		int h = 1; //希尔排序中元素的间隔
		while(h<=a.length/3)
		{
			h = h*3 + 1; //kunth序列，有其他的产生序列方式
               }
		
		while(h>0)
		{	
			//插入排序部分
			int out;//需要插入的元素下标
			int in;
			for(out=1;out<a.length;out++)
			{
				int temp = a[out];
				in = out;
				//逐步比较，若是数组的元素大于需要插入的元素则向左移动。否则将元素插入到该位置。间隔为h
				while(in>h-1&&a[in-h]>=temp)
				{
					a[in] = a[in-h];
					in-=h;
				}
				a[in] = temp;
			} 
			h = (h-1)/3;	//逐步减小序列间的距离
		}
		System.out.println("希尔排序后");
		for(int i : a)
		{
			System.out.print(i);
		}
	}
}