常见排序算法总结和Go标准库排序源码分析.pdf

《常见排序算法总结和Go标准库排序源码分析.pdf》由会员分享，可在线阅读，更多相关《常见排序算法总结和Go标准库排序源码分析.pdf（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、前后排序算法是数组相关算法的基础知识之一，它们的经典思想可以用于很多算法之中。这里详细介绍和总结7种最常见排序算法，并 用G o做了实现，同时对比这几种算法的时间复杂度、空间复杂度和稳定性。后一部分 是 对G o标准库排序实现的源码阅读和分析，理解官方是如何通过将以上排序算法进行组合来提高排序性能，完成生产环境的排序实践。排序算法分类常 见 的 这7种排序算法分别是:选 择排序冒 泡排序插 入排序希 尔排序归 并排序快 速排序堆 排序我们可以根据算法特点像复杂度、是否比较元素、内外部排序等特点对它们做分类，比如上面的算法都是内部排序的。一般可以基于算法是否比较了元素，将排序分为两类：1.比较类

2、排序：通过比较来决定元素间的相对次序。由于其平均时间复杂度不能突破$O(Nlog N)$,因此也称为非线性时间比较类排序。2.非比较类排序：不通过比较来决定元素间的相对次序。它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。主要实现有：桶排序、计数排序和基数排序。通过这个的分类，可以先有一个基本的认识，就是比较类排序算法的平均时间复杂度较好的情况下是$O(NlogN)$(一遍 找 元 素$0(N)$,一遍找位置$O(logN)$)o注：有重复大量元素的数组，可以通过三向切分快速排序，将平均时间复杂度降 低 到$0(N)$比较类排序算法因为非比较排序有其局限性，所

3、以它们并不常用。本文将要介绍的7种算法都是比较类排序。选择排序原理：遍历数组，从中选择最小元素，将它与数组的第一个元素交换位置。继续从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。循环以上过程，直到将整个数组排序。时间复杂度分析:$0(NN2)$。选择排序大约需要$N72/2$次 比 较 和$N$次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要很多的比较和交换操作。实现：/选 择 排 序(selection ort)package sortsFeme Selectio.Sort(arr 心t)it for i：=O i /c八()；i+m/ia：=/

4、for j:=r+j /en(rr);j+if arirj arrmin tvu八=jtmp:=arriarri=arrminarrmm=tmp)return arr)冒泡排序原理：遍历数组，比较并将大的元素与下一个元素交换位置，在一轮的循环之后，可以让未排序i的最大元素排列到数组右侧。在一轮循环中，如果没有发生元素位置交换，那么说明数组已经是有序的，此时退出排序。时间复杂度分析：$0(NA2)$实现:/冒 泡 排 序 四 sort)package sortsFeme bubb(eSort(arr(swapped:=truefor swapped swapped=fakefor i:=O i

5、；i+if arri-hl arri arr/+-l?arri=a rrli,arr7+2jswapped-tnxe)1)return arr)插入排序原理:数组先看成两部分，排序序列和未排序序列。排序序列从第一个元素开始，该元素可以认为已经被排序。遍历数组，每次将扫描到的元素与之前的元素相比较，插入到有序序列的适当位置。时间复杂度分析：插入排序的时间复杂度取决于数组的排序序列，如果数组已经部分有序了，那么未排序元素较少，需要的插入次数也就较少，时间复杂度较低。平均情况下插入排序需要$N 72/4$次 比 较 以 及$N 72/4$次交换；最坏的情况下需要$N 72/2$比 较 以 及$NA2

6、/2$次交换，最坏的情况是数组都是未排序序列（倒序）的；最好的情况下需要$N-l$次 比 较 和 0 次交换，最好的情况就是数组已经是排序序列。实现：/插入排序。八scrti。八 sort)package sortsFeme 伍sertio八Sort 口/八t)，八t(for current!tadex:=X;currentlHex O&arriterator-l=temporary;iterator-arriterator=arrliterator-larriterator=temporary1return arv希尔排序原理：希尔排序，也称递减增量排序算法，实质是插入排序的优化(分组插入排

7、序)。对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素位置，每次只能将未排序序列数量减少1。希尔排序的出现就是为了解决插入排序的这种局限性，通过交换不相邻的元素位置，使每次可以将未排序序列的减少数量变多。希尔排序使用插入排序对间隔d的序列进行排序。通过不断减小d,最后令d=l,就可以使得整个数组是有序的。时间复杂度：$O(dN*M)$,M表示已排序序列长度，d表示间隔，即N的若干倍乘于递增序列的长度S|8 3 S S ,s7|6 1|3()7()()o S O实现：/希尔排序(shell sort)package sortsFeme ShellSort(arr it)for d/h/2

8、);d O;d/=2 for i:=d;i=d&arrj-d arrfj;j-=d arrf/,arrfj-d=arrj-d,arrj)return arr归并排序原理：将数组分成两个子数组，分别进行排序，然后再将它们归并起来（自上而下）。具体算法描述：先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。再考虑递归分解，基本思路是将数组分解成好t 和 的 向，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可

