希尔排序（缩小增量排序）算法

- 日理万妓 2024-04-08 11:29 38阅读 0赞

### 基本思想 ###

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

### 算法描述 ###

1.  首先选取一个间隙序列，如 (n/2，n/4 … 1)，n 为数组长度
2.  每一轮将间隙相等的元素视为一组，对组内元素进行插入排序，目的有二
    
    ① 少量元素插入排序速度很快
    
    ② 让组内值较大的元素更快地移动到后方
3.  当间隙逐渐减少，直至为 1 时，即可完成排序

### 算法代码 ###

/**
     * @author pzz
     * @date 2022/8/23
     * 希尔排序
     */
    public class Shell {
        
        public static void main(String[] args) {
        
            int[] a = {
        7, 5, 19, 8, 4, 1};
            shell(a);
        }
    
        private static void shell(int[] a){
        
            //数组的长度
            int n = a.length;
            //遍历每个间隙组
            for (int gap = n / 2;gap > 0;gap /= 2){
        
                //遍历间隙组内的每个元素
                for(int i = gap;i < n;i++){
           //i表示插入元素的索引
                    //待插入的值
                    int t = a[i];
                    int j = i;
                    while(j >= gap){
        
                        //每次与上一个间隙为gap的元素进行插入排序（同一个gap间隙的为一组，然后组内进行插入排序）
                        if(t < a[j - gap]){
           // j-gap 是上一个元素索引，如果 > t，后移
                            a[j] = a[j - gap];
                            j -= gap;
                        }else{
           //如果 j-1 已经 <= t, 则 j 就是插入位置
                            break;
                        }
                    }
    
                    a[j] = t;
                    System.out.println(Arrays.toString(a) + " gap:" + gap);
                }
            }
        }
    }

结束！！

--------------------

或许最大的烦恼就是没钱