python算法与数据结构-希尔排序算法(35)

àì夳堔傛蜴生んèń 2023-10-06 12:53 10阅读 0赞

**阅读目录**

*  [一、希尔排序的介绍][Link 1]
 *  [二、希尔排序的原理][Link 2]
 *  [三、希尔排序的图解　][Link 3]
 *  [四、希尔排序的python代码实现][python]
 *  [五、希尔排序的C语言实现][C]
 *  [六、希尔排序的时间复杂度][Link 4]
 *  [七、希尔排序的稳定性][Link 5]

#### 一、希尔排序的介绍 ####

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的记录越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

#### 二、希尔排序的原理 ####

在前面文章中介绍的直接插入排序，它对于已经基本有序的数据进行排序，效率会很高，而如果对于最初的数据是倒序排列的，则每次比较都需要移动数据，导致算法效率降低。

希尔排序的基本思想就是：将需要排序的序列逻辑上划分为若干个较小的序列**（但并非真的分割成若干分区）**，对这些逻辑上序列进行直接插入排序，通过这样的操作可使需要排序的数列基本有序，最后再使用一次直接插入排序。

在希尔排序中首先要解决的是怎样划分序列，对于子序列的构成不是简单地分段，而是采取将相隔某个增量的数据组成一个序列。一般选择增量的规则是：**取上一个增量的一半作为此次子序列划分的增量，一般初始值元素的总数量的一半。**

#### 三、希尔排序的图解　 ####

![format_png][]

![format_png 1][]

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

#### 四、希尔排序的python代码实现 ####

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

# 创建一个希尔排序的函数
    def shell_sort(alist):
        # 需要排序数组的个数
        N = len(alist)
        # 最初选取的步长
        gap = N//2
        
        # 根据每次不同的步长，对分组内的数据进行排序
        # 如果步长没有减为1就继续执行
        while gap>0:
            # 对每个分组进行插入排序，
            # 因为插入排序从第二个元素开始，而这里第二个元素的下标就是gap
            # 所以i的起始点是gap
            for i in range(gap,N):
                # 控制每个分组内相邻的两个元素,逻辑上相邻的两个元素间距为gap，
                # j的前一个元素比它少一个gap距离，所以for循环中j的步长为 -gap
                for j in  range(i,0,-gap):
                    # 判断和逻辑上的分组相邻的两个数据大小
                    if alist[j]<alist[j-gap] and j-gap>=0:
                        # 交换
                        temp = alist[j]
                        alist[j] = alist[j-gap]
                        alist[j-gap] = temp
            # 改变步长
            gap = gap//2
        
        
    numlist = [5,7,8,3,1,2,4,6,9]
    print("排序前：%s"%numlist)
    shell_sort(numlist)
    print("排序后：%s"%numlist)

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

运行结果为：

排序前：[5, 7, 8, 3, 1, 2, 4, 6, 9]
    排序后：[1, 2, 3, 4, 5, 6, 7, 8, 9]

#### 五、希尔排序的C语言实现 ####

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

#include <stdio.h>
    // 创建一个希尔排序的函数
    void shell_sort(int arr[],int arrLength,int gap)
    {
        // 根据每次不同的步长，对分组内的数据进行排序
        // 如果步长没有减为1就继续执行
        while (gap>0)
        {
            // 对每个分组进行插入排序，
            // 因为插入排序从第二个元素开始，而这里第二个元素的下标就是gap，
            // 所以i的起始点是gap
            for (int i = gap; i<arrLength; i++)
            {
                // 控制每个分组内相邻的两个元素,逻辑上相邻的两个元素间距为gap，
                // j的前一个元素比它少一个gap距离，所以for循环中j每次减少一个gap
                // 因为j-gap是上一个元素的下标，也必须保证大于等于0
                for (int j = i; j>0&&j-gap>=0; j=j-gap)
                {
                    // 判断和逻辑上的分组相邻的两个数据大小
                    if (arr[j]<arr[j-gap])
                    {
                        // 交换
                        int temp = arr[j];
                        arr[j] = arr[j-gap];
                        arr[j-gap] = temp;
                    }
                }
            }
            gap = gap/2;
        }
    }
    
    int main(int argc, const char * argv[]) {
       
        // 定义数组
        int array[] = {5,7,8,3,1,2,4,6,9};
        // 希尔排序的声明
        void shell_sort(int arr[],int arrLength,int gap);
        // 计算数组长度
        int len = sizeof(array)/sizeof(int);
        // 制定gap为二分之一的长度
        int g = len/2;
        // 使用希尔排序
        shell_sort(array, len, g);
        // 验证
        for (int i = 0; i<len; i++)
        {
            printf("%d ",array[i]);
        }
        
        return 0;
    }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

