网络知识 娱乐 希尔排序算法

希尔排序算法

ced485cbb11e458d81a746890b32cf3f.gif

作者:敲代码の流川枫

博客主页:流川枫的博客

专栏:和我一起学java

语录:Stay hungry stay foolish

工欲善其事必先利其器,给大家介绍一款超牛的斩获大厂offer利器——牛客网

点击免费注册和我一起刷题吧    

文章目录

1. 算法思想

2. 算法图解

3. 代码实现

4. 算法特点


插入排序算法详解

1. 算法思想

希尔排序是一种基于插入排序的快速的排序算法。简单插入排序对大规模乱序数组很慢,元素之恩那个一点一点从数组一端移动到另一端

为了解决这个问题,希尔排序改进了插入排序,称为缩小增量排序,该算法也是突破O(n*n)的第一批算法之一

主要思想是:把数据按照一定增量分组,对每组使用直接插入排序算法,然后缩小增量继续分组排序,随着增量逐渐减小,每组包含的关键词越来越多,增量减小至1时,整个数组被分为一组,再次排序,完成整个数组的排序,这个不断缩小的增量构成了增量序列

常用的增量序列有:

2. 算法图解

int[] array = {77,20,31,5,8,9,11,33,22,88,99,35};

以数组array排升序为例:

希尔排序图解

第一个增量为6,则原始数组被分为6组,组内的每个元素下标之差为6,然后对这6组进行插入排序

第二个增量为3,则第一次排序后数组被分为三组,组内每个元素之间数组下标之差为3 ,这三组分别进行插入排序

第三个增量为1,则第二次排序后数组被分为1组,进行插入排序

结果为:

至此希尔排序完成

3. 代码实现

代码:

import java.util.Arrays;

public class ShellSort {
    public int[] sortArray(int[] nums){
        int len = nums.length;
        //按增量分组后,每个分组中temp代表当前待排序数据,该元素之前的组内元素均已被排过
        //gap只用来分组的增量,会依次递减
        int currentValue,gap = len / 2;
        while(gap>0){
            for (int i = gap; i =0 && nums[preIndex] > currentValue){
                    nums[preIndex+gap]=nums[preIndex];
                    preIndex -= gap;
                }
                //当while循环结束时,说明找到了当前待排序数据的合适位置插入数据
                nums[preIndex+gap] = currentValue;
            }
            System.out.println("本轮增量:"+gap+"     排序后的数组:");
            PrintArray.print(nums);
            System.out.println("----------");
            gap/=2;
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] array = {77,20,31,5,8,9,11,33,22,88,99,35};
        ShellSort shellSort = new ShellSort();
        shellSort.sortArray(array);
    }
}
class PrintArray{
    public static void print(int[] nums){
        System.out.println(Arrays.toString(nums));
    }
}

4. 算法特点

时间复杂度:n和d的函数:O(n^1.25)~  O(1.6n^1.25)

空间复杂度: O(1)

希尔排序每一趟移动,移动位置较大,跳跃式地接近排序后的最终位置
增量序列必须是递减的,最后一个必须是1(对整体进行直接插入排序)
希尔排序是一种不稳定的排序方法,且不宜在链式存储结构上实现
希尔排序通过降低比较次数和移动次数来提高排序的效率

“ 本期的分享就到这里了, 记得给博主一个三连哈,你的支持是我创作的最大动力!

ced485cbb11e458d81a746890b32cf3f.gif