9、以二分，直至分解出的小组只含有一个元素时为止,此时认为该小组内部已有序。然后合并排序相邻二个小组即可。归并算法是分治法的一个典型应用，所以它有两种实现方法:1.自上而下的递归：每次将数组对半分成两个子数组再归并(分治)2.自下而上的迭代：先归并子数组，然后成对归并得到的子数组时间复杂度分析:$O(Nlog N)$实现：/归并排序(Merge sort)pckge sortsF eme ierge(a 口，八 七 b Qmt)Jint(var r=H A ke(Ji八七怙 八()+/。八(匕)vav i -Ovar j Ofor i /。八()&j leia(b)if犯 =如J ri+j=血i+

10、eke(巾包=如Jj+)for i lei(a)“切=w什 十for j ri+j=bjj+return r/Mergesort 合并两个数组 fimc Mergcsort(iteMS mt)iiat if/c八(itehs)2.return/terns)var Middle=/2var a=McYgesort(iCMS:Middle)var b=Mergesort(itei,siddle：)return merged,b)快速排序原理：快速排序也是分治法的一个应用，先随机拿到一个基准pivot,通过一趟排序将数组分成两个独立的数组，左子数组小于或等于pivot,右子数组大于等于 pivoto

11、然后可在对这两个子数组递归继续以上排序，最后使整个数组有序。具体算法描述：1.从数组中挑选一个切分元素，称为“基 准(pivot)2.排序数组，把所有比基准值小的元素排到基准前面，所有比基准值大的元素排到基准后面(相同元素不对位置做要求)。这个排序完成后，基准就排在数组的中间位置。这个排序过程称为“分 区 (partition)3.递归地把小于基准值元素的子数组和大于基准值的子数组排序空间复杂度分析：快速排序是原地排序，不需要辅助数据，但是递归调用需要辅助栈，最好情况下是递归$log 2N$次，所以空间复杂度为$O(log2N)$,最坏情况下是递归$N-1$次，所以空间复杂度是$0(N)$。时

12、间复杂度分析：最好的情况是每次基准都正好将数组对半分，这样递归调用最少，时间复杂度为$0(N log N)$最坏的情况是每次分区过程，基准都是从最小元素开始，对应时间复杂度为$0(NAA2)$算法改进：1.分区过程中更合理地选择基准(pivot)。直接选择分区的第一个或最后一个元素做pivot是不合适的，对于已经排好序，或者接近排好序的情况，会进入最差情况，时间复杂度为$0(NA2)$2.因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序3.更快地分区（三向切分快速排序）：对于有大量重复元素的数组，可以将数组切分为三部分，分别对应

