希尔排序算法

偏执的太偏执、 2023-01-21 02:15 34阅读 0赞

**希尔排序**（Shell sort）是插入排序的一种又称"**缩小增量排序**",是直接**插入排序算法**的一种**更高率的改进版本**。**希尔排序是非稳定算法**。

为什么不稳定呢？举例子：3   5  10   8   7   2  8   1  20  6 现在d=2（3  10 7  8  20）和（5  8  2  1   6），原本相同的数据（如两个8，可以记为 8' ,8")但是经过排序后变成（8",8')不稳定的意思不是出错的意思。

## 1、排序原理 ##

*  选定一个增量h（一般是数组长度的一半），**按照增量h作为数据分组的依据**，对数据进行分组。
 *  对分好组的**每一组数据****完成插入排序**。
 *  减小增量，最小减为1，重复上述第二步。

## 2、算法分析过程 ##

**图解**其他排序的**过程原理**：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70][]

动态图演示过程：

![20210514001036567.gif][]

## 3、Java代码实现 ##

import java.util.Arrays;
    
    public class Shell {
        public static void main(String[] args) {
            System.out.println("排序前：");
            Integer [] a =new Integer[]{89,45,68,90,29,34,17};
            System.out.println(Arrays.toString(a));
            System.out.println("排序过程：");
            sort(a);
            //System.out.println(Arrays.toString(a));
        }
        public static void sort(Comparable []a){
            int h = a.length/2;
            while(h>=1){
                for(int i=h;i<a.length;i++){
                    for(int j=i;j>=h;j-=h){
                        if(isGreater(a[j-h],a[j])){
                            Exchange(a,j-h,j);
                            System.out.println(Arrays.toString(a));
                        }else {
                            break;
                        }
                    }
                }
                h/=2;
            }
        }
        /**
         * 交换
         * @param a
         * @param i
         * @param j
         */
        public static  void Exchange(Comparable []a,int i,int j){
            Comparable temp;
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    
        /**
         * 判断
         * @param c1
         * @param c2
         * @return
         */
        public static boolean isGreater(Comparable c1,Comparable c2){
            return c1.compareTo(c2)>0;
        }
    }

运行截图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 1][]

其中最关键的部分：

通过图解过程：发现每一次**没有排序**（**需要插入到已经排序中**）的开始第一个元素都是在**下标为h处**，（**前面是已经排序的，后面是未排序的**）而且每一组进行插入排序时（**每个元素之间（下标）相差h**）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 2][]

public static void sort(Comparable []a){
            int h = a.length/2;
            while(h>=1){
                for(int i=h;i<a.length;i++){
                    for(int j=i;j>=h;j-=h){
                        // j-h 和 j是同一组的数据，进行插入排序
                        if(isGreater(a[j-h],a[j])){
                            Exchange(a,j-h,j);
                            System.out.println(Arrays.toString(a));
                        }else {
                            break;
                        }
                    }
                }
                h/=2;
            }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70]: /images/20221021/4af6b81d1a804225bd88e48975d55561.png
[20210514001036567.gif]: /images/20221021/d5c2b937276348499b71cfd46b3ddfe6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 1]: /images/20221021/52191036b67f4bd395c5314ea7fc1c78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 2]: /images/20221021/1d06fffb7eda4c6f86f0308700688440.png