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、希尔排序法 的示意图


图片.png
图片.png**

5、希尔排序的两种方法

5.1、交换法

5.1.1、源码

  1. package com.study.sort;
  3. import java.util.Arrays;
  4. import java.util.Random;
  6. public class ShellSort {
  8.     public static void main(String[] args) {
  9.         int[] arr ={8,9,1,7,2,3,5,4,6,0};
  10.         shellSort(arr);
  11.     }
  13.     //希尔排序：交换法
  14.     public static void shellSort(int[] arr){
  15.         int count = 1;//计算排序次数
  16.         int temp = 0;//定义临时变量
  17.         for (int gorp = arr.length / 2; gorp > 0; gorp /= 2){//将数组不断分组(arr.length / 2)循环
  18.             for (int i = gorp; i < arr.length; i++){
  19.                 for (int j = i-gorp; j >= 0; j -= gorp){//遍历当前分组，一共gorp个组,步长为gorp;
  20.                     //如果当前元素大于加上步长后的那个元素，则交换
  21.                     if (arr[j] > arr[j+gorp]){
  22.                         temp = arr[j];
  23.                         arr[j] = arr[j+gorp];
  24.                         arr[j+gorp] = temp;
  25.                     }else {
  26.                         break;
  27.                     }
  28.                 }
  29.             }
  30.             System.out.println("第"+(count++)+"轮排序:"+ Arrays.toString(arr));
  31.         }
  32.     }

5.1.2、运行结果

图片.png

5.1.3、测试时间

  1. package com.study.sort;
  3. import java.util.Arrays;
  4. import java.util.Random;
  6. public class ShellSort {
  8.     public static void main(String[] args) {
  10.         int[] arr = new int[8000000];
  11.         Random random = new Random();
  12.         for (int i = 0; i < 8000000; i++) {
  13.             arr[i] = random.nextInt(800000000);
  14.         }
  15.         //交换法时间：
  16.         long l1 = System.currentTimeMillis();
  17.         shellSort(arr);
  18.         long l2 = System.currentTimeMillis();
  19.         System.out.println("希尔排序(交换法)对"+arr.length+"个数据排序所花费的时间为："+(l2-l1)+"ms");
  20.     }
  22.     //希尔排序：交换法
  23.     public static void shellSort(int[] arr){
  24.         int count = 1;//计算排序次数
  25.         int temp = 0;//定义临时变量
  26.         for (int gorp = arr.length / 2; gorp > 0; gorp /= 2){//将数组不断分组(arr.length / 2)循环
  27.             for (int i = gorp; i < arr.length; i++){
  28.                 for (int j = i-gorp; j >= 0; j -= gorp){//遍历当前分组，一共gorp个组,步长为gorp;
  29.                     //如果当前元素大于加上步长后的那个元素，则交换
  30.                     if (arr[j] > arr[j+gorp]){
  31.                         temp = arr[j];
  32.                         arr[j] = arr[j+gorp];
  33.                         arr[j+gorp] = temp;
  34.                     }else {
  35.                         break;
  36.                     }
  37.                 }
  38.             }
  39.             //System.out.println("第"+(count++)+"轮排序:"+ Arrays.toString(arr));
  40.         }
  41.     }

测试结果：
希尔排序(交换法)对80000个随机数进行排序，只用了20ms,比之前的插入排序快了很多，其实希尔排序（交换法）只是在冒泡排序的基础上进行不断地分组，我们之前测试冒泡排序所用的时间为11s。
如果我们以插入排序为基础，进行希尔排序，那么时间应该会更短？
图片.png

5.2、移位法

5.2.1、源码

  1. package com.study.sort;
  3. import java.util.Arrays;
  4. import java.util.Random;
  6. public class ShellSort {
  8.     public static void main(String[] args) {
  9.        int[] arr ={8,9,1,7,2,3,5,4,6,0};
  10.        shellSort2(arr);
  11.     }
  13.     //希尔排序：移位法
  14.     public static void shellSort2(int[] arr){
  15.         int count = 1;//计算排序次数
  16.         for (int gorp = arr.length / 2;gorp>0; gorp /= 2){
  18.             for (int i = gorp;i < arr.length;i++){
  19.                 int j = i;
  20.                 int temp = arr[j];
  21.                 if (arr[j] < arr[j-gorp]){
  22.                     while (j-gorp >= 0 && temp < arr[j-gorp]){
  23.                         arr[j] = arr[j-gorp];
  24.                         j -= gorp;
  25.                     }
  26.                     arr[j] = temp;
  27.                 }
  28.             }
  29.             System.out.println("第"+(count++)+"轮排序:"+ Arrays.toString(arr));
  30.         }
  31.     }
  33. }

5.2.2、运行结果

图片.png

5.2.3、测试时间

  1. package com.study.sort;
  3. import java.util.Arrays;
  4. import java.util.Random;
  6. public class ShellSort {
  8.     public static void main(String[] args) {
  9.        /* int[] arr ={8,9,1,7,2,3,5,4,6,0};
  10.         shellSort2(arr);*/
  12.         int[] arr = new int[80000];
  13.         Random random = new Random();
  14.         for (int i = 0; i < 80000; i++) {
  15.             arr[i] = random.nextInt(800000000);
  16.         }
  17.         //交换法时间：
  18.         long l1 = System.currentTimeMillis();
  19.         shellSort(arr);
  20.         long l2 = System.currentTimeMillis();
  21.         System.out.println("希尔排序(交换法)对"+arr.length+"个数据排序所花费的时间为："+(l2-l1)+"ms");
  23.         //移位法时间：
  24.         long l11 = System.currentTimeMillis();
  25.         shellSort2(arr);
  26.         long l22 = System.currentTimeMillis();
  27.         System.out.println("希尔排序(移位法)对"+arr.length+"个数据排序所花费的时间为："+(l22-l11)+"ms");
  28.     }
  30.     //希尔排序：交换法
  31.     public static void shellSort(int[] arr){
  32.         int count = 1;//计算排序次数
  33.         int temp = 0;//定义临时变量
  34.         for (int gorp = arr.length / 2; gorp > 0; gorp /= 2){//将数组不断分组(arr.length / 2)循环
  35.             for (int i = gorp; i < arr.length; i++){
  36.                 for (int j = i-gorp; j >= 0; j -= gorp){//遍历当前分组，一共gorp个组,步长为gorp;
  37.                     //如果当前元素大于加上步长后的那个元素，则交换
  38.                     if (arr[j] > arr[j+gorp]){
  39.                         temp = arr[j];
  40.                         arr[j] = arr[j+gorp];
  41.                         arr[j+gorp] = temp;
  42.                     }else {
  43.                         break;
  44.                     }
  45.                 }
  46.             }
  47.             //System.out.println("第"+(count++)+"轮排序:"+ Arrays.toString(arr));
  48.         }
  49.     }
  51.     //希尔排序：移位法
  52.     public static void shellSort2(int[] arr){
  53.         int count = 1;//计算排序次数
  54.         for (int gorp = arr.length / 2;gorp>0; gorp /= 2){
  56.             for (int i = gorp;i < arr.length;i++){
  57.                 int j = i;
  58.                 int temp = arr[j];
  59.                 if (arr[j] < arr[j-gorp]){
  60.                     while (j-gorp >= 0 && temp < arr[j-gorp]){
  61.                         arr[j] = arr[j-gorp];
  62.                         j -= gorp;
  63.                     }
  64.                     arr[j] = temp;
  65.                 }
  66.             }
  67.             //System.out.println("第"+(count++)+"轮排序:"+ Arrays.toString(arr));
  68.         }
  69.     }
  71. }

图片.png
测试结果我们发现移位法比交换法还要快，80000个随机数只用短短的4ms就完成了排序，其实不难理解，之前测试的插入排序和冒泡排序所用时间为852ms和11s，很明显插入排序比冒泡排序快很多，所以在插入排序的基础上嵌套一层希尔排序后速度将起飞，嘿嘿。。

再看看800w个随机数所用的时间，如果理论上只要某算法的排序时间比插入排序还短，那么进行希尔排序后，时间可能还会更短
图片.png
或**许这就是算法的魅力吧！
**