`
- 浏览:
66797 次
- 性别:
- 来自:
黑龙江
-
排序方法比较
以关键字序列(265,301,751,129,937,863,742,694,076,438)为例,分别写出执行以下排序算法的各趟排序结束时,关键字序列的状态。
(1) 直接插入排序 (2)希尔排序 (3)冒泡排序 (4)快速排序
(5) 直接选择排序 (6) 堆排序 (7) 归并排序 (8)基数排序
上述方法中,哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。
(1)直接插入排序:(方括号表示无序区)
初始态: 265[301 751 129 937 863 742 694 076 438]
第一趟:265 301[751 129 937 863 742 694 076 438]
第二趟:265 301 751[129 937 863 742 694 076 438]
第三趟:129 265 301 751[937 863 742 694 076 438]
第四趟:129 265 301 751 937[863 742 694 076 438]
第五趟:129 265 301 751 863 937[742 694 076 438]
第六趟:129 265 301 742 751 863 937[694 076 438]
第七趟:129 265 301 694 742 751 863 937[076 438]
第八趟:076 129 265 301 694 742 751 863 937[438]
第九趟:076 129 265 301 438 694 742 751 863 937
(2)希尔排序(增量为5,3,1)
初始态: 265 301 751 129 937 863 742 694 076 438
第一趟:265 301 694 076 438 863 742 751 129 937
第二趟:076 301 129 265 438 694 742 751 863 937
第三趟:076 129 265 301 438 694 742 751 863 937
(3)冒泡排序(方括号为无序区)
初始态 [265 301 751 129 937 863 742 694 076 438]
第一趟: 076 [265 301 751 129 937 863 742 694 438]
第二趟: 076 129 [265 301 751 438 937 863 742 694]
第三趟: 076 129 265 [301 438 694 751 937 863 742]
第四趟: 076 129 265 301 [438 694 742 751 937 863]
第五趟: 076 129 265 301 438 [694 742 751 863 937]
第六趟: 076 129 265 301 438 694 742 751 863 937
(4)快速排序:(方括号表示无序区,层表示对应的递归树的层数)
初始态: [265 301 751 129 937 863 742 694 076 438]
第二层: [076 129] 265 [751 937 863 742 694 301 438]
第三层: 076 [129] 265 [438 301 694 742] 751 [863 937]
第四层: 076 129 265 [301] 438 [694 742] 751 863 [937]
第五层: 076 129 265 301 438 694 [742] 751 863 937
第六层: 076 129 265 301 438 694 742 751 863 937
(5)直接选择排序:(方括号为无序区)
初始态 [265 301 751 129 937 863 742 694 076 438]
第一趟: 076 [301 751 129 937 863 742 694 265 438]
第二趟: 076 129 [751 301 937 863 742 694 265 438]
第三趟: 076 129 265[ 301 937 863 742 694 751 438]
第四趟: 076 129 265 301 [937 863 742 694 751 438]
第五趟: 076 129 265 301 438 [863 742 694 751 937]
第六趟: 076 129 265 301 438 694 [742 751 863 937]
第七趟: 076 129 265 301 438 694 742 [751 863 937]
第八趟: 076 129 265 301 438 694 742 751 [937 863]
第九趟: 076 129 265 301 438 694 742 751 863 937
(6)堆排序:(通过画二*树可以一步步得出排序结果)
初始态 [265 301 751 129 937 863 742 694 076 438]
建立初始堆: [937 694 863 265 438 751 742 129 075 301]
第一次排序重建堆:[863 694 751 765 438 301 742 129 075] 937
第二次排序重建堆:[751 694 742 265 438 301 075 129] 863 937
第三次排序重建堆:[742 694 301 265 438 129 075] 751 863 937
第四次排序重建堆:[694 438 301 265 075 129] 742 751 863 937
第五次排序重建堆:[438 265 301 129 075] 694 742 751 863 937
第六次排序重建堆:[301 265 075 129] 438 694 742 751 863 937
第七次排序重建堆:[265 129 075] 301 438 694 742 751 863 937
第八次排序重建堆:[129 075]265 301 438 694 742 751 863 937
第九次排序重建堆:075 129 265 301 438 694 742 751 863 937
(7)归并排序(为了表示方便,采用自底向上的归并,方括号为有序区)
初始态:[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]
第一趟:[265 301] [129 751] [863 937] [694 742] [076 438]
第二趟:[129 265 301 751] [694 742 863 937] [076 438]
第三趟:[129 265 301 694 742 751 863 937] [076 438]
第四趟:[076 129 265 301 438 694 742 751 863 937]
(8)基数排序(方括号内表示一个箱子共有10个箱子,箱号从0到9)
初始态:265 301 751 129 937 863 742 694 076 438
第一趟:[] [301 751] [742] [863] [694] [265] [076] [937] [438] [129]
第二趟:[301] [] [129] [937 438] [742] [751] [863 265] [076] [] [694]
第三趟:[075] [129] [265] [301] [438] [] [694] [742 751] [863] [937]
在上面的排序方法中,直接插入排序、冒泡排序、归并排序和基数排序是稳定的,其他排序算法均是不稳定的,现举实例如下:以带*号的表示区别。
希尔排序:[8,1,10,5,6,*8]
快速排序:[2,*2,1]
直接选择排序:[2,*2,1]
堆排序:[2,*2,1]
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
实现了几种常见排序方法,并对同一数据操作,比较排序时间,对于各种方法有很直观的感受
《数据结构》内排序方法比较.xlsx
基于C语言的几种排序方法比较.pdf
排序方法比较程序的设计与实现程序设计报告
三种排序方法比较的演示程序——Borland C++ Builder中的多线程应用 一个老师编的
各种排序方法汇总介绍数据结构中的经典排序,并进行比较
对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较(详细文档)源码 即使不是为了实现这个排序方法的比较也可以下载,都有每个排序方法实现的代码 C语言实现
各种内部排序方法及其比较实验报告
List类几种排序方法比较灵活 可以根据自己的需要 选用合适的方法
随即生成一组数据 可以实现三种排序方法的速度比较
交换排序 选择排序 冒泡排序 插入排序
数据结构课程中的对多种排序方法的综合比较
* 通用排序方法 * @param arr 需要排序的数组 * @param field 排序字段 值类型传null 单字段传string 多字段传数组[["field1", SortType], ["field2", SortType]] 可传属性名 方法名 * @param sortType 排序类型...
1. 掌握各种排序的基本思想。 2. 掌握各种排序方法的算法实现。 3. 掌握各种排序方法的优劣分析及花费的...根据排序函数中的核心语句,计算出每种排序方法的时间复杂度级=及空间复杂度,分析几种排序方法的优劣。
字符串排序方法 javaScript中的字符串排序。
几种不同的排序方法的算法比较,插入排序,快速排序,选择排序,堆排序等
1、包含归并与快速排序的不同实现方法的比较 2、C++实现各种常见排序方法及比较 3、排序方法适用场合的建议 4、参考源程序
数据结构报告c++,简单选择排序,冒牌排序,插入排序,快速排序,两路合并排序,堆排序,几种排序方法的比较,有详细的源代码和实验报告
C语言排序方法及代码 C语言排序方法及代码
实验项目名称:COP2000实验仪中排序方法探讨 (4学时) 一、实验目的 综合运用所学计算机原理知识,设计微程序实现题目规定的...综上所述:本次试验目标至少做出一种排序方法,并在此基础之上比较各种排序方法的效率。