排序算法之希尔排序【java实现】

前面介绍的冒泡、选择、插入排序算法虽然简单直观，但是在排序上的效率一般。对于大量的数据排序就需要更加高效的算法，那么下面来介绍一下高效的排序算法----希尔排序，又称Shell排序，缩小增量排序。

实际上，希尔排序是基于插入排序的思想。

实现步骤：

（1）将有n个元素的数组分成n/2的数字序列，第一个数据和第n/2+1个数据为一对。

（2）一次循环使每一个序列对排好序。

（3）然乎，在变为n/4个序列，再次排序。

（4）不断重复上述过程，随着序列减少最后变为一个，也就完成了整个序列。

package zhgyu.sort;

public class ShellSort {

	static final int SIZE = 10;
	
	static void shellSort(int[] arr) {
		
		int temp,r;
		int i,j,k;
		int x = 0;
		
		for(r = arr.length/2; r >= 1; r /= 2) {
			for(i = r; i < arr.length; i++) {
				temp = arr[i];
				j = i - r;
				while(j >= 0 && arr[j] > temp) {
					arr[j+r] = arr[j];
					j -= r;
				}
				arr[j+r] = temp;
			}
			
			x++;
			System.out.print("第"+ x +"次的排序结果:");
			for(k = 0; k < arr.length; k++) {
				System.out.print(arr[k] + "\t");
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		int[] arr = new int[SIZE];
		int i;
		
		for(i = 0; i < SIZE; i ++) {
			arr[i] = (int)(Math.random()*(100 + 1));
		}
		//排序前的数组
		System.out.print("排序前的数组:" + "\t");
		for(i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + "\t");
		}
		System.out.println();
		
		//调用插入排序算法
		shellSort(arr);
		
		//排序后的数组
		System.out.print("排序前的数组:" + "\t");
		for(i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + "\t");
		}
		System.out.println();

	}
}