排序算法总结.doc

排序算法总结常见的排序方式有6种:---简单排序里面的有:插入排序、选择排序、冒泡排序,时间复杂度为O(n^2)---线性对数阶的排序:归并排序(mergesort),快速排序,堆排序,时间复杂度为O(nlogn)在n<=50的情况下,最好使用插入排序或者选择排序,由于选择排序移动次数比插入排序少,在数据量比较多的情况,推荐使用选择排序。如果序列基本上正序了,则使用插入排序、冒泡排序或者随机的快速排序在n非常大的情况下,使用O(nlogn)的算法,即归并排序、快速排序、堆排序。后2者是不稳定的排序,而merge排序是稳定的排序方式,快速排序是基于比较的排序中的最好的排序方法。实验条件下算法运行时间:(单位毫秒,10万随机数)冒泡排序:56953选择排序:20109插入排序:14547归并排序:134堆排序:67快速排序:28三种O(nlogn)的排序时间比较为:排序算法10万100万1000万归并排序134130913985堆排序6786514292快速排序285139815几种排序算法介绍一、插入排序(InsertionSort):每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。:【示例】:[初始关键字][49]38659776132749J=2(38)[3849]659776132749J=3(65)[384965]9776132749J=4(97)[38496597]76132749J=5(76)[3849657697]132749J=6(13)[133849657697]2749J=7(27)[13273849657697]49J=8(49)[1327384949657697](VarR:FileType);2.//对R[1..N]按递增序进行插入排序,R[0]是监视哨//:=2ToNDo//依次插入R[2],...,R[n]//[0]:=R;J:=I-1;[0]<R[J]Do//查找R的插入位置//[J+1]:=R[J];//将大于R的元素后移//:=J-[J+1]:=R[0];//插入R//;//InsertSort//复制代码二、:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。:【示例】:初始关键字[4938659776132749]第一趟排序后13,38659776492749]第二趟排序后1327,659776493849]第三趟排序后132738[9776496549]第四趟排序后13273849[49976576]第五趟排序后1327384949[979776]第六趟排序后132738494976[7697]第七趟排序后13273849497676[97](VarR:FileType);//对R[1..N]进行直接选择排序//:=1ToN-1Do//做N-1趟选择排序//:=I;:=I+1ToNDo//在当前无序区R[I..N]中选最小的元素R[K]//[J]<R[K]ThenK:=;<>IThen//交换R和R[K]//:=R;R:=R[K];R[K]:=Temp;end;;//SelectSort//复制代码三、冒泡排序(BubbleSort):两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。:设想被排序的数组R,1..N,垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"漂浮",如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。【示例】:(VarR:FileType)//从下往上扫描的起泡排序//:=1ToN-