Java数据结构与算法中的排序算法(六)希尔排序法详解

  当需要插入的数是较小的数时,我们之前使用的插入排序的算法,后移的次数就会明显增多,因此可以使用希尔排序,希尔排序也是一种插入排序,它是简单插入排序经过改进之后的,也称为缩小增量排序。

希尔排序的基本思想:

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

  希尔排序可以使用交换法,也可以使用移动法,这里都给大家介绍一下:

首先是交换法:

    public static void shellsort(int[] arr) {        //使用循环处理        int temp = 0;        int x = 0;        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {            x++;            for (int i = gap; i < arr.length; i++) {                //遍历各组中所有的元素(共gap组,每组有个arr.length/gap元素),步长为gap                for (int j = i - gap; j >= 0; j--) {                    //如果当前元素大于加上步长后的元素,说明需要交换                    if (arr[j] > arr[j + gap]) {                        temp = arr[j];                        arr[j] = arr[j + gap];                        arr[j + gap] = temp;                    }                }            } //           System.out.println("希尔排序第" + x + "轮后" + Arrays.toString(arr));        }    }

遍历各组中所有的元素(共gap组,每组有个arr.length/gap元素),步长为gap,如果当前元素大于加上步长后的元素,说明需要交换。

   举个例子来看,可以分轮进行具体验证:

Java数据结构与算法中的排序算法(六)希尔排序法详解

但是当我们使用大批量数据运行时,较慢,因此通常使用移动法:

    //对交换式的希尔排序法进行优化    public static void  shellsort2(int[] arr){        for (int gap = arr.length / 2; gap > 0; 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;                    }                    //当退出while循环后,就给temp找到插入位置                    arr[j] = temp;                }            }        }    }

用大批量数据进行验证:

Java数据结构与算法中的排序算法(六)希尔排序法详解

发现运行时间远远小于交换法,因为交换法中用了三层循环。

来源:琢磨先生DataBase,本文观点不代表自营销立场,网址:https://www.zyxiao.com/p/125759

发表评论

登录后才能评论
侵权联系
返回顶部