type
status
date
slug
summary
tags
category
icon
password

希尔排序 java详细讲解

1、希尔排序法介绍

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序

2、希尔排序法基本思想

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

3、简单插入排序存在的问题

我们看简单的插入排序可能存在的问题. 数组 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} 结论: 当需要插入的数是较小的数时,后移的次数明显增多,对效率有影响.

4、希尔排序法的示意图

notion image
notion image
notion image

5、希尔排序法应用实例:

有一群小牛, 考试成绩分别是 {8,9,1,7,2,3,5,4,6,0} 请从小到大排序. 请分别使用 希尔排序时, 对有序序列在插入时
采用交换法
, 并测试排序速度. 希尔排序时, 对有序序列在插入时
采用移动法
, 并测试排序速度
notion image

6、代码实现(交换法)

package com.qf.sort; import java.util.Arrays; public class ShellSort {    public static void main(String[] args) {        int[] arr={49,38,65,97,76,13,27,49,78,34};        shell(arr);   }    public static void shell(int[] arr){        //第一轮        int temp=0;        for (int i=5;i< arr.length;i++){            for (int j=i-5;j>=0;j=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));        //第二轮        for (int i=2;i< arr.length;i++){            for (int j=i-2;j>=0;j=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));        //第三轮        for (int i=1;i< arr.length;i++){            for (int j=i-1;j>=0;j=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));   } }

7、代码实现(交换法简化)

package com.qf.sort; import java.util.Arrays; public class ShellSort {    public static void main(String[] args) {        int[] arr={49,38,65,97,76,13,27,49,78,34};        shell(arr);   }    public static void shell(int[] arr){        int temp=0;        int count=0;        //步长        for (int gap= arr.length/2;gap>=1;gap=gap/2){            count++;            for (int i=gap;i< arr.length;i++){                //分组                for (int j=i-gap;j>=0;j=j-gap){                    if (arr[j]>arr[j+gap]){                        temp=arr[j];                        arr[j]=arr[j+gap];                        arr[j+gap]=temp;                   }               }           }            System.out.println("第"+count+"轮排序后的数据:");            System.out.println(Arrays.toString(arr));       }   } }

8、代码实现(移动法简化)

package com.qf.sort; import java.util.Arrays; public class ShellSort {    public static void main(String[] args) {        int[] arr={49,38,65,97,76,13,27,49,78,34};        shell2(arr);        System.out.println(Arrays.toString(arr));   }    public static void shell(int[] arr){        int temp=0;        int count=0;        //步长        for (int gap= arr.length/2;gap>=1;gap=gap/2){            count++;            for (int i=gap;i< arr.length;i++){                //分组                for (int j=i-gap;j>=0;j=j-gap){                    if (arr[j]>arr[j+gap]){                        temp=arr[j];                        arr[j]=arr[j+gap];                        arr[j+gap]=temp;                   }               }           }       }   }    public static void shell2(int[] arr){        //增量gap,并且逐步的缩小增量        for (int gap=arr.length/2;gap>=1;gap=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=j-gap;                   }                    arr[j]=temp;               }           }       }   } }
如有不正确的还请支出,谢谢!!!
 
线索化二叉树