1、 简单插入排序存在的问题
我们看简单的插入排序可能存在的问题。
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。
2、希尔排序法介绍
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
3、希尔排序法基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
4、希尔排序法的示意图
5、希尔排序法应用实例
请从小到大排序.对{8,9,1,7,2,3,5,4,6,0} 请分别使用
希尔排序时， 对有序序列在插入时采用交换法, 并测试排序速度；
希尔排序时， 对有序序列在插入时采用移动法, 并测试排序速度。
【交换法】逐步推导
第一轮
int temp = 0; //希尔排序的第一轮 //思路：第一轮排序是将10个数据分成了5组 for(int i=5;i<arr.length;i++){ //遍历各组中的所有元素，每组中有2个元素，步长是5 for(int j=i-5;j>=0;j-=5){ //如果当前元素大于加上步长后的那个元素，就交换 if(arr[j]>arr[j+5]){ temp = arr[j]; arr[j] = arr[j+5]; arr[j+5] = temp; } } } System.out.println("希尔排序第一轮后的结果："); for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" "); } System.out.println();第二轮
// 希尔排序的第2轮 // 思路：第二轮排序是将10个数据分成了5/2=2组 for (int i = 2; i < arr.length; i++) { // 遍历各组中的所有元素，每组中有2个元素，步长是5 for (int j = i - 2; j >= 0; j -= 2) { // 如果当前元素大于加上步长后的那个元素，就交换 if (arr[j] > arr[j + 2]) { temp = arr[j]; arr[j] = arr[j + 2]; arr[j + 2] = temp; } } } System.out.println("希尔排序第二轮后的结果："); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println();第三轮
// 希尔排序的第3轮 // 思路：第一轮排序是将10个数据分成了2/2=1组 for (int i = 1; i < arr.length; i++) { // 遍历各组中的所有元素，每组中有2个元素，步长是5 for (int j = i - 1; j >= 0; j -= 1) { // 如果当前元素大于加上步长后的那个元素，就交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } System.out.println("希尔排序第二轮后的结果："); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println();最终代码
int temp = 0; int count = 0; // 根据前面的逐步分析，使用循环处理 for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { // 遍历各组中的所有元素，共gap组，每组中有2个元素，步长是gap for (int j = i - gap; j >= 0; j -= gap) { // 如果当前元素大于加上步长后的那个元素，就交换 if (arr[j] > arr[j + gap]) { temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } // System.out.println("希尔排序第"+(++count)+"轮后的结果："); // for(int i=0;i<arr.length;i++){ // System.out.print(arr[i]+" "); // } // System.out.println(); }测试时间
//测试80000个数据 int arr[] = new int[80000]; for(int i=0;i<80000;i++){ arr[i] = (int)(Math.random()*800000); //随机生成【0.80000】 } //写一个测试时间 Date date1 = new Date(); SimpleDateFormat simple1 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String str1 = simple1.format(date1); System.out.println("排序前的时间："+str1); shellSort2(arr); Date date2 = new Date(); String str2 = simple1.format(date2); System.out.println("排序前的时间："+str2);可以发现交换法的希尔排序速度非常慢
【移动法】
// 对交换式希尔排序进行改进----》移位法 public static void shellSort2(int[] arr) { // 使用增量的gap，并逐步缩小增量 for (int gap = arr.length / 2; gap > 0; gap /= 2) { // 从第gap个元素开始，逐个对其所在的组直接插入排序 for (int i = gap; i < arr.length; i++) { int index = i; int temp = arr[index]; if (arr[index] < arr[index - gap]) { while (index - gap >= 0 && temp < arr[index - gap]) { // 移动 arr[index] = arr[index - gap]; index -= gap; } // 找到位置 arr[index] = temp; } } } }移动法使用了插入排序。
速度极大的提高了。
再附上另一种，思路是一样的，速度同样很快
public static void TestShellSort(int[] arr) { int increment = arr.length; int i, j, k; do { increment = increment / 3 + 1; for (i = 0; i < increment; i++) { //插入排序的思路 for (j = i + increment; j < arr.length; j += increment) { if (arr[j] < arr[j - increment]) { int temp = arr[j]; for (k = j - increment; k >= 0 && temp < arr[k]; k -= increment) { arr[k + increment] = arr[k]; } arr[k + increment] = temp; } } } } while (increment > 1); }希尔排序比插入排序多了分组，稍微难理解一点。