13、小于pivot、等 于p iv o t和大于p iv o t切分元素实现：/;向 切 分 快 速 排 序：(quick sort)package sortsim port(niath/raiadn)fuiac QuickSort(arr 口/认 亡)口 讥 士(i f加 八rr)=2 return avv)pivot:=arrraiad.hat(le(arr)lowPart:=O,/en(rr)highPart：=kvake(in.tj O _,/e八()widdlePart:=O,te(rr)for-/tern:=range tarr switch case itew pivot：higkP

14、aH=appe八d(highPart/tern)lowPart=QuickSort(lowPart)higkPart=QuickSort(kigkPart)lowPart=appcidowPart,i,iddlePart.)lowPart=appe八(lowPart,kighPart.)return lowPart堆排序原理：堆排序是利用 堆积(h e a p)这种数据结构的一种排序算法。因为堆是一个近似完全二叉树结构，满足子节点的键值或索引小于(或大于)它的父节点。具体算法描述：1.将待排序数组构建成大根堆，这个堆为初始的无序区2.将堆顶元素$R_1$与最后一个元素$R_n$交换，此时得到新

15、的无序区($R_l,R_2,.R_n-l$)和 新 的 有 序 区($R _(n$),并且满足$R_l,2,.n-l)=O;i-k.MaxHeapify(i)return h)fuiac(h kvxaxHeap)MaxHeapify(i mt)L r:=2*i+1,2*i+2max：=iif I hslicevax mx=Iif r hsliceax max=r)if/=i hslicci,kslicei.ax=h.s/cemax hsliceik.MaxHcapify(iax)Feme(h size。iit(return h.heapSize)func HeapSort(slice m t)

16、in t h:=buildMaxbleap(stice)for i:=lei(h.slice)-1;r=1;i-kslice。,kslicei=h.slicei,ksliccOh.heapSize-h.MaxHeapify(O)return h.slice算法复杂度比较下面是各排序算法的复杂度和稳定性比较:注：排序算法时间复杂度（平均）时间复杂度（最好）时 间 复 杂 度（最坏）空间复杂度稳定性备注选择排序$0(NA2)$0(NA2)$0(NA2)$0(1)$o不定冒泡排序$0(NA2)$0(N)$0(NA2)$0(1)$稳定插入排序$0(NA2)$0(N)$0(NA2)$0(1)$稳定时间复

17、杂度和序有关希尔排序$0(NA13)$0(N)$0(NA2)$0(1)$稳不定改进版插入排归并排序$0(N log N)$0(N log N)$0(N log N)$0(N)$稳定扪速树序$0(N log N)$0(N log N)$0(NA2)$0(N logN)$不稳定堆排序$0(N log N)$0(N log N)$0(N log N)$0(1)$不定无法利用局部 稳定：如 果a原 本 在b前面，而a=b,排 序 之 后a仍 然 在b的前面。不稳定：如 果a原 本 在b的前面，而a=b,排 序 之 后a可能会出现在b的后面。对比这里排序的时间复杂度，归并排序、快速排序和堆排序的平均时间

18、复杂度都是$O（Nlog N）$。但是再比较最坏的情况，可以看到堆排序的下界也是$0（Nlog N）$,而快排最坏的时间复杂度是$0（N、2）$。你可能会问，按分析结果来说，堆排序应该是实际使用的更好选择，但为什么业界的排序实现更多是快速排序？实际上在算法分析中，大$0$的作用是给出一个规模的下界，而不是增长数量的下界。因此，算法复杂度一样只是说明随着数据量的增加，算法时间代价增长的趋势相同，并不是执行的时间就一样，这里面有很多常量参数的差别，比如在公式里各个排序算法的前面都省略了一个$c$,这个$c$对于堆排序来说是100,可能对于快速排序来说就是1 0,但因为是常数级所以不影响大$0$。这

19、里有一份平均排序时间的Benchmark测试数据（数据集是随机整数，时间单位s）：数据规模快速排序归并排序希尔排序堆抖1000 w0.751.221.773.575000 w3.786.299.4826.541亿7.6513.0618.7961.31因为堆排序每次取一个最大值和堆底部的数据交换，重新筛选堆，把堆顶的X调整到位，有很大可能是依旧调整到堆的底部（堆的底部X显然是比较小的数，才会在底部），然后再次和堆顶最大值交换，再调整下来，可以说堆排序做了许多无用功。总结起来就是，快排的最坏时间虽然复杂度高，但是在统计意义上，这种数据出现的概率极小，而堆排序过程里的交换跟快排过程里的交换虽然都是常

20、量时间，但是常量时间差很多。G o标准库排序源码分析梳理完最常用的7种排序算法后，我们继续来看下G o在标准库里是怎么做的排序实现。标准库的sort包的目录树如下（以G。1.15.5为例）：$t r e e .|-example二 八terface_test.go/提供 对 口比W&排 序 的 example.|-exakvple_keys_test.go/根据s t r u c t里 对 某 字段的自定义比较，来对Jstruct排 序 的example|-cxamplevuAlti_test.g。/根据用户定义好的 As方法做排序的example|-exakvple_search_tcst.

21、go/sort.Searck 提供对排序数组二分查找某元 素 的 e x a m p l e|-exai O;i =1 W 平仍+1return depth.*2需要注意的一点是，sorts。调用的quicksort排序函数，并不是最常见的快排(参考本文3.6小 节)，quicks。的整体框架比较复杂，流程如下：fuM qaickSort(data Interface,a,b,iaxU)epth mt)是第一个索引，b是 最 后 一 个 索 引。如果slice长度大于12,会 一 周 走 下 面 排 序 循 环for b-a 工2/如果递归到了最大深度，就使用堆排序if aaxDeptk=(9

22、 heapSodata,a,b)return)/循环一次，最大深度-1,相当于又深入(递归)了一层iaxDepth-/这是使用的是三向切分快速排序，通 过doPivot进行快排的分区/doPivot的实现比较复杂，a是数据集的左边，b是数据集的右边，/它取一点为轴，把不大于中位数的元素放左边，大于轴的元素放右边，/返回小于中位数部分数据的最后一个下标，以及大于轴部分数据的第一个下标。/下标位置a.S p iv此/dataa.i,lo datapivotiloj mM/:=doPivot(data,a,b)/避免较大规模的子问题递归调用，保证栈深度最大为MnxDep协/解释：因为循环肯定比递归调

