数据结构课件-第10章.pdf

数据结构与算法 Data Structure and Algorithm 第10章 排序 目 录 10．1 基本概念 10．2 插入排序 10．3 交换排序 10．4 选择排序 10．5 归并排序 10. 6 基数排序 退出 10．1 基本概念 10.1.1 排序介绍 排序 （Sorting ）是数据处理中一种很重要的运算， 同时也是很常用的运算，一般数据处理工作25% 的时间都 在进行排序。 简单地说，排序就是把一组记录 （元素）按照某个域 的值的递增 （即由小到大）或递减 （即由大到小）的次序 重新排列的过程。 表10-1 学生档案表 学号 姓名 年龄 性别 99001 王晓佳 18 男 99002 林一鹏 19 男 99003 谢宁 17 女 99004 张丽娟 18 女 99005 周涛 20 男 99006 李小燕 16 女 10.1.2 基本概念 1．内排序与外排序 按照排序过程中使用内外存的不同将排序方法分为内 排序和外排序。 若排序过程全部在内存中进行，则称为内排序； 若排序过程需要不断地进行内存和外存之间的数据交 换，则称为外排序。 本章仅讨论内排序。 2 ．稳定性 因为排序码可以不是记录的关键字，同一排序码值可能 对应多个记录。对于具有同一排序码的多个记录来说，若采 用的排序方法使排序后记录的相对次序不变，则称此排序方 法是稳定的，否则称为不稳定的。 例如： 数据项 1 2 2+ 8 3 8+ 排序后 1 2 2+ 3 8 8+ 稳定 1 2+ 2 3 8+ 8 不稳定 3．内部排序分类 插入排序（直插排序、二分排序、希尔排序） 交换排序（冒泡排序、快速排序） 排序 选择排序 （直选排序、树型排序、堆排序） 归并排序（二路归并排序、多路归并排序） 分配排序 （多关键字排序、基数排序） 2 简单排序法 O(n ) 排序 先进排序法O(nlogn) 基数排序 O(d n) * 4 ．排序的时间复杂性 排序过程主要是对记录的排序码进行比较和记录的 移动过程。因此排序的时间复杂性可以算法执行中的数据 比较次数及数据移动次数来衡量。当一种排序方法使排序 过程在最坏或平均情况下所进行的比较和移动次数越少， 则认为该方法的时间复杂性就越好，分析一种排序方法， 不仅要分析它的时间