排序算法分析比较.doc
《排序算法分析比较.doc》由会员分享,可在线阅读,更多相关《排序算法分析比较.doc(8页珍藏版)》请在三一文库上搜索。
1、精品论文推荐排序算法分析比较王晓宇 北京邮电大学信息与通信工程学院,北京(100876) E-mail: 摘要:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序是程序设计中非常重要的内容,其算法种类繁多,排序算法的选择会 直接影响到计算的效率。由于实际工作中处理的数据量巨大,所以排序算法对算法本身的速度要求很高。排序的主要性能指标有算法执行时间、算法本身的复杂度和算法的稳定度。常 用的排序算法主要有:插入排序、选择排序、冒泡排序、快速排序和堆排序等,本文主要介 绍这几种常用的排序算法原理、算法实现和排序性能,并比较他们的异同,最后根据分析的结果总结出
2、在不同情况选择不同的排序算法以提高排序效率。关键词:插入排序;选择排序;冒泡排序;快速排序;堆排序 中图分类号:TP3931.引言由于记录的形式、数量和所存放的存储设备不同,排序所采用的方法也不同,不同的排 序方法影响排序的效率。本文主要是讨论常用排序的各种典型方法和算法。常用排序的方法 很多,如果按照排序过程中依据的不同原则对常用排序方法进行分类,则主要有:插人排序、 选择排序、冒泡排序、快速排序和堆排序等五类。为了比较各种排序算法的优劣,要分析算 法的时间复杂性和稳定性,评价排序的另一个主要标准是执行算法所需要的附加空间1。2.常用排序算法2.1 插入排序2.1.1 基本思想 每次将一个待
3、排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。2.1.2 排序过程【示例】:初始关键字 49 38 65 97 76 13 27 49J=2(38) 38 49 65 97 76 13 27 49J=3(65) 38 49 65 97 76 13 27 49J=4(97) 38 49 65 97 76 13 27 49J=5(76) 38 49 65 76 97 13 27 49J=6(13) 13 38 49 65 76 97 27 49J=7(27) 13 27 38 49 65 76 97 49J=8(49) 13 27 38
4、49 49 65 76 97Procedure InsertSort(Var R : FileType); /对 R1.N按递增序进行插入排序, R0是监视哨/ Beginfor I := 2 To N Do/依次插入 R2,.,Rn/beginR0 := RI; J := I - 1;- 8 -While R0 RJ Do/查找 RI的插入位置/beginRJ+1 := RJ;/将大于 RI的元素后移/ J := J - 1endRJ + 1 := R0 ;/插入 RI /endEnd;/InsertSort /直接插人排序算法简洁,易理解,容易实现。当序列中的记录“基本有序”或 n 值较小
5、时, 它是最佳的排序方法。但是,通常待排记录的数量 n 很大,此时直接插人排序就不适用了。 显然,这个方法是稳定的,且直接插人排序的时间复杂性为饰为。从空间来看,它只需要一 个记录。2.2 选择排序2.2.1 基本思想 每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。2.2.2 排序过程【示例】:初始关键字 49 38 65 97 76 13 27 49 第一趟排序后 13 38 65 97 76 49 27 49 第二趟排序后 13 27 65 97 76 49 38 49 第三趟排序后 13 27 38 97 76 49
6、65 49 第四趟排序后 13 27 38 49 49 97 65 76 第五趟排序后 13 27 38 49 49 97 97 76 第六趟排序后 13 27 38 49 49 76 76 97 第七趟排序后 13 27 38 49 49 76 76 97 最后排序结果 13 27 38 49 49 76 76 97Procedure SelectSort(Var R : FileType);/对 R1.N进行直接选择排序 / Beginfor I := 1 To N - 1 Do/做 N - 1 趟选择排序/beginK := I;For J := I + 1 To N Do/在当前无序区
7、 RI.N中选最小的元素 RK/beginIf RJ RK Then K := Jend;If K I Then/交换 RI和 RK /begin Temp := RI; RI := RK; RK := Temp; end;endEnd./SelectSort /关于选择排序算法,由于其主要部分为两层嵌套的 for 循环,显然可以看出,其时间复杂性为 0(n2) 2。在实现中,如果记录较大,为了减少调整记录位置的时间,可以用一个辅 助数组存放指向各个记录的指针。交换时只需交换相应指针的相对位置。经过排序,所有指 针将按相应记录键值不减的顺序排列。最后如果需要,可以一次性地按指针的顺序整理记录的
8、实际位置。选择排序算法简单、易懂、容易实现。该算法适宜 n 较大的情况;因为当 n 较大时速度 受到影响。选择排序是不稳定的。2.3 冒泡排序2.3.1 基本思想 两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。2.3.2 排序过程设想被排序的数组 R1.N垂直竖立,将每个数据元素看作有重量的气泡,根据轻气 泡不能在重气泡之下的原则,从下往上扫描数组 R,凡扫描到违反本原则的轻气泡,就使其 向上漂浮,如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。【示例】:49 13 13 13 13 13 13 1338 49 27 27 27
9、 27 27 2765 38 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97 65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97Procedure BubbleSort(Var R : FileType) /从下往上扫描的起泡排序/ BeginFor I := 1 To N-1 Do/做 N-1 趟排序/beginNoSwap := True;/置未排序的标志/ For J := N - 1 DownTo 1 Do/从底部往上扫描
10、/ beginIf RJ+1= X) And (I J) Do beginJ := J - 1/从右向左扫描,查找第 1 个小于 X 的元素/If I J Then/已找到 RJ X/beginRI := RJ;/相当于交换 RI和 RJ/ I := I + 1end;While (RI = X) And (I J) DoI := I + 1/从左向右扫描,查找第 1 个大于 X 的元素/end;If I X /beginRJ := RI;/相当于交换 RI和 RJ/ J := J - 1endUntil I = J;RI := X/基准 X 已被最终定位/ End; /Parttion /P
11、rocedure QuickSort(Var R :FileType; S,T: Integer);/对 RS.T快速排序/BeginIf S T Then/当 RS.T为空或只有一个元素是无需排序/beginPartion(R, S, T, I);/对 RS.T做划分/ QuickSort(R, S, I-1); /递归处理左区间 RS,I-1/ QuickSort(R, I+1,T);/递归处理右区间 RI+1.T /end;End./QuickSort/要把递归算法改写成非递归算法,可引进一个栈,这个栈的大小取决于递归调用的深度, 最多不会超过 n,如果每次都选较大的部分进栈,处理较短的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排序 算法 分析 比较
链接地址:https://www.31doc.com/p-3625303.html