希尔排序

直接插入排序的效率在某些时候是很高的，比如，记录本身就是基本有序的，我们只需要少量的插入操作，就可以完成整个记录集的排序工作，此时直接插入很高效。还有就是记录数比较少时，直接插入的优势也比较明显。可问题在于两个条件本身就过于苛刻，现实中记录少或者基本有序都属于特殊情况。

希尔排序是直接插入排序经过改进之后的一个更高效的版本。

基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。

思路

代码实现

package com.nanzx.sort;

import java.util.Arrays;

public class ShellSort {

	public static void main(String[] args) {
		int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
        shellSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static void shellSort(int[] arr) {
		for (int gap = arr.length / 2; gap > 0; gap /= 2) {
			// 从第gap个元素开始，逐个对其所在的组进行直接插入排序，组里相邻元素的间隔为gap
			for (int i = gap; i < arr.length; i++) {
				int index = i;
				int insertValue = arr[index];
				while (index - gap >= 0 && insertValue < arr[index - gap]) {
					arr[index] = arr[index - gap];
					index -= gap;
				}
				arr[index] = insertValue;
			}
		}		
	}
}

测试希尔插入排序的速度

package com.nanzx.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

public class ShellSort {

	public static void main(String[] args) {
		// 创建一个8000000个元素的随机的数组，8百万个元素
		int[] arr = new int[8000000];
		for (int i = 0; i < 8000000; i++) {
			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
		}
        
		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("排序前的时间是=" + date1Str);

		shellSort(arr);

		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序后的时间是=" + date2Str);
	}

	public static void shellSort(int[] arr) {
		for (int gap = arr.length / 2; gap > 0; gap /= 2) {
			// 从第gap个元素开始，逐个对其所在的组进行直接插入排序，组里相邻元素的间隔为gap
			for (int i = gap; i < arr.length; i++) {
				int index = i;
				int insertValue = arr[index];
				while (index - gap >= 0 && insertValue < arr[index - gap]) {
					arr[index] = arr[index - gap];
					index -= gap;
				}
				arr[index] = insertValue;
			}
		}	
	}
}