算法入门教程-希尔排序

上节我们学习了插入排序,其实插入排序存在一些小的缺陷,还是不够完美,所以有人在它的基础上进行了完善,.由于完善的人叫希尔,故此算法的思想叫希尔排序算法思想,为啥说插入排序有缺陷了,我们来简单的看一个例子:

• 假如我有这样一个待排序的数组如: int [] arr = {2,3,4,5,6,1},通过之前的分步推导我们来看排序的过程:
• 第一轮排序的代码如下:

  //逐步推导过程
    //{2,3,4,5,6,1} -> 首先以{2}为有序列表,以{3,4,5,6,1}为无序列表
    //将无序列表中的数往有序列表中添加
    //定义待插入的数和索引下标
    int insertVal = arr[1]; //这里也就是3
    int insertIndex = 1 - 1; //arr[1]前面数的下标

    //简单说明:
    //1. insertIndex>=0 其主要的目的是为了防止在插入时候为了约束越界
    //2. insertVal < arr[insertIndex]表示待插入的数还没有找到插入的位置
    //3. 需要将 arr[insertIndex]往后移动
    while (insertIndex >= 0 && insertVal < arr[insertIndex]) {

        arr[insertIndex + 1] = arr[insertIndex]; 
        insertIndex--;
    }
    //当退出while循环时,说明插入的位置找到,需要 insertIndex +1 如: 34改为 134
        arr[insertIndex + 1] = insertVal;
    System.out.println("第一轮插入后的结果为:");
    System.out.println(Arrays.toString(arr));

由于上述给的排序的数组的特殊性,其实我们的while循环是不进去的,只需要因为将无序列表的3插入有序列表的{2}中时,3>2,所以插入到有序列表{2}的后面即{2,3}来看测试结果:

第一轮排序结果.png

跟我们预想的结果一样,接着看:

• 第二轮排序过程:

 //定义待插入的数和索引下标
     insertVal = arr[2]; 
     insertIndex = 2-1; 
    //简单说明:
    //1. insertIndex>=0 其主要的目的是为了防止在插入时候为了约束越界
    //2. insertVal < arr[insertIndex]表示待插入的数还没有找到插入的位置如:
    //3. 需要将 arr[insertIndex]往后移动
    while (insertIndex >=0 && insertVal < arr[insertIndex]){

        arr[insertIndex +1] = arr[insertIndex]; 
        insertIndex --;
    }
    //当退出while循环时,说明插入的位置找到,需要 insertIndex +1 
    arr[insertIndex + 1] = insertVal;
    System.out.println("第二轮插入后的结果为:");
    System.out.println(Arrays.toString(arr));

分析过程跟第一轮的一样,我们来看结果:

第二轮排序结果.png

• 第三轮排序过程

 //定义待插入的数和索引下标
    insertVal = arr[3]; //这里也就是119
    insertIndex = 3-1; //arr[2]前面数的下标
    //简单说明:
    //1. insertIndex>=0 其主要的目的是为了防止在插入时候为了约束越界
    //2. insertVal < arr[insertIndex]表示待插入的数还没有找到插入的位置如: 34 < arr[] =101
    //3. 需要将 arr[insertIndex]往后移动
    while (insertIndex >=0 && insertVal < arr[insertIndex]){

        arr[insertIndex +1] = arr[insertIndex]; //此时的数组为{101,101,119,1}
        insertIndex --;
    }
    //当退出while循环时,说明插入的位置找到,需要 insertIndex +1 如: 34改为 134
    arr[insertIndex + 1] = insertVal;
    System.out.println("第三轮插入后的结果为:");
    System.out.println(Arrays.toString(arr));

直接看结果:

第三轮排序结果.png

• 第四轮排序过程

 //定义待插入的数和索引下标
    insertVal = arr[4]; //这里也就是119
    insertIndex = 4-1; //arr[2]前面数的下标
    //简单说明:
    //1. insertIndex>=0 其主要的目的是为了防止在插入时候为了约束越界
    //2. insertVal < arr[insertIndex]表示待插入的数还没有找到插入的位置如: 34 < arr[] =101
    //3. 需要将 arr[insertIndex]往后移动
    while (insertIndex >=0 && insertVal < arr[insertIndex]){

        arr[insertIndex +1] = arr[insertIndex]; //此时的数组为{101,101,119,1}
        insertIndex --;
    }
    //当退出while循环时,说明插入的位置找到,需要 insertIndex +1 如: 34改为 134
    arr[insertIndex + 1] = insertVal;
    System.out.println("第四轮插入后的结果为:");
    System.out.println(Arrays.toString(arr));

来看测试结果:

第四轮测试结果.png

• 第五轮排序过程:

 //定义待插入的数和索引下标
    insertVal = arr[5]; //这里也就是119
    insertIndex = 5-1; //arr[2]前面数的下标
    //简单说明:
    //1. insertIndex>=0 其主要的目的是为了防止在插入时候为了约束越界
    //2. insertVal < arr[insertIndex]表示待插入的数还没有找到插入的位置如: 34 < arr[] =101
    //3. 需要将 arr[insertIndex]往后移动
    while (insertIndex >=0 && insertVal < arr[insertIndex]){

        arr[insertIndex +1] = arr[insertIndex]; //此时的数组为{101,101,119,1}
        insertIndex --;
    }
    //当退出while循环时,说明插入的位置找到,需要 insertIndex +1 如: 34改为 134
    arr[insertIndex + 1] = insertVal;
    System.out.println("第五轮插入后的结果为:");
    System.out.println(Arrays.toString(arr));

