排序算法实验报告

《排序算法实验报告》由会员分享，可在线阅读，更多相关《排序算法实验报告（19页珍藏版）》请在装配图网上搜索。

1、数据结构实验报告八种排序算法实验报告、 实验内容编写关于八种排序算法的 C 语言程序，要求包含直接插入排序、希尔排序、 简单选择排序、堆排序、冒泡排序、快速排序、归并排序和基数排序。、 实验步骤各种内部排序算法的比较：1. 八种排序算法的复杂度分析（时间与空间）。2. 八种排序算法的 C 语言编程实现。3. 八种排序算法的比较，包括比较次数、移动次数。三、稳定性，时间复杂度和空间复杂度分析S? 序性 定 稳7tfl.OJ. zf定 稳-1J, OKJ定& 不)-OIJ rlz .JnlhVJ0(定 不序 推 堆匚32VJ稳 不换序 君.0(JVJ- L.定 稳 不拓墓裁接序的复杂度申壬代表茉蟹

2、字的基蠢,d储强 n代表黄整字的令数比较时间复杂度函数的情况：时间复杂度函数O(n)的增长情况*i,i不同丸小拾入的谗行时闻旳flH/Mog fl卽鼻IWTa .ni Pk(EO羽0. 26 卩还4 rtewc& flf2pa.oftjifi.-26|i4.10 ji*5-5p120.03 Iifl*. 16 f1 .也 jj32讣丹*0.3S4叭262 n5 .5 iwtLS4.01 plO.Bhfl.90 jh：K.m0Lft 3TT讷TZCL0 Jl。.至m65 鬪 H0. 02 沁irt zSI260“0-51 u4一创262.14Qi )3 沁用为ctifl22.33#0 .01 吹

3、1 0Q wc产gt4096mm卩4.l49 l$r0噬逸3.40L昭 Klflim0.01/dS Igas旳1 , |, S fttaiL 严 nl怡珈0叫M.期”9_38 Fi.D.27 1.12 g胪归的32呗0.0232,力严452P9.77 4IO*5 切菇536U-GZitQ 血 mi n3.3 diy囁mu620.02 jie131.0? fi222K.lp0.2936 iLaja炉 r car*沁闌Wff舐-1471 氐1. f5 riia7 mn加沪*虧itSW2S3O.CCp523.2p.坯】.3“4 5fi nii4afr JWV灯如“(Masvs22 A15 3 EW3

4、:?it I 为抽甘，H为毫苗T rec为扒 mizi曲甘钟I站为小时i 4*TS A ,Uu方月】Fftm为年卜cwt为世配：所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。时间复杂度来说：(1) 平方阶(O(n2)排序各类简单排序:直接插入、直接选择和冒泡排序；(2) 线性对数阶(O(nlog2n)排序快速排序、堆排序和归并排序；(3) 0(n1+)排序，是介于0和1之间的常数。希尔排序(4) 线性阶(O(n)排序基数排序，此外还有桶、箱排序。说明：当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和 移动记录的次数，时间复杂度可降至 O(n)

5、；而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提 高为 O(n2)；原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂 度影响不大。稳定性：排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录， 经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后， 记录的相对 次序发生了改变，则称该算法是不稳定的。稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另 一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这 样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是 不会改变的。另外，如

6、果排序算法稳定，可以避免多余的比较；稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序四、设计细节排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外 部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要 访问外存。我们这里说说八大排序就是内部排序。-直接描人排序r楠入排序 屈非序使用内存厂简单选择袜序-选择排序堆排序-交换排序驚-归井搏序基数排序内存相外廿结合傍用外部徘序1.插入排序-直接插入排序(Straight Insertion Sort) 基本思想：将一个记录插入到已排序好的有序表中，从而得到

7、一个新， 记录数增 1 的有序表。即：先将序列的第 1 个记录看成是一个有序的子序列，然后 从第 2 个记录逐个进行插入，直至整个序列有序为止。 要点：设立哨兵，作为临时存储和判断数组边界之用。 直接插入排序示例：MS却字tC49)ja65977613274Ji2t65&776132749(3849齡9776*1327药*4$cm(38496597)132749(76)(3849制76m1327J&i=6t(13)(1338496576972745i=7i(27)(13帚3B49倚7697)輔i=8itj, tk=l；2. 按增量序列个数k,对序列进行k趟排序；3. 每趟排序，根据对应的增量t

8、i,将待排序列分割成若干长度为 m的子序列，分别对各子表进行直接插入排序。仅增量因子 为1时，整个序列作为一个表来处理，表长度即为整个序列 的长度。希尔排序的示例:【初始关穂字:49 妙 85761327 S5 0436L97762749一趟rr序结畢:13274955044938 C5和fi二趟扌丰序结黒：三越排茅结果：算法的实现：我们简单处理增量序列:增量序列 d = n/2 ,n/4, n/8 .1 n为要排序数的个数即：先将要排序的一组记录按某个增量d (n/2,n为要排序数 的个数)分成若干组子序列，每组中记录的下标相差d.对每 组中全部元素进行直接插入排序,然后再用一个较小的增量

9、(d/2)对它进行分组，在每组中再进行直接插入排序。继续 不断缩小增量直至为 1，最后使用直接插入排序完成排序。13Q4佃382749S5祐97Q4H27384949556S7657时效分析： 希尔排序时效分析很难，关键码的比较次数与记录移动次数 依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选 取最好的增量因子序列的方法。增量因子序列可以有各种取 法，有取奇数的，也有取质数的，但需要注意：增量因子中 除1外没有公因子，且最后一个增量因子必须为1。希尔排 序方法是一个不稳定的排序方法。3.选择排序简单选择排序（ Simple Select

10、ion Sort）基本思想：在要排序的一组数中，选出最小（或者最大）的一个数与第 1 个位置的数交换；然后在剩下的数当中再找最小（或者最大） 的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数 第二个数）和第 n 个元素（最后一个数）比较为止。 简单选择排序的示例：唯 面胃尚尚尚尚尚逋 或 1234-5678 初第第第第第第第第315724913572491257349123754912345791234579123456912345671234567操作方法：第一趟，从 n 个记录中找出关键码最小的记录与第一个记录交 换；第二趟，从第二个记录开始的 n-1 个记录中再选出关键码最小的

11、 记录与第二个记录交换；以此类推第 i 趟，则从第 i 个记录开始的 n-i+1 个记录中选出关键码最小 的记录与第 i 个记录交换， 直到整个序列按关键码有序。4.选择排序一堆排序（Heap Sort）堆排序是一种树形选择排序，是对直接选择排序的有效改进。基本思想：堆的定义如下：具有n个元素的序列（kl,k2,.,kn），当且仅当满足跖占虹时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素） 必为最小项（小顶堆）。若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非 叶结点的值均不大于（或不小于）其子女的值，根结点（堆顶元素） 的值是最小（或最大）的。如：（a）大顶堆序列:（96,

12、83,27,38,11,09）（b）小顶堆序列：（12，36，24，85，47，30，53，91）初始时把要排序的 n 个数的序列看作是一棵顺序存储的二叉树 （一维数组存储二叉树），调整它们的存储序，使之成为一个堆， 将堆顶元素输出，得到 n 个元素中最小（或最大）的元素，这时堆 的根节点的数最小（或者最大）。然后对前面（n-1）个元素重新调 整使之成为堆，输出堆顶元素，得到 n 个元素中次小（或次大） 的元素。依此类推，直到只有两个节点的堆，并对它们作交换， 最后得到有n个节点的有序序列。称这个过程为堆排序。 因此，实现堆排序需解决两个问题:1. 如何将 n 个待排序的数建成堆；2. 输出堆

13、顶元素后，怎样调整剩余 n-1 个元素，使其成为一个 新堆。首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建 成堆的调整过程。调整小顶堆的方法：1）设有 m 个元素的堆，输出堆顶元素后，剩下 m-1 个元素。 将堆底元素送入堆顶（最后一个元素与堆顶进行交换），堆被破 坏，其原因仅是根结点不满足堆的性质。2）将根结点与左、右子树中较小元素的进行交换。3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点 不满足堆的性质，则重复方法 （2） .4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点 不满足堆的性质。则重复方法 （2） .5）继续对不满足堆性质的子树进行上述交换操作，直

14、到叶子结 点，堆被建成。称这个自根结点到叶子结点的调整过程为筛选。如图：9存91出锚出堆M丄臨轉H一难麓葩耳堤培 点9打子號交撫巳百子押玮満足粧. 英很与右于虫交捡再讨论对 n 个元素初始建堆的过程。建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过 程。1) n个结点的完全二叉树，则最后一个结点是第个结点的子树。2) 筛选从第-甘:;-个结点为根的子树开始，该子树成为堆。3) 之后向前依次对各结点为根的子树进行筛选，使之成为堆， 直到根结点。如图建堆初始过程：无序序列：(49， 38， 65， 97， 76， l3， 27， 49)3BE9n3438767S9-7无序序列】畀披範选之后

15、的找东匸M 65 端选之后的状杰38确晞选之病的找海F (即49袪障选之怎建咸的堆算法的实现： 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶 与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一 是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。 时效分析：设树深度为k,从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k次。所以，在建好堆后，排序过 程中的筛选次数不超过下式：Z( Lio 的 Cn 一 lilH-Uog? (ti2j4- * + log3 2) V 2n(llogs J) 而建堆时的比较次数不超过4n次，因此堆排序最坏情况下，时 间复杂度也为：O

16、(nlogn )。5.交换排序一冒泡排序(Bubble Sort)基本思想： 在要排序的一组数中，对当前还未排好序的范围内的全部数，自 上而下对相邻的两个数依次进行比较和调整，让较大的数往下 沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序 与排序要求相反时，就将它们互换。冒泡排序的示例：冊49!S13274SS;肃一翹排用后 “話6&貯馬1327再初姐关键字3B昶65132r457fi嬢二趟排序后274938序后3.1第六趙排序后6.交换排序一快速排序(Quick Sort)基本思想：1) 选择一个基准元素,通常选择第一个元素或者最后一个元素,2) 通过一趟排序讲待排序的记录分割成独

17、立的两部分，其中一 部分记录的元素值均比基准元素值小。另一部分记录的 元素值 比基准值大。3) 此时基准元素在其排好序后的正确位置4) 然后分别对这两部分记录用同样的方法继续进行排序，直到 整个序列有序。快速排序的示例：(a)趟排序的过程：pivatkc刼始关偉字逬行 抚蛮换之估 进持2底交掘之后进行3次空换之睜避行4次兗换之辰完就一対排序(b)排序的全过程:有序涉列i93BG5977fiB27(273&阊49(75护。时27(38)绪束4976(S7)祁am键束13273849S574&7初姥找态-底划分之后 井疑进行快速排存时效分析:快速排序是通常被认为在同数量级(O (nlog2n)的排

18、序方 法中平均性能最好的。但若初始序列按关键码有序或基本有序 时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中 法”来选取基准记录，即将排序区间的两个端点与中点三个记录 关键码居中的调整为支点记录。快速排序是一个不稳定的排序方 法。7.归并排序(Merge Sort)基本思想:归并(Merge)排序法是将两个(或两个以上)有序表合并 成一个新的有序表，即把待排序序列分为若干个子序列，每个子 序列是有序的。然后再把有序子序列合并为整体有序序列。 归并排序示例:算法的实现：1 个元素的表总是有序的。所以对 n 个元素的待排序列，每 个元素可看成 1 个有序子表。对子表两两合并生成 n/2

19、个子表， 所得子表除最后一个子表长度可能为 1 外，其余子表长度均为 2。再进行两两合并，直到生成 n 个元素按关键码有序的表。&桶排序/基数排序(Radix Sort)基本思想： 是按照低位先排序，然后收集；再按照高位排序，然后再收 集；依次类推，直到最高位。有时候有些属性是有优先级顺序的， 先按低优先级排序，再按高优先级排序。最后的次序就是高优先 级高的在前，高优先级相同的低优先级高的在前。基数排序基于 分别排序，分别收集，所以是稳定的。五、程序设计1、 直接插入排序算法的实现事祷排序元靑ninelude unid prill I (i nt F int n ) int j :pdntF(

20、”结果是 for(j- U; jn;MrliitfC U ,drjll；printF(n；打若第i个元打干i i元素.直接插九小于的话.移动有序表后插人素后uoid IiiburLSurKlnt d , int II) f int i:FOr(i= 1; iii; i*) IfOliJ int i-1;int k - ai; 川1 -町i-H；Lfhiictx Jj” Hj+1 - Mj； -void nain()Int aS = ；、prints W :直接插入排序的一般也式&p3r3n int dk缩小増量如果是直接插人排序,dl-l UDid She丄丄lnEQFt0Ft(lnt a|

21、|, Int n, int dlQint 1；fari= ilk； iu； iF(d i d i-ilk) int j = i-ilk； int x - h订； ai = Hi-d 町; whileCx (RjBk - Rj； j = dk;aj*dh -若第1个元素丸于17元爲直掏卸V小于的话,有序蘇插人 擔麟零严排序元素插人到正确位苣printn-df.dK: prints, nJ;丿苻T印每趙排序的结果/g纭础丑H疔押牛卜州4讦后|甘庁void 5hcllSDrt(int , int n) int dlt - n/2;while( dk = 1ShpllTnt?pr|-Snrt, n ,

22、 elk): dk = ns；uaid nidinfHint a8 - 3,1,5,7,2,4,9,6H /ShellInsertSort(a, B, 1);富按插 =hcllS Drt(3,町；希駅遥心print(a,B);3、简单选择排序算法的实现ttinclude liaid pri nt(int , int n ,i.nt i )int j；printfC第勧趟for(j= B; i8; i+)f piintFCd 戶j;printfCXn);H数组的最/値斷Qtuf int数组的傩值 int seiectninKeytint a| int n, int i)int k = i, j;

23、fcr(j-i1 ;j aj) k = j：return k;H选择排序uoid selectSart(int a, int n) lnt key, tnp,i;for(i - 9; i i) key = SelectMinKey(a, n,i):选泽最小的元套iFfkey = i) print(a, n , i);int main()int aB = 3,1,5,7,2,4,9, int j ;ptdntF初始); forij= ; js； j+) prinLfC-d -adj);printFCVn): selectSortfa, 8); print(a,8,8);4、堆排序算法的实现tti

24、ncluds void print(int a t int r)int J;forJ- n； jn; j*+)pi-1 ntrcrlprintFCXnH/*已知e除了 H咎均堆的尋.:月整呛使rMm窘：洋茫点丿艰旳丁树左*即旳n s崑莓遍鑒的蜒申藤的位宣*/void Hedpfldjustdnt H,int s. int length)int Li屮-Hl;lnt cnild - 2e*1 :左;歿子結点的是宣i*l为当前调蚪点的右孩子结点的置) iihile (child length) lFWidid+i iength t& HchiidHchiid*i /如果右建子大于左孩子(找到比当前

25、特调整带点大的畏子结点】child =/：PiA-：T. 7.调整.口 挟卫丄iF(HSHChild) H5 - Hchild； / s - child; child 2*5*1; else / 2 int i;for (i = (ipngrn -1) / ? ; i = M； -i)HeapAdjust(H,i,lengtti;陥排rrm丈*/void HedpSurL(int H ,int lenyLli)Int i ；初姑堆BuildLingHcap(ll, length);从最三一八元素开始对序列进行调整for (i - lenijLh - 1; i B; i)山换堆頂元袁叫町詞挂中最

26、肓一丫元袁int Ltmp - HTil； Hfil - 盯町；H0 - Lenp;皿次交换堆顶元素丸妊中最方一个元嵩之云,都更对妊进F话整 hjm卩口njii寸【H U);intint HL1HJ =少上冊 printfC初雄值】； |jrinL(ti, 16);HeapSort(H,10);/sclcctSart(a, 6; printfC果:)； print(H,1G);5、冒泡排序算法优化后的实现ninciude bLdij.ri?void pr int(int a , int n ) int j ;prioTK结果：J； far( i- 0; iprinttc xn );冒泡排序uo

27、ld BubLltSurl f int rl. int u)int low - 9;int high= n -1 ; /设直娈量的初始值int tnp ,j; Iwhile (Iulj hiqli)(for (j= Low; j rj+1 low： j)皮向冒泡执封最小古 if (rjrj-1 tnp - rj； rj-rj 1；rj+1OW； print(r 3n);Int nidiiif)int a8 = 3,1,5,7,2,4,9P6; int j;intF【“初值为:);For(j= 0; jR; j+H printFCdprintf(Xn;BubbleSortfd , 8); pri

28、nt(a,8,8;6、快速排序算法的实现ttincludetvoid in-im( int .il, int n) int j;FDMj- fl： j;uold sMpfint *ja Int *U)int tm卩歸； = *b;囂D - top；mt pairtitlcntint 利.int Iw, int high)”F：.壬.|L沖干汽int prdvcteji - a10M|; whilp(lcw higbijrnileClo high GA |tiigri ?= privotKu) siiijafljt.allow ?卧hi#”uhilv( Low higha| Low P Int

