山东大学《数据结构》讲义07排序.docx
需积分: 3 115 浏览量
2022-12-15
21:38:34
上传
评论
收藏 34KB DOCX 举报
第七章排序
内容概述：
我们居住在一个迷惑于如何保存信息的世界里，为了寻找出路，人们必须以某 种切合
实际的顺序来保存信息。本章我们考虑数据处理中经常遇到的问题一排 序，主要内容包
括：排序的基本概念；插入排序、交换排序、堆排序、归并排序 等内排序方案及实现
算法；外排序简介。
重点与难点：
重点为插入、交换、选择等基本排序方法和改进的排序方法，归并排序算法及基 数排
序算法。
难点为快速排序算法、堆排序算法和归并排序算法。
思考与习题：
1 .从时间复杂度的角度对排序方法进行归类。
2 .在所有排序方法中，关键字比拟的次数与记录的初始排列次序无关有哪些？
3 .空间复杂度最正确的排序方法有哪些？
4 .从算法的简单性角度对排序方法进行归类.序列{503, 17, 512, 908, 170, 897,
275, 653, 426, 154, 509,
612, 677, 765, 703, 94},请给出采用希尔排序法（dl=8）对该序列作升序 排序时的
每一趟的结果。
5 .序列{70, 83, 100, 65, 10, 32, 7, 9},请给出采用插入排序法对该 序列作升序排序
时的每一趟的结果。
6 .序列{10, 18, 4, 3, 6, 12, 1, 9, 18, 8},请给出采用归并排序法 对该序列作升序排序
时的每一趟的结果。
7 .采用单链表作存储结构，编写一个采用选择排序方法进行升序排序的算法〃将有序
的P[i・.m]和P[m+L・n]归并为有序的Q[i..n]
剩余10页未读，继续阅读
资源评论
