5.希尔排序

算法 > 排序算法排序算法算法

发布时间 : 2024-04-14 17:43

字数:2.5k 阅读 :

评论:

5.希尔排序

5.希尔排序

5.1 基础知识

核心思想

希尔排序是插入排序的一种改进版本，通过引入步长将元素分成子序列，对子序列进行插入排序，逐渐减小步长，最终达到对整体的基本有序，从而提高插入排序的效率。

算法步骤

选择步长：选择一个初始的步长值，通常为数组长度的一半，并逐步减小步长。
分组插入排序：将数组按照步长分成若干子序列，对每个子序列进行插入排序。
逐步减小步长：缩小步长，重复步骤2，直至步长为1。此时，数组近乎有序，最后进行一次插入排序即可完成排序。

时间复杂度

希尔排序的时间复杂度取决于步长序列的选择，一般介于 O(n log n) 和 O(n^2) 之间，在实践中比插入排序更快，尤其对于大规模数据集。

空间复杂度

希尔排序是一种原地排序算法，空间复杂度为 O(1)。

稳定性

希尔排序是不稳定的，因为相同元素可能会在不同的子序列中发生位置交换。

适用场景

希尔排序适用于中等规模的数据集，特别是在相对有序的情况下表现较好，对于大规模数据的初步排序也有一定的优势。

代码步骤

外层循环（步长选择）：通过外层循环控制步长的选择，初始步长为数组长度的一半，每轮循环减半直至步长为1。
内层循环（插入排序）：对每个子序列进行插入排序，从第一个子序列的第 step 个元素开始，逐个向后取元素进行插入排序。
当前待插入元素：在每一轮开始时，将当前待插入的元素记录为 currentElement。
内层循环找插入位置：通过内层循环，在当前子序列已排序区域中寻找合适的插入位置，每次比较的元素相隔一个步长。
插入当前元素：找到合适的插入位置后，将 currentElement 插入到已排序区域的正确位置。
输出插入后的数组：在每次插入后，输出当前数组的状态，显示排序的过程。
重复直到完成：不断重复上述步骤，直到整个数组完全有序。

总结说明

希尔排序通过引入步长的方式改进插入排序，在某些情况下对大规模数据排序具有良好性能，尽管不稳定，但在实际应用中仍值得考虑。

5.2 思路框架

static void ShellSort(ref int[] array)
{
    循环：根据步长，步长初始化为数组长度的一半，逐步减半直至步长为1
    {
        循环：从步长开始遍历数组直至数组末尾（差不多相当于插入排序，跨越部分改成步长）
        {
            将当前元素保存到临时变量中
            
            定义指针，用于比较当前元素和已排序部分的元素，初始值是当前元素索引减去步长

            循环：将当前元素与已排序部分的元素逐个比较并移动，只要指针没越界且当前元素值比排序区的小就一直移动
            {
                覆盖当前指针加上步长的元素值且指针往前移一个步长
            }

            出循环代表找到合适的插入位置，将当前元素值覆盖到指针加上步长的元素中
        }
    }
}

5.3 纯净代码

static void ShellSort(ref int[] array)
{
    for (int step = array.Length / 2; step > 0; step /= 2)
    {
        for (int i = step; i < array.Length; i++)
        {
            int currentElement = array[i];
            int j = i - step;

            while (j >= 0 && array[j] > currentElement)
            {
                array[j + step] = array[j];
                j -= step;
            }

            array[j + step] = currentElement;
        }
    }
}

require("Lesson01_SortHelpTool")  
  
-- 希尔排序函数  
function ShellSort(array)  

    local arrayLength = #array  
    local step = math.floor(arrayLength / 2)  
  
    while step > 0 do  
        
        for i = step + 1, arrayLength do  

            local currentElement = array[i]  
            local j = i - step  
  
            while j >= 1 and array[j] > currentElement do  
                array[j + step] = array[j]  
                j = j - step  
            end  
  
            array[j + step] = currentElement  
        end  
  
        step = math.floor(step / 2)  
    end  
end  
  
SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序前")  
  
ShellSort(SortHelpTool.arrayToSort)  
  
SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序后")

5.4 带注释代码

using System;
using Lesson01_概述;

class Program
{
    static void Main()
    {
        // 输出排序前的数组
        Console.WriteLine("排序前的数组:");
        SortHelpTool.PrintArray(SortHelpTool.arrayToSort);

        // 调用希尔排序函数
        ShellSort(ref SortHelpTool.arrayToSort);

        // 输出排序后的数组
        Console.WriteLine("排序后的数组:");
        SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
    }

