希尔排序算法

​

文章目录

1. 算法思想
2. 算法图解
3. 代码实现
4. 算法特点

插入排序算法详解

1. 算法思想

常用的增量序列有：

1. 算法图解

int[] array = {77,20,31,5,8,9,11,33,22,88,99,35};
以数组array排升序为例：

希尔排序图解

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

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

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

结果为：

至此希尔排序完成

1. 代码实现

代码：

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 < len; i++) {
            currentValue = nums[i];
            //组内已被排序数据的索引
            int preIndex = i - gap;
            //在组内已被排序过的数据中倒序寻找合适的位置，如果当前待排序数据比比较的元素要小，
            // 则将比较的元素在组内后移一位
            while(preIndex>=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));
}

}

1. 算法特点

时间复杂度:n和d的函数：O（n^1.25）~  O（1.6n^1.25）

空间复杂度: O（1）

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

​