原创

(四) 数据结构 - 希尔排序

希尔排序

希尔排序是一种高效的排序算法,它基于插入排序算法。如果较小的值在最右边并且必须移到最左边,则该算法避免了在插入排序的情况下的大移位。

该算法对广泛分布的元素使用插入排序,首先对它们进行排序,然后对间距较小的元素进行排序。该间隔称为间隔。该间隔是根据Knuth的公式计算的(h = h * 3 +1其中-h是初始值为1的间隔)

对于中等大小的数据集,此算法非常有效,因为该算法的平均复杂度和最坏情况的复杂度取决于间隙序列,众所周知,该间隙序列是O(n),其中n是项数。最坏的情况是空间复杂度为O(n)。

核心思想

我们采用与先前示例相同的数组。对于我们的示例和易于理解,我们采用4的间隔。为位于4个位置的间隔的所有值创建一个虚拟子列表。这些值是{35,14},{33,19},{42,27}和{10,44}

Shell Sort

我们比较每个子列表中的值,并在原始数组中交换它们(如果需要)。此步骤之后,新数组应如下所示

Shell Sort

然后,我们取间隔1,此间隔生成两个子列表-{14,27,35,42},{19,10,33,44}

Shell Sort

如果需要,我们将比较并交换原始数组中的值。完成此步骤后,数组应如下所示:

Shell Sort

最后,我们使用值1的间隔对数组的其余部分进行排序。希尔排序使用插入排序对数组进行排序。以下是分步描述-

Shell Sort

我们看到它只需要四个交换就可以对数组的其余部分进行排序。

或可参考:https://blog.csdn.net/qq_28081081/article/details/80598960

代码开发

实现思路

Step 1−初始化h的值步骤
Step 2−将列表分为等间隔h的较小子列表
Step 3−使用插入排序对这些子列表进行排序
Step 4−重复直到对完整列表进行排序

伪代码

package com.paal.demo.c01SortingBasic;

import com.paal.demo.Sort;

/**
 * <p/>
 * <li>title: 基础排序-希尔排序</li>
 * <li>@author: li.pan</li>
 * <li>Date: 2019/11/5 1:41 下午</li>
 * <li>Version: V1.0</li>
 * <li>Description: </li>
 */

public class ShellSort implements Sort {


    @Override
    public void sort(Integer[] arr) {

        int n = arr.length;

        // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
        int h = 1;
        while (h < n / 3) h = 3 * h + 1;

        while (h >= 1) {
            // h-sort the array
            for (int i = h; i < n; i++) {
                // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
                Integer e = arr[i];
                int j = i;
                for (; j >= h && e < arr[j - h]; j -= h)
                    arr[j] = arr[j - h];
                arr[j] = e;
            }
            h /= 3;
        }

    }
}
    /**
     * 希尔排序
     */

    @Test
    public void shellSortTest() {
        Integer[] integers0 = SortTestHelper.generateRandomArray(10001000000);
        Integer[] integers1 = SortTestHelper.generateRandomArray(1000001000000);
        Integer[] integers2 = SortTestHelper.generateRandomArray(10000001000000);
        System.out.println("------------------------------随机数组--------------------------------");
        System.out.println("插入排序测试1数据量为100"+SortTestHelper.testSort(integers0, new InsertionSort()));
        System.out.println("插入排序测试2数据量为10000"+SortTestHelper.testSort(integers1, new InsertionSort()));
        System.out.println("插入排序测试3数据量为100000"+SortTestHelper.testSort(integers2, new InsertionSort()));
        System.out.println("冒泡排序测试1数据量为100"+SortTestHelper.testSort(integers0, new BubbleSort()));
        System.out.println("冒泡排序测试2数据量为10000"+SortTestHelper.testSort(integers1, new BubbleSort()));
        System.out.println("冒泡排序测试3数据量为100000"+SortTestHelper.testSort(integers2, new BubbleSort()));
        System.out.println("希尔排序测试1数据量为100"+SortTestHelper.testSort(integers0, new ShellSort()));
        System.out.println("希尔排序测试2数据量为10000"+SortTestHelper.testSort(integers1, new ShellSort()));
        System.out.println("希尔排序测试3数据量为100000"+SortTestHelper.testSort(integers2, new ShellSort()));
    }

执行结果

------------------------------随机数组--------------------------------
插入排序测试1数据量为100排序时长为: 0.001s
插入排序测试2数据量为10000排序时长为: 0.084s
插入排序测试3数据量为100000排序时长为: 5.868s
冒泡排序测试1数据量为100排序时长为: 0.0s
冒泡排序测试2数据量为10000排序时长为: 0.061s
冒泡排序测试3数据量为100000排序时长为: 9.069s
希尔排序测试1数据量为100排序时长为: 0.0s
希尔排序测试2数据量为10000排序时长为: 0.004s
希尔排序测试3数据量为100000排序时长为: 0.008s

 

正文到此结束
本文目录