2021-10-10

• 希尔排序
• • • 1、什么是希尔排序：
    • 2、希尔排序的代码示例
    • 3、时间复杂度分析及稳定性
    • 4、希尔排序如何选择自己的增量
    • 5、验证

希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。
希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。
它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。
希尔排序是改进的直接插入排序，运用了插入排序的思想，但是比插入排序要好。
好在两个方面：
1、当shell排序的间隔较大的时候，排列比较的次数较少。
2、当shell排序的间隔较小的时候，排列移动的距离比较短。

    //shell排序
    static void shell(int[] arr){
         //flag作为增量
        for(int flag = 4; flag>0;flag/=2){
            for(int i = flag;iflag-1;j-=flag){
                    if(arr[j] 
3、时间复杂度分析及稳定性 
时间复杂度 ：O（n^1.3）
 最好情况下：O（n）
 最坏情况下：O（n^2）
 空间复杂度：O（1）
 
稳定性：不稳定
 
4、希尔排序如何选择自己的增量 
改进：使用Knuth序列：
 1、h=1;
 2、h=3*h+1
 
 //shell排序
    static void shell(int[] arr){
        int h = 1;
        while(h<=arr.length/3){
            h = h*3+1;
        }
        for(int flag = h; flag>0;flag = (flag-1)/3){
            for(int i = flag;iflag-1;j-=flag){
                    if(arr[j] 
5、验证 
因为排序次数少或者原始数据较少可能会产生偶然性，应该编写程序验证排序算法的正确性。
 
package Sort;

import java.util.Arrays;
import java.util.Random;

public class shellSort {
    public static void main(String[] args) {
        check();
    }

    //shell排序
    static void shell(int[] arr){
        int h = 1;
        while(h<=arr.length/3){
            h = h*3+1;
        }
        for(int flag = 4; flag>0;flag = (flag-1)/3){
            for(int i = flag;iflag-1;j-=flag){
                    if(arr[j]