希尔排序

作者: 程序员will | 来源:发表于2019-10-31 16:13 被阅读0次

    希尔排序 (Shell Sort)

    算法原理

    希尔排序算法是按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布,是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步(增量较大)间隔比较,使记录跳跃式接近它的排序位置;然后增量缩小;最后增量为 1 ,这样记录移动次数大大减少,提高了排序效率。希尔排序对增量序列的选择没有严格规定。

    希尔排序是基于插入排序的以下两点性质而提出改进方法的:

    • 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
    • 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位

    算法思路:

    1. 先取一个正整数 d1(d1 < n),把全部记录分成 d1 个组,所有距离为 d1 的倍数的记录看成一组,然后在各组内进行插入排序
    2. 然后取 d2(d2 < d1)
    3. 重复上述分组和排序操作;直到取 di = 1(i >= 1) 位置,即所有记录成为一个组,最后对这个组进行插入排序。一般选 d1 约为 n/2,d2 为 d1 /2, d3 为 d2/2 ,…, di = 1。

    算法图解

    Image result for 希尔排序 gif"

    代码实现

    public class ShellSort implements IArraySort {
    
        @Override
        public int[] sort(int[] sourceArray) throws Exception {
            // 对 arr 进行拷贝,不改变参数内容
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    
            int gap = 1;
            while (gap < arr.length) {
                gap = gap * 3 + 1;
            }
    
            while (gap > 0) {
                for (int i = gap; i < arr.length; i++) {
                    int tmp = arr[i];
                    int j = i - gap;
                    while (j >= 0 && arr[j] > tmp) {
                        arr[j + gap] = arr[j];
                        j -= gap;
                    }
                    arr[j + gap] = tmp;
                }
                gap = (int) Math.floor(gap / 3);
            }
    
            return arr;
        }
    }
    

    相关文章

      网友评论

        本文标题:希尔排序

        本文链接:https://www.haomeiwen.com/subject/qyytbctx.html