23、用节省时间，但是两个子问题只能一个进行循环，另一个只能用递归。这里是把较小规模的子问题进行递归，较大规模子问题进行循环。if mfo-a X/D。ShellSort pass with gap 6/It could be written i八 this simplified form cause b-a=12for i:=a+6;i=hi breakif chil4+工 =O;i-si&Dow.(da%j i,hi,first)/Pop elementsj largest firstj into end of data.for i:=ki-工；i=O;i-data.Swap(firstJ fi

24、dt+i)siftDow八。first)在上面快速排序的原理我们有提到过：如果每次分区过程，基 准(pivot)都是从最小元素开始，那么对应时间复杂度为$0(N 772)$,这是快排最差的排序场景。为避免这种情况，quicksort里的WoP/vot选取了两个基准，进行三向切分，提高快速排序的效率：APivot在切分之前，先 使 用 或mOfThree函数选择一个肯定不是最大和最小的值作为轴，放在了切片首位。然后把不小于datapivot的数据放在了$lo,b)$区间，把大于datapivot的数据放在了$(c,h i-l$区间(其 中 datahi-l=datapivot)o即 slice会

25、被切分成三个区间：left begin matrix idatalo,b-1)datab-l,c)datac,hi)endmatrixright.U 勿 企l,d)M7 匕/)W o Pivot的实现如卜：/Quicksort Joos 叫 following Bentley aiad M c Ilro y/八gi 八 een八g a Sort Function,SP&ENovember J-993./ediaiaOfTkfree woves the median of the three values dataO J dataiZinto datakvl.fuiac iediaiOfThre

26、data Interface,wO.m2,int)/sort 3 eleeiatsif data.L ess(hl,3O)data.SA/ap(ilJ m(9)/dataivO=datavif data.Less(12,M l)data.Swap(Kv2.j w1)/data o =dataw&datakvl dataivZif data.Le$s(iJ m9)data.SA/ap(iJ m(9)/now datakvO=datakvJ-4 0 /Ttxkegs、NM thcJ hAedi 八 of three wediavs of three.s:=(hi-lo)/3麻ed/n八/。，/o+

27、s,/。+2*s)麻0+”八。什 砥d仇 m,m-s,m4-s)iediaOfThrcdataj hi-工,k-l-s,ki-J2*s)cdiaiOtThrdataj ot m,hi-1)/Iwariaits are：/datalo=pivot(set up by ChoosePivot)/datalo i a pivot/dataa=i fe =pivot/datab=i cj uMxaiiMd/datac =i pivot/dataki-l=pivotpivot：=Io2 c:=/。+1,for;a c&data.Lesa,pivot);a+)b:=afor(FOK;。c&Idata.Le

28、spivot,b);。+/datab =pivotfo r;b pivot)if b=c break/datab pivot;datac-l =pivotdata.Swap(b,c-1)。+c)/if Ki-cO the八 there are duplicates(by property of wediav of 八Me)./Lets be a bit M。conservat/Ve,avd set border to S.protect:=ki-c 6if(protect&ki-c 6/b-lo (hi-lo)*3/4-i 8/=F V datai 1)if protect/Protect a