通过五步我们完成了对它的排序过程,期待吧,心累:

第五轮排序结果.png

其实我们也能发现问题,我们要对1进行排序时需要移动的次数太频繁,这样是很耗时的一个操作,当然会影响我们的效率,所以著名的希尔提出了新的算法思想对它进行了优化操作---------->希尔排序思想,首先我们来对它进行一个简单的介绍

希尔排序的介绍

我们都说了,希尔排序排序的本质是插入排序,由希尔本人在1959年提出的算法思想,是对插入排序的完善后的一个高效版本的插入排序,同时也称作为缩小增量排序.

我们通过一张示意图来了解下希尔[排序的过程和思想

希尔排序示意图.png

简单的来说一下上述图解的过程

• 首先我们将上述数组分成步长为5,也就是5组数组,就像图中的一样,同一种颜色为一组如[8,3]为一组.
• 接着对每一组的数据进行插入排序,将小的数字排到了前面,然后在缩小步长也就是5/2 = 2,将数组分成了2组也就是图中所示
• 对步长为2的数组进行插入排序排序之后,继续分组为 2/2 =1 ,也就是图中最后一个我们将数组分为了一组最后进行排序即可.

上述的过程每一次都再缩小步长,我们可以发现从5---->2------>1,最后完成排序,简单的对希尔排序算法的思想进行总结

希尔排序算法的思想

希尔排序就是将一组待排序的数字按下标进行一定增量的分组,对每组直接使用插入排序的算法,随着增量的减少,每组包含的数字也越来越多,当增量减至1时,整个列表被分为一组,也就是我们算法的停止.
假设我有一组待排序的数字如: int [] arr = {8,9,1,7,2,3,5,4,6,0},我们通过代码的方式来完成对它的排序:

代码实现希尔排序算法

• 第一轮的排序实现过程

 //第一轮排序
    //首先将10个数据分成5组了
    int temp = 0;
    for (int i = 5; i<arr.length; i++){
        //内循环的说明:
        //遍历各组中所有的元素(总共5组,每组有2个元素),步长为5如 8 和3为一组,9和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("第一轮的排序结果为:");
    System.out.println(Arrays.toString(arr));

• 来看测试结果:

希尔排序第一轮测试结果.png

• 第二轮的代码实现过程

//第二轮排序
    //在前面5组的基础上进行分5/2 = 2组
    for (int i = 2; i<arr.length; i++){
        //内循环的说明:
        //遍历各组中所有的元素(总共5组,每组有2个元素),步长为5如 8 和3为一组,9和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("第二轮的排序结果为:");
    System.out.println(Arrays.toString(arr));

• 来看测试结果:

  
  希尔排序第二轮测试结果.png
• 第三轮的代码实现过程

 //第三轮排序
    //因为是第三轮排序,我们将10个数字分为2/2 = 1组
    for (int i = 1; i<arr.length; i++){
        //内循环的说明:
        //遍历各组中所有的元素(总共5组,每组有2个元素),步长为5如 8 和3为一组,9和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("第三轮的排序结果为:");
    System.out.println(Arrays.toString(arr));

• 来看测试结果

  
  希尔排序第三轮测试结果.png

之前我们也通过图来了解了该过程,通过三轮的排序我们完成了对该数组的数字从小到大的排序过程,我们对代码来优化下.

代码优化

//希尔排序方法
public static void shellSort(int[] arr){

   //定义一个临时的变量来储存交换的元素
    int temp = 0;
    int count = 0;
    for (int gap = arr.length /2;gap>0; gap /= 2){
        for (int i = gap; i<arr.length; i++){
            //内循环的说明:
            //遍历各组中所有的元素(总共5组,每组有2个元素),步长为gap如 8 和3为一组,9和5为一组等等
            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;
                }
            }
        }
        count ++;
        System.out.println("第"+count+"轮的排序结果为:");
        System.out.println(Arrays.toString(arr));

    }

上述代码是采用交换的一种方式来完成排序,也就是说我们每发现一个就立马进行交换,这种写法其实也没毛病,我们来看下另外一种(移位法)来实现,代码如下,大家可以比较两个算法的好与不好:

• 移位法

//方法优化(移位法)
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 j = i; //交换变量
            int temp = arr[j];
            //表示需要进行位置的交换
            if (arr[j] < arr[j - gap] ){
                while (j -gap >=0 && temp < arr[j-gap]){
                    //移动
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                //当退出循环时,表示给temp找到了插入的位置
                arr[j] = temp;
            }

        }
    }
}

这里就不测试了,我们最后来看下希尔排序的执行时间如何,同样是10W数据的排序,代码如下:

 //插入的时间复杂度测试
    int [] arr = new int[100000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int)(Math.random() * 100000); //随机生成[0,100000)的数
    }

    Date date1 = new Date();
    SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String format = dateFormat.format(date1);
    System.out.println("排序前的时间为:"+format);
    //进行排序
    shellSort(arr);
    Date date2 = new Date();
    SimpleDateFormat dateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String format2 = dateFormat.format(date2);
    System.out.println("排序后的时间为:"+format2);
}

• 测试结果如下:

交换法的执行时间.png

来看下移位法的执行时间

移位法的执行时间结果.png

从上图我们可以看出两个方式算法的执行效率,那么关于希尔算法的学习就到这里了....