29、k K J r(i-1; i-n;i + + )int tup - r|l;int J-1-1;r| 1-1 I = I n|iint naln(3int diai fl声上.,1札册：呼讣怖广初始窗料;；print;qulckSnrtmVni#);niintdCT. ；iprint(aB19);7、归并排序算法的实现打将ri- n和+1口归并到辅助数组rFi- nuoid M9rge(Elen)T9pe *r pElcmTijpe *rF, int i, int n, int n)int j ?k；for(j=in* 1 ,k=i; i=m j =ii ; +k) if(rj ri) rfk

30、 = 口j+； else rFk = ri+;uhilefi = m) rfk+ = ri*+;uhile(j 18、基数排序算法的实现Uoid RadixSort (Node L length anaKtjadis)int汕十;k=1;m=1;int teTip10length-1;Empty (temp);打清空I临时空间 uhile(kinajradiK遍比丹专天犍For(int i=G;ilengtti ;i+)分|，配过程iF(Lin) TenpQn=Li;elseLsp=(Li,/ni)10;确定关挺字 Templpn=Li;n+;CollectElementfL tTenip);

31、收集 n=G;m=nnr| 0;k+;六、测试结果、 直接插入排序算法的实现有如下结果：戛婕叙白呼算袪的程序实现弟丄T；l壬口果疋 二3S 49 65 97 76 13 27常2次结果是二38 49 65 97 76 13 27懐3次结果是：I 3S 49 65 9? ?6 13 27當4次结果是：3S 49 65 ?6 97 13 27第5次结果是二,13 3S 49 65 76 97 27常E次结果是：13 27 3S 49 65 76 97常果是，13 27 39 49 &5 76 97Piess any key to continue 2、 希尔排序算法的实现有如下结果：*2本枚结果为

32、:21365497增量2 本袂结果为：21345697関量2 本次结果为；21345697增量2 本次结果为；21345697增量1 本次结果为：12345697愴量1 本次结果为 .12345697 增量1 本次结果为：12345697憎量1 本次结果为：12345697憎量1 本妆结果为：12345697增量1 本次结果为； 112345697 牌量i 本次结果为；112345679本次结果为：12345679Fr亡ss ajiyto continue3、 简单选择排序算法的实现4、堆排序算法的实现初始值：31572496 10 8 1578496 10 2 15 IB 849672 Q1

33、9 10 845672 10 97845612 10 89734561 985734261B7563421 6 3 5 12 4 5 3 4 124 3 2 1 122 11結果：123456789 10Press any key to continue5、冒泡排序算法优化后的实现值果果果果果 聲结结结结5321 为.43214 9 67 97 97 97 97 9n a s5e5to continue6、快速排序算法的实现ffUSn#： 31572496 10 8 Ei3?5496i0S21365479 10 8綺果：Press any ke 1/ to cont in Lie 7、归并排序

34、算法的实现排住对翻4F肝4fi 19S4421fl54FH93扛克后121W2427444 耳4R3阳眄95tBSS anv k石y to cDritinne8、基数排序算法的实现ffUSn#! 31572496 10 801375496 10 821365479 10 8綺果：Press any ke 1/ to cont in Lie 七、总结反思本次对于八种排序的系统学习，利用图标的记忆能够很好的帮助学习。花 了很长时间终于把排序的基础学了一下，这段时间学了很多东西，总结一下： 学的排序算法有：插入排序，合并排序，冒泡排序，选择排序，希尔排序，堆排 序，快速排序，基数排序。比较一下学习后

35、的心得。我不是很清楚他们的时间复杂度，也真的不知道他们到底谁快谁慢，因为书 上的推导我确实只是小小了解，并没有消化。也没有完全理解他们的精髓，所以 又什么错误的还需要高手指点。1.排序稳定，所谓排序稳定就是指：如果两个数相同，对他们进行的排序结 果为他们的相对顺序不变。例如A=1,2,1,2,1这里排序之后是人=1,1,1,2,2 稳定就是排序后第一个 1 就是排序前的第一个 1，第二个 1 就是排序前第二个 1， 第三个 1 就是排序前的第三个 1。同理2 也是一样。这里用颜色标明了。不稳定 呢就是他们的顺序不应和开始顺序一致。也就是可能会是A二1,1,1,2,2这样的 结果。2感觉谁最好，

36、在我的印象中快速排序是最好的，时间复杂度：n*log(n), 不稳定排序。原地排序。他的名字很棒，快速嘛。当然快了。我觉得他的思想很 不错，分治，而且还是原地排序，省去和很多的空间浪费。速度也是很快的， n*log(n)。但是有一个软肋就是如果已经是排好的情况下时间复杂度就是n*n, 不过在加入随机的情况下这种情况也得以好转，而且他可以做任意的比较，只要 你能给出两个元素的大小关系就可以了。适用范围广，速度快。3插入排序：n*n的时间复杂度，稳定排序，原地排序。插入排序是我学的 第一个排序，速度还是很快的，特别是在数组已排好了之后，用它的思想来插入 一个数据，效率是很高的。因为不用全部排。他的

37、数据交换也很少，只是数据后 移，然后放入要插入的数据。(这里不是指调用插入排序，而是用它的思想)。我 觉得，在数据大部分都排好了，用插入排序会给你带来很大的方便。数据的移动 和交换都很少。4. 冒泡排序，n*n的时间复杂度，稳定排序，原地排序。冒泡排序的思想很 不错，一个一个比较，把小的上移，依次确定当前最小元素。因为他简单，稳定 排序，而且好实现，所以用处也是比较多的。还有一点就是加上哨兵之后他可以 提前退出。5选择排序，n*n的时间复杂度，稳定排序，原地排序。选择排序就是冒泡 的基本思想，从小的定位，一个一个选择，直到选择结束。他和插入排序是一个 相反的过程，插入是确定一个元素的位置，而选

38、择是确定这个位置的元素。他的 好处就是每次只选择确定的元素，不会对很多数据进行交换。所以在数据交换量 上应该比冒泡小。6插入排序，选择排序，冒泡排序的比较，他们的时间复杂度都是n*n。我 觉得他们的效率也是差不多的，我个人喜欢冒泡一些，因为要用它的时候数据多 半不多，而且可以提前的返回已经排序好的数组。而其他两个排序就算已经排好 了，他也要做全部的扫描。在数据的交换上，冒泡的确比他们都多。举例说明插 入一个数据在末尾后排序，冒泡只要一次就能搞定，而选择和插入都必须要n*n 的复杂度才能搞定。7合并排序：n*log(n)的时间复杂度，稳定排序，非原地排序。他的思想 是分治，先分成小的部分，排好部

39、分之后合并，因为我们另外申请的空间，在合 并的时候效率是0(n)的。速度很快。貌似他的上限是n*log(n)，所以如果说是 比较的次数的话，他比快速排序要少一些。对任意的数组都能有效地在n*log(n) 排好序。但是因为他是非原地排序，所以虽然他很快，但是貌似他的人气没有快 速排序高。8堆排序：n*log(n)的时间复杂度，非稳定排序，原地排序。他的思想是 利用的堆这种数据结构，堆可以看成一个完全二叉树，所以在排序中比较的次数 可以做到很少。加上他也是原地排序，不需要申请额外的空间，效率也不错。可 是他的思想感觉比快速难掌握一些。还有就是在已经排好序的基础上添加一个数 据再排序，他的交换次数和

40、比较次数一点都不会减少。虽然堆排序在使用的中没 有快速排序广泛，但是他的数据结构和思想真的很不错，而且用它来实现优先队 列，效率没得说。堆，还是要好好学习掌握的。9希尔排序：n*log(n)的时间复杂度(这里是错误的，应该是namda(l lamda 2), lamda和每次步长选择有关。)，非稳定排序，原地排序。主要思 想是分治，不过他的分治和合并排序的分治不一样，他是按步长来分组的，而不 是想合并那样左一半右一半。开始步长为整个的长度的一半。分成nLen/2个组， 然后每组排序。接个步长减为原来的一半在分组排序，直到步长为1，排序之后 希尔排序就完成了。这个思路很好，据说是插入排序的升级版

41、，所以在实现每组 排序的时候我故意用了插入排序。我觉得他是一个特别好的排序方法了。他的缺 点就是两个数可能比较多次，因为两个数据会多次分不过他们不会出现数据的交 换。效率也是很高的。10. 快速排序，堆排序，合并排序，希尔排序的比较，他们的时间复杂的都 是n*log(n),我认为在使用上快速排序最广泛，他原地排序，虽然不稳定，可 是很多情况下排序根本就不在意他是否稳定。他的比较次数是比较小的，因为他 把数据分成了大和小的两部分。每次都确定了一个数的位置，所以理论上说不会 出现两个数比较两次的情况，也是在最后在交换数据，说以数据交换上也很少。 合并排序和堆排序也有这些优点，但是合并排序要申请额外

42、的空间。堆排序堆已 经排好的数据交换上比快速多。所以目前快速排序用的要广泛的多。还有他很容 易掌握和实现。11. 基数排序：n的时间复杂度，稳定排序，非原地排序。他的思想是数据比 较集中在一个范围，例如都是4位数，都是5位数，或数据有多个关键字，我们 先从各位开始排，然后排十位，依次排到最高位，因为我们可以用一个n的方法 排一位，所以总的方法为d*n的复杂度。关键字也一样，我们先排第3个关键字， 在排第3个关键字，最后排第一个关键字。只有能保证每个关键字在n的时间复 杂度完成，那么整个排序就是一个d*n的时间复杂度。所以总的速度是很快的。 不过有一点就是要确保关键字能在 n 的时间复杂度完成。

43、12. 排序算法的最后感悟：黑格尔说过：存在即合理。所以这些排序的算法 都是很好的，他确实给了我们思想上的帮助。感谢前人把精华留给了我们。我得 到的收获很大，总结一下各自排序的收获：冒泡：好实现，速度不慢，使用于轻量级的数据排序。插入排序：也使用于小数据的排序，但是我从他的思想中学到怎么插入一个 数据。呵呵，这样就知道在排好的数据里面，不用再排序了，而是直接调用一下 插入就可以了。选择排序：我学会了怎么去获得最大值，最小值等方法。只要选择一下，不 就可以了。合并排序：我学会分而治之的方法，而且在合并两个数组的时候很适用。堆排序：可以用它来实现优先队列，而且他的思想应该给我加了很多内力。 快速排序：本来就用的最多的排序，对我的帮助大的都不知道怎么说好。 希尔排序：也是分治，让我看到了分治的不同，原来还有这种思想的存在。 基数排序：特殊情况特殊处理。