高级排序---希尔排序（常见经典排序算法）

忘是亡心i 2023-10-14 12:26 4阅读 0赞

>  **一、原理：** 
> 
> 希尔排序又叫缩小增量排序，也是一种插入排序方法(通常快于直接插入法)，具体做法是将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序;
> 
>  **二、步骤：** 
> 
> 1.先选定一个小于数组长度的整数gap（步长）作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作...
> 
> 2.当增量的大小减到1时，就相当于整个序列被分到一组，进行步长为1的直接插入排序，排序完成。
> 
>  **增量（步长）说明：**  对于增量的选定无一定论，但最后一个增量必须等于1，也就是说，每趟后一个增量是前一个增量的1/2或1/3（自定义，最好是1/2）。
> 
>  **编程步骤：** 
> 
>  **用for-for-while嵌套循环，最外层for循环设置步长增量，然后里面的for-while循环和插入排序一样，将每组的元素进行排序。** 
> 
>  **三、平均时间复杂度：O（ ![n^\{1.3\}][n_1.3] ）**

###  **希尔排序图片展示：**  ###

![21205827_67Q2.gif][]

![21205827_ukgV.png][]

![21205828_T4BJ.png][]

![21205828_CSuo.png][]

import java.util.Arrays;
    
    public class ShellSort {
        public static void main(String[] args) {
            int[] arr = {3, 45, 78, 99, 45, 64, 55, 52, 11, 18, 66, 17, 37, 199, 120, 54, 49};
            System.out.println("未排序数组："+ Arrays.toString(arr));
           shellSort(arr);
            System.out.println("已排序数组："+Arrays.toString(arr));
        }
    
        //希尔排序和插入排序相似，多了一个循环进行分组排序
        public static void shellSort(int[] arr){
            //步长  gap
            for (int gap=arr.length/2;gap>0;gap /=2){//步长可以自定义，可以除2也可以除3...（下面步骤和插入排序步骤一样）
                for (int i=gap;i<arr.length;i+=gap){//每次增加一个步长的长度
                    int insertIndex = i;
                    int insertValue = arr[i];
                    while (insertIndex-gap >= 0 && insertValue < arr[insertIndex - gap]){
                        arr[insertIndex] = arr[insertIndex - gap];
                        insertIndex -= gap;
                    }
                    arr[insertIndex] = insertValue;
                }
            }
        }
    }

[n_1.3]: https://static.oschina.net/uploads/img/202206/21205827_JOZ4.jpg
[21205827_67Q2.gif]: https://static.oschina.net/uploads/img/202206/21205827_67Q2.gif
[21205827_ukgV.png]: https://static.oschina.net/uploads/img/202206/21205827_ukgV.png
[21205828_T4BJ.png]: https://static.oschina.net/uploads/img/202206/21205828_T4BJ.png
[21205828_CSuo.png]: https://static.oschina.net/uploads/img/202206/21205828_CSuo.png