    // 希尔排序函数
    static void ShellSort(ref int[] array)
    {
        // 希尔排序第几轮计数标识
        int shellSortTimes = 0;

        // 外层循环负责选择步长。在每个循环迭代中，gap 的值会缩小一半。
        // 初始步长 gap 被设置为数组长度的一半。这个步长将逐步缩小，直至为1。
        for (int step = array.Length / 2; step > 0; step /= 2)
        {
            // 新的一轮希尔排序开始
            shellSortTimes++;
            Console.WriteLine($"第{shellSortTimes}轮希尔排序开始，步长为{step}");

            // 对每个子序列进行插入排序，代表取出来的未排序区的第一个元素，也可以理解为从第一个子序列的第二个元素开始。
            for (int i = step; i < array.Length; i++)
            {
                // 当前待插入元素
                int currentElement = array[i];

                // i-step代表当前子序列从已排序区的末尾开始比较，子序列步长是一个步长step，所以减去step
                int j = i - step;

                // 在当前子序列已排序区寻找插入位置，只要未到当前子序列已排序区头，且当前子序列比较的已排序区元素大于当前待排序元素，就继续往前移动一个步长比较子序列元素，找到合适的子序列位置插入
                while (j >= 0 && array[j] > currentElement)
                {
                    // 移动子序列元素到上一个子序列元素，为当前元素腾出插入位置
                    array[j + step] = array[j];
                    // 继续往前移动一个步长比较比较
                    j -= step;
                }

                // 插入当前元素到正确子序列位置，j+step是因为while中将比currentElement大的子序列元素都向后移动了一个步长位置并让j -= step继续往前和前一个子序列元素进行比较，所以插入位置就是j+step。
                array[j + step] = currentElement;

                // 输出排序中的数组
                Console.WriteLine($"排序第{i % step + 1}子序列 插入元素{currentElement}到正确位置 插入后的数组:");
                SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
            }

            Console.WriteLine($"第{shellSortTimes}希尔排序结束");
        }
    }
}

5.5 运行结果

排序前的数组:
5 2 8 1 7 3 10 4 6 9

第1轮希尔排序开始，步长为5
排序第1子序列插入元素3到正确位置插入后的数组:
3 2 8 1 7 5 10 4 6 9
排序第2子序列插入元素10到正确位置插入后的数组:
3 2 8 1 7 5 10 4 6 9
排序第3子序列插入元素4到正确位置插入后的数组:
3 2 4 1 7 5 10 8 6 9
排序第4子序列插入元素6到正确位置插入后的数组:
3 2 4 1 7 5 10 8 6 9
排序第5子序列插入元素9到正确位置插入后的数组:
3 2 4 1 7 5 10 8 6 9
第1希尔排序结束

第2轮希尔排序开始，步长为2
排序第1子序列插入元素4到正确位置插入后的数组:
3 2 4 1 7 5 10 8 6 9
排序第2子序列插入元素1到正确位置插入后的数组:
3 1 4 2 7 5 10 8 6 9
排序第1子序列插入元素7到正确位置插入后的数组:
3 1 4 2 7 5 10 8 6 9
排序第2子序列插入元素5到正确位置插入后的数组:
3 1 4 2 7 5 10 8 6 9
排序第1子序列插入元素10到正确位置插入后的数组:
3 1 4 2 7 5 10 8 6 9
排序第2子序列插入元素8到正确位置插入后的数组:
3 1 4 2 7 5 10 8 6 9
排序第1子序列插入元素6到正确位置插入后的数组:
3 1 4 2 6 5 7 8 10 9
排序第2子序列插入元素9到正确位置插入后的数组:
3 1 4 2 6 5 7 8 10 9
第2希尔排序结束

第3轮希尔排序开始，步长为1
排序第1子序列插入元素1到正确位置插入后的数组:
1 3 4 2 6 5 7 8 10 9
排序第1子序列插入元素4到正确位置插入后的数组:
1 3 4 2 6 5 7 8 10 9
排序第1子序列插入元素2到正确位置插入后的数组:
1 2 3 4 6 5 7 8 10 9
排序第1子序列插入元素6到正确位置插入后的数组:
1 2 3 4 6 5 7 8 10 9
排序第1子序列插入元素5到正确位置插入后的数组:
1 2 3 4 5 6 7 8 10 9
排序第1子序列插入元素7到正确位置插入后的数组:
1 2 3 4 5 6 7 8 10 9
排序第1子序列插入元素8到正确位置插入后的数组:
1 2 3 4 5 6 7 8 10 9
排序第1子序列插入元素10到正确位置插入后的数组:
1 2 3 4 5 6 7 8 10 9
排序第1子序列插入元素9到正确位置插入后的数组:
1 2 3 4 5 6 7 8 9 10
第3希尔排序结束

排序后的数组:
1 2 3 4 5 6 7 8 9 10

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com