运行结果为：

1 2 3 4 5 6 7 8 9

#### 六、希尔排序的时间复杂度 ####

*  最优时间复杂度：根据步长序列的不同而不同
 *  最坏时间复杂度：O(n2)

#### 七、希尔排序的稳定性 ####

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

![format_png 7][]

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

侯哥语录：我曾经是一个职业教育者，现在是一个自由开发者。我希望我的分享可以和更多人一起进步。分享一段我喜欢的话给大家："我所理解的自由不是想干什么就干什么，而是想不干什么就不干什么。当你还没有能力说不得时候，就努力让自己变得强大，拥有说不得权利。"

来源:[https://www.cnblogs.com/Se7eN-HOU/p/11079526.html][https_www.cnblogs.com_Se7eN-HOU_p_11079526.html]

[Link 1]: https://www.cnblogs.com/Se7eN-HOU/p/11079526.html#_label0
[Link 2]: https://www.cnblogs.com/Se7eN-HOU/p/11079526.html#_label1
[Link 3]: https://www.cnblogs.com/Se7eN-HOU/p/11079526.html#_label2
[python]: https://www.cnblogs.com/Se7eN-HOU/p/11079526.html#_label3
[C]: https://www.cnblogs.com/Se7eN-HOU/p/11079526.html#_label4
[Link 4]: https://www.cnblogs.com/Se7eN-HOU/p/11079526.html#_label5
[Link 5]: https://www.cnblogs.com/Se7eN-HOU/p/11079526.html#_label6
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvNzUxNzU0LzIwMTkwNi83NTE3NTQtMjAxOTA2MjQyMDA2MzU4MjYtMjAxODgzMDY2OS5wbmc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvNzUxNzU0LzIwMTkwNi83NTE3NTQtMjAxOTA2MjQyMDA3MDQ0MjEtMTA5Mjg4OTM2NC5wbmc?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvNzUxNzU0LzIwMTkwNi83NTE3NTQtMjAxOTA2MjQyMDA3NTMwMjItMTcyNjkzNDcxNC5wbmc?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvNzUxNzU0LzIwMTkwNi83NTE3NTQtMjAxOTA2MjQyMDEyMDQwNzItMTc1NzU2NDU1LnBuZw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvNzUxNzU0LzIwMTkwNi83NTE3NTQtMjAxOTA2MjQyMDEyNDk4MTAtMjQwMDYzNDMzLnBuZw?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvNzUxNzU0LzIwMTkwNi83NTE3NTQtMjAxOTA2MjQyMDEzMjk5MDYtOTc2NjI0OTgxLnBuZw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvNzUxNzU0LzIwMTkwNi83NTE3NTQtMjAxOTA2MjQyMDE0MDI4NDMtNTI2ODc3NjQ5LnBuZw?x-oss-process=image/format,png
[aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvNzUxNzU0LzIwMTkwNi83NTE3NTQtMjAxOTA2MjQyMTExMjQxODUtMjMzODYxMzkyLnBuZw?x-oss-process=image/format,png
[https_www.cnblogs.com_Se7eN-HOU_p_11079526.html]: https://www.cnblogs.com/Se7eN-HOU/p/11079526.html