数据结构与算法分析新视角（第2版） 课件 第7、8章 排序、索引与查找.pptx

数据处理方法排序技术Chapter7DataStructuresandAlgorithmAnalysis

主要内容 排序的概念 常见排序方法

学习目标熟悉各种排序方法的特点熟悉各种排序过程及其依据原则

学习排序的目的经典的排序技术，已经被广泛地应用于许许多多的程序语言或数据库当中，甚至它们都已经封装了关于排序算法的实现代码。我们学习排序更多的原因并不是为了去在现实中编程排序算法，而是通过学习来提高我们编写算法的能力，以便于去解决更多复杂和灵活的应用性问题。

概述插入排序交换排序选择排序归并排序分配排序各种排序算法的比较CONTENTS7.17.27.37.47.57.67.7

概述插入排序交换排序选择排序归并排序分配排序各种排序算法的比较CONTENTS7.17.27.37.47.57.67.7

7.1概述7.1.17.1.2排序的基本概念排序算法的分类

问题引入——手机通讯录的查找效率问题姓名电话张东东135XXXXXXXX安小红136XXXXXXXX李小明138XXXXXXXX姓名电话安小红136XXXXXXXX李小明138XXXXXXXX张东东135XXXXXXXX有序？无序？查找效率之差别

7.1概述7.1.17.1.2排序的基本概念排序算法的分类

排序的基本概念排序依据——关键字排序顺序——非递增、非递减、递增、递减排序是对一个无序序列R，按照其关键字K以指定的顺序调整无序序列，最终得到有序序列的过程。排序

排序中的相关问题关键字K的确定依据在排序过程中关键字K可以是某一确定的依据（以上一实例为例，可以采用联系人姓拼音首字母为依据，也可以采用联系人姓笔画书目为依据），也可以是若干依据的组合，在使用上非常灵活。关键字相同情形的处理原则稳定排序——如果存在关键字相等的两个记录，如R3和R5，排序之前R3在R5的前面，在排序后R3依然在R5的前面不稳定排序算法——若可能使R5在R3的前面，则称所采用的排序算法是不稳定的。排序记录的存放内部排序——内部排序指将待排序记录放在计算机随机存储器中进行排序的过程，整个过程中不涉及到外部存储操作；外部排序——外部排序指待排序的记录数量十分巨大，内存无法一次容纳全部记录，因此在排序过程中必须借助外部存储操作的排序算法。

7.1概述7.1.17.1.2排序的基本概念排序算法的分类

排序的分类按算法复杂度分类简单的排序算法O(n2)先进的排序算法??(??log??)基数排序O(d*n)（注：n是排序元素个数，d是数字位数）按照排序过程中依据操作分类插入排序交换排序选择排序归并排序分配排序比较指关键字之间的比较。移动指记录从一个位置移动到另一个位置在内排序中，主要进行两种操作：比较和移动。

概述插入排序交换排序选择排序归并排序分配排序各种排序算法的比较CONTENTS7.17.27.37.47.57.67.7

7.2插入排序7.2.17.2.2直接插入排序希尔排序

7.2插入排序7.2.17.2.2直接插入排序希尔排序

直接插入排序——基本思想抓牌整理法——每次拿到一张牌后把它插入到手上的牌中适当的位置每次从数列中取一个还没有取出过的数，并按照大小关系插入到已经取出的数中使得已经取出的数仍然有序。算法思想

直接插入排序——伪代码描述for(从第二个数据开始对所有数据循环处理){if（第i个数据小于它之前的第i-1个数据）{将第i个数据复制到一个空闲空间临时存储，这个空间为“哨兵”在前i-1个数据中寻找合适的位置，将从该位置开始的元素全部后移将哨兵数据插入到合适位置}}

直接插入排序——代码实现/*==========================================================函数功能：直接插入排序函数输入：数组首地址*a，数组长度n函数输出：无==========================================================*/算法效率：O(n*n)

直接插入排序——例子

7.2插入排序7.2.17.2.2直接插入排序希尔排序

希尔排序——基本思想把一个长序列分割为K个短序列进行高效的直接插入排序，形成一种“基本有序”的顺序；再调用直接插入排序算法，对全体记录进行一个高效的排序。算法思想希尔排序是对直接插入排序的一个改进，其中的一个重点是将每间隔k个数组成新的短子序列

希尔排序的例子对数列{49,38,65,97,76,13,27,49,55,04}进行排序例k=5个短序列对每个短序列进行排序希尔排序第一趟排序结果

希