程序猿修仙之路--算法之希尔排序-阿里云开发者社区

开发者社区> Golang语言社区> 正文

程序猿修仙之路--算法之希尔排序

简介:

IT江湖

自冯诺依曼开启大计算机时代以来,经过近一个世纪的蓬勃发展,已然成为一个人才众多的群体:IT江湖
依附市场规律,江湖上悄然兴起数十宗门,其中以AI,大数据近期最为热门。每个宗门人才济济,抢夺人才大战早已在阿里,腾讯,百度等数百个国度白热化。
IT江湖人士凭借JAVA,Python等武器,在精通各路内功心法的基础上在各个国度扬名立万,修仙成佛者众多,为后人树下追宠之榜样。
内功心法众多,其中以算法最为精妙,是修仙德道必经之路。
虽然江湖上算法内功繁多,但是好的算法小编认为必须符合以下几个条件,方能真正提高习练者实力:
时间复杂度(运行时间)
在算法时间复杂度维度,我们主要对比较和交换的次数做对比,其他不交换元素的算法,主要会以访问数组的次数的维度做对比。。
其实有很多修炼者对于算法的时间复杂度有点模糊,分不清什么所谓的 O(n),O(nlogn),O(logn)...等,也许下图对一些人有一些更直观的认识。
7156c86d5e53bcd02f627bf05c917f9672a24cf6
空间复杂度(额外的内存使用)
排序算法的额外内存开销和运行时间同等重要。 就算一个算法时间复杂度比较优秀,空间复杂度非常差,使用的额外内存非常大,菜菜认为它也算不上一个优秀的算法。
结果的正确性
这个指标是菜菜自己加上的,我始终认为一个优秀的算法最终得到的结果必须是正确的。就算一个算法拥有非常优秀的时间和空间复杂度,但是结果不正确,导致修炼者经脉逆转,走火入魔,又有什么意义呢?
算法虽然精妙,但需循序渐进修炼,并且需要一定的数学内功基础方可彻底领悟。今日习练算法第三章:排序之希尔排序
气运丹田 开启修炼之路
心法简介
上一篇我们修炼了插入排序,希尔排序(又名Shell's Sort)本质上属于插入排序,是插入排序的一种更高效升级版本,也称为**缩小增量排序**。同时希尔排序在时间复杂度上也是突破O(n²)的第一批算法之一。你说厉不厉害?~~
心法基本思想

通过直接插入排序的修炼,我们知道直接插入排序是一种性能比较低的初级算法,对修炼者提升不是不大, 但是有一点优势那就是对于小型数组或者部分有序的数组非常高效,希尔排序就是基于这一点优势对直接插入排序进行了改良。换句话说直接插入排序低效的原因在于无序,无序的程度越高越低效。例如:最小的元素初始位置在数组的另一端,此元素要想到达正确位置,是需要一个一个位置前移,最终需要N-1次移动。如何改变这种状态正是希尔排序的突破口。

希尔排序的思想是把数组下标按照一定的增量h分组,然后对每组进行直接插入排序。在进行排序时,如果h很大,我们就能将元素移动到很远的地方,为实现更小的h有序创造方便。然后增量h逐渐减小(每个分组的元素量增多),直到h为1整个数组划分为一组,排序结束。

也许一张更直观的图比上千句话效果都好

8aae215db179b0efdef91cd98b67665b25becb5b

心法复杂度
时间复杂度
最坏时间复杂度依然为O(n²),一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n^3/2),最好情况下为O(n)属于线性复杂度。
空间复杂度
优于希尔排序本质上属于插入排序升级版,所以空间上和直接插入排序一致为O(1),在常数级别。
性能和特点
希尔排序之所以高效是因为它权衡了子数组的规模和有序性。排序之初各个子数组都很短,这种情况很适合插入排序.
对于增量h的选择对希尔排序非常重要,直接影响其性能。其实除了h的选择之外,h之间的数学性质也影响希尔排序的性能,比如它们的公因子等。很多论文研究了各种不同的递增序列,但都无法证明某个序列是最好的。对于某些基础递增的序列其实在性能上和某些复杂的序列接近,所以很多情况下我们没有必要花大力气在复杂序列上的研究上。
适用场景

与插入排序不同,希尔排序可以适用于大型数组,它对任意排序的数组表现良好,虽然不是最好。实验证明,希尔排序比我们上两章学习的选择排序和插入排序要快的多,并且数组越大,优势越大。目前最重要的结论是:希尔排序的运行时间达不到平方级别。

对于中等大小的数组希尔排序的时间是在可接受范围之内的,因为它的代码量很小,而且需要的额外空间很小,几乎可以忽略。对于其他更高效的其他算法,可能比希尔排序更高效,但是代码也更复杂,性能上比希尔排序也高不了几倍,所以在很多情况下希尔排序成为首选的算法。

其他

1. 直接插入排序是稳定的,希尔排序呢?

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

cdb8d20e3f7e13cf96223c6e4091c2664258aec7

c#武器版本


1static void Main(string[] args)
2 {
3
4 List<int> data = new List<int>() ;
5
6 for (int i = 0; i < 11; i++)
7 {
8 data.Add(new Random(Guid.NewGuid().GetHashCode()).Next(1, 100));
9 }
10 //打印原始数组值
11 Console.WriteLine($"原始数据: {string.Join(",", data)}");
12 int n = data.Count;
13 int h = 1;
14 //计算初始化增量,网络提供,据说比较好的递增因子
15 while (h < n / 3)
16 {
17 h = 3 * h + 1;
18 }
19
20 Console.WriteLine($"初始化增量:{h}");
21
22 while (h >= 1)
23 {
24 for (int i = h; i < n; i++)
25 {
26 for (int j = i; j >=h&&data[j]<data[j-h]; j-=h)
27 {
28 //异或法 交换两个变量,不用临时变量
29 data[j] = data[j] ^ data[j - 1];
30 data[j - 1] = data[j] ^ data[j - 1];
31 data[j] = data[j] ^ data[j - 1];
32 }
33 }
34 h = h / 3;
35 }
36
37
38 //打印排序后的数组
39 Console.WriteLine($"排序数据: {string.Join(",", data)}"); Console.Read();
40 }

运行结果:

原始数据: 47,50,32,42,44,79,10,16,51,74,52

初始化增量:4

排序数据: 10,16,32,42,44,47,50,51,52,74,79

golang武器版本

1package main
2import (
3 "fmt"
4 "math/rand"
5)
6
7func main() {
8 var data []int
9 for i := 0; i < 11; i++ {
10 data = append(data, rand.Intn(100))
11 }
12 fmt.Println(data)
13 var n = len(data)
14 var h = 1
15 for h < n/3 {
16 h = 3*h + 1
17 }
18 fmt.Println(h)
19 for h >= 1 {
20 for i := h; i < n; i++ {
21 for j := i; j >= h && data[j] < data[j-h]; j -= h {
22 data[j], data[j-h] = data[j-h], data[j]
23 }
24 }
25 h = h / 3
26 }
27 fmt.Println(data)
28}

运行结果:

[81 87 47 59 81 18 25 40 56 0 94]

4

[0 18 25 40 47 56 59 81 81 87 94]


原文发布时间为:2018-11-29
本文作者:大菜
本文来自云栖社区合作伙伴“Golang语言社区”,了解相关信息可以关注“Golang语言社区”。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
Golang语言社区
使用钉钉扫一扫加入圈子
+ 订阅

官方博客
官网链接