29、gainst a lot of duplicates/Add invariaiat:/dataa=i b uM xaM d/datab=i c-pivotfor(for j a b&鼠ata.Less(b-1,pivot);b-/datab=pivot)for j a b&data.L.esa,pivot);a+/dataa pivot)if a b break/dataa=pivot;datab-八 为止。Feme Stab(e(data Interface)stabdataj data.Leia()fuM tab（e（data Interface,八 i八 土）（blocksize:=2.

30、0/初 始 blocksize 设 置 为 20a,b:=Ot blocksize/对每个块（以及剩余不足勿。ckSizc的一个块）进行查询排序for 4?=H insert!oiSodataj at b）a-bb+=blocksizei八sertio八SortaM a,八）for blocksize 八a b-O,2blockSize/每两个blocksize进行 合 并for fa =H$yiMerge（dataJ a blocksize,b）a-b。+=2*blocksize）/剩余一个多blocksize进行 合 并if m:=+blocksize;m n.sgiMe电4M a,m,八

31、)blocksize*=2)/SymMrge merges the two sorted subscq e八ccs dataa：i aiad datai：b using/theSymMerge algorithm froix Pok-S。八 K/m 八 d A me Kutzier,Stable Mm/mum/StorageMerging by Symmetnc CoMpark。八s”,in S s八八e Alters ad Tomasz/Radzik,editors,Algorithms-ESA 2004,volume 3221 of Lecture Notes in/Computer Sc

32、ience,pages714-72.3.SpH八gw,2 0 0 4./Let M 二 小-久 avd N-b-v.Wo/og M log(M)as the 八 麻。of ass/?八八ts dssuhihg a/rotation.algoritk wkick usesO(M+N+gcd(M N)ss/?八 侬ents.The argiAievtatioa/M the paper carries though forSwap operations,especially as the block/swapping rotate uses oily O(M+N)Swaps./symMere ass

33、umes non.-dcgeMrate argiAiets：m&m=dataa for m=r b./Exit the search loop with i=b in case 八。such index exists.i:=侬j：=bfor j h:=iit(uint(i-ij)1)if data.Less(k,a)i=+工 eke(j二人)/Swap values until dataa reaches the position before i.for k.:=a;k dataw(for a i m./Exit tke search.loop with i=m m case 八。such

34、mex exists,i:=aj :二 3for i i;k-dataSwap(kJ k-X)return)wid:=1)八:=mid+mvav start,r iitif kv m/d start 二八一br=m/c eke(start=ar=mp:二 八一1for start r c:=i八亡Vvt(start)1-)if Idata.L-ep-Cj c)start=c+2 else r=c)e八d:=n-startif start m&m c八d(rotate(dataJ start,m,end)if a start&start syiMergeCdata,a,start,m/d)if

35、3以 e八4&end b syiMerge(dataJ vid,b)/Rotate two coiasecutive blocks u=dataa：i,J avd.v=datakv:b/认 data：/Data of theform x u v y1 is changed to x v u y1./Rotate perforins at kvxost b-a iaiay calls todata.Swap./Rotate assumes 八。八-degenerate arguments：a m&m b.fuM rotate(dataInterfacea b iiat)i:=3一j:=-mfor

36、 i!=j fjsA/apRaige(dataJ w-i,m,j)i-=J else(swapR.am.ge(data,M-i,M+j-i,i)J=1)/i=j$wapRange(dataJ w-i,IM.,i)1以上是稳定排序方法Stable的全部代码。排序 example为应用sort包里排序函数Sort(不稳定排序)，我们需要让被排序的slice类型实现sort/nterface接口，以整形切片为例：type IntSlice/ntfuiac(p litSlice)Lei()return lei(p)fuM(p litSlice)Less(i,j i八t)bool return pi p

37、j(P ltSlice)Swap(i,j mt)pi,pj=pj,pi)flAM 鹏 4 心 Si:=14,8,%17,56,Q5,3)fmt.Prmtkfsl)/89 14 8 9 i7 S6 95 3sort.Sort(s。/3 8 q 14 17 56 83 Q5)总结本文主要详细介绍了我们常见的7 种排序算法的原理，实现和时间复杂度分析,并阅读G o 源码里sort包的实现，分析官方如何通过将以上排序算法进行组合来提高排序性能，完成生产环境的排序实践。参考 十大经典排序算法 程序员必知必会的十大排序算法 算法-排序 TheAlgorithms/Go Package sort 三向切分的快速排序 快速排序V S 归并排序V S 堆排序 快速排序算法的优化思路 一文搞懂Go语言中的切片排序 从 sort.go看排序算法的工程实践 问答|Go sort包使用与源码剖析sort包源码分析