《数据结构——C++实现 教学课件 ppt 作者 缪淮扣 顾训穰 沈俊数据结构-第九章》由会员分享，可在线阅读，更多相关《数据结构——C++实现 教学课件 ppt 作者 缪淮扣 顾训穰 沈俊数据结构-第九章（110页珍藏版）》请在金锄头文库上搜索。
1、数据结构 C+实现 第九章 排序 缪淮扣 顾训穰 沈 俊 编著 科 学 出 版 社,新世纪计算机专业系列教材,所谓排序(Sorting)就是对数据元素集合建立某种有序排列的过程。 排序在计算机软件系统设计中占有相当重要的地位，特别是在事务处理系统中，需要经常对有关的数据排序，以便提高检索等操作的效率。 本章将介绍一些常用的排序算法，它们有：交换排序、插入排序、选择排序、归并排序和基数排序，并对有关的算法进行性能分析和对比。,基础知识,1排序：设含有n个数据元素的数据表为： R0、R1、Rn-1， 其相应的关键字序列为： K0、K1、Kn1。 所谓排序，是确定0、1、n-1的一种排列p0、p1、
2、pn-1，使各关键字满足如下的递增(或递减)关系： Kp0Kp1Kpn1或Kp0Kp1Kpn1,2排序的稳定性：如果在排序表中任意两个数据元素Ri和Rj（ij），它们的关键字KiKj，且在排序之前，数据元素Ri排在Rj的前面， 如果在排序之后，数据元素Ri仍在数据元素Rj的前面，即不改变关键字相同的数据元素在排序前、后的相对位置，则称这种排序方法是稳定的，否则称这种排序方法是不稳定的。 3内部排序与外部排序：根据在排序过程中数据元素是否全部在内存中进行，排序可分为两大类：内排序和外排序。 内排序是指在排序过程中数据元素全部存放在内存进行的排序； 外排序是指由于数据元素太多，在排序期间全部数据元
3、素不能同时存放在内存中，必须在排序过程中，不断地在内存和外存之间交换数据元素的排序。,4排序的效率：排序算法的效率可以从时间复杂度和空间复杂度两个方面来分析。 排序算法的时间复杂度可用排序过程中的数据元素之关键字的比较次数与数据元素的移动次数来衡量。 在本章下面各节讨论算法的时间复杂度时一般都按平均时间复杂度进行估算；对于那些受排序表中数据元素的初始排列及数据元素数目影响较大的算法，按最好情况和最坏情况进行分别估算。 算法的空间复杂度为算法执行时所需的附加存储空间。,排序表的抽象数据类型描述和类定义,顺序表表示的排序表中数据元素的抽象数据类型描述 : ADT element is Data 数
4、据元素的关键字 数据元素的其他信息 Operation element 初始化值：无 动作：构造一个数据元素,getKey 输入：无 前置条件：无 动作：取数据元素关键字 输出：数据元素关键字key 后置条件：无,setKey 输入：k 前置条件：无 动作：把数据元素关键字设置为k 输出：无 后置条件：无,= 输入：x 前置条件：无 动作：数据元素的值赋为x 输出：无 后置条件：无,= 输入：k 前置条件：无 动作：判数据元素关键字key是否等于 输入值k 输出：1或0 后置条件：无,!= 输入：k 前置条件：无 动作：判数据元素关键字key是否不等于输入值k 输出：1或0 后置条件：无,=
5、输入：k 前置条件：无 动作：判数据元素关键字key是否小于等于输入值k 输出：1或0 后置条件：无,= 输入：k 前置条件：无 动作：判数据元素关键字key是否大于等于输入值k 输出：1或0 后置条件：无, 输入：k 前置条件：无 动作：判数据元素关键字key是否小于输入值k 输出：1或0 后置条件：无, 输入：k 前置条件：无 动作：判数据元素关键字key是否大于输入值k 输出：1或0 后置条件：无 end ADT element,用顺序表表示的排序表的抽象数据类型描述，它包括存储排序表的向量，排序表的长度，并提供对排序表中数据元素进行交换位置的操作。 ADT sortlist is Da
6、ta 存储数据元素的向量 数据表中数据元素的当前个数,Operation sortlist 初始化值：无 动作：构造排序表 swap 输入：两个数据元素x和y 前置条件：无 动作：数据元素x和y交换位置 输出：交换位置后的数据元素x和y 后置条件：无 end ADT sortlist,下面给出用顺序表表示的排序表的类定义: const int MaxSize = 100; template class sortlist template class element /数据元素的类定义 friend class sortlist ; private: Type key;/数据元素的关键字 oth
7、er; /其它信息,public: element ( ) ; /构造函数 Type getKey ( ) return key; /取数据元素关键字 void setKey ( const Type k ) key = k; /修改数据元素关键字 element ,int operator != ( Type ,template class sortlist protected: element * Arr; /存储数据元素的向量（排序表） int CurrentSize; /数据表中数据元素的个数 public: sortlist ( ) : CurrentSize (0) Arr = n
8、ew element MaxSize; /构造函数 sortlist ( ) delete Arr ; /析构函数 void swap ( element /数据元素x和y交换位置 ,下面给出用链表表示的排序表的类定义: const int MaxSize = 100; template class sortlinklist template class node /数据元素的类定义 friend class sortlinklist ; private: Type key;/数据元素的关键字 int next; /后继指针 other; /其它信息,public: node( ) ; /构造
9、函数 Type getKey ( ) return key; /取数据元素关键字 void setKey ( const Type k ) key = k; /修改数据元素关键字 int getLink ( ) return next; /取结点的后继指针 void setKey ( const int p ) next = p; /修改结点的后继指针 int operator = ( Type ,template class sortlinklist protected: node * Arr; /存储排序表结点的向量（静态链表） int CurrentSize; /排序表中的结点个数 pu
10、blic: sortlinklist ( ) : CurrentSize (0) Arr = new node MaxSize; /构造函数 sortlinklist ( ) delete Arr ; /析构函数 ,交换排序,交换排序的基本思想： 对排序表中所有两两相邻的数据元素的关键字进行比较，如果发生逆序(即排列顺序与排序后的次序正好相反)，则两者交换位置，直到所有数据元素都排好序为止。 在本节中，将介绍两种交换排序的方法：冒泡排序和快速排序。,冒泡排序,算法思想是： 设排序表中有n个数据元素，首先对排序表中第一、二个数据元素的关键字Arr0.Key和Arr1.Key进行比较，如果Arr0
11、.KeyArr1.Key，则交换Arr0和Arr1; 然后对第二、三个数据元素做同样处理；重复此过程直到处理完最后两个相邻的数据元素。,冒泡排序示例：,冒泡排序的算法: template void BubbleSort (sortlist ,在最坏情形下总的关键字比较次数和数据元素移动次数分别为：,因此在最坏情况下，冒泡排序的时间复杂度为O(n2）。冒泡排序需要一个附加存储空间以实现数据元素的交换。 冒泡排序算法是一种稳定的排序方法。,快速排序,快速排序（Quick Sort）又被称做分区交换排序，这是一种平均性能非常好的排序方法。 其算法基本思想是：任取排序表中的某个数据元素(例如取第一个数
12、据元素)作为基准，按照该数据元素的关键字大小，将整个排序表划分为左右两个子表： 左侧子表中所有数据元素的关键字都小于或等于基准数据元素的关键字。 右侧子表中所有数据元素的关键字都大于基准数据元素的关键字，基准数据元素则排在这两个子表中间(这也是该数据元素最终应安放的位置)， 然后分别对这两个子表重复施行上述方法的快速排序，直到所有的子表长度为1，则排序结束。,快速排序过程示例：,快速排序算法的描述如下： template void QuickSort ( sortlist ,Table.Arri= temp /将基准元素就位 QuickSort ( list, low, i-1); /在左子区
13、间递归进行快速排序 QuickSort ( list, i+1, high ); /在右子区间递归进行快速排序 ,在n个元素的序列中，对一个数据元素定位所需时间为0(n)。 若设T(n)是对n个元素的序列进行排序所需的时间，而且每次对一个数据元素正确定位后，正好把排序表划分为长度相等的两个子表。 此时，总的计算时间为： T(n) cn + 2T(n/2 ) 其中，c是一个常数 cn + 2( cn/2 + 2T(n/4) = 2cn + 4T(n/4) 2cn + 4( cn/4 +2T(n/8) = 3cn + 8T(n/8) cnlog2n + nT(1) =O(nlog2n),在一般情况
14、下，设选为基准的数据元素是关键字第k小的，且等概率地取1、2、n，则有：,就是快速排序的平均计算时间，可以用归纳法证明，这个时间数量级也为0(nlog2n)。 由于快速排序是递归的，就需要有一个栈存放每层递归调用时的指针和参数，其最大递归调用层次数与递归树的深度一致，理想情况为log2(n+1)，因此，要求的存储开销为0(log2n)。 快速排序是一种不稳定的排序方法。,插入排序,插入排序的基本思想是： 每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。 开始时建立一个初始的有序序列，它只包含一个数据元素。 然后，从这个的初始序列开始不断进行插入数据元素
15、，直到最后一个数据元素插入到有序序列后，整个排序工作就完成了。,直接插入排序,算法基本思想是： 开始时把第一个数据元素作为初始的有序序列， 然后依次从第二个数据元素开始把数据元素按关键字大小插入到已排序的部分排序表的适当位置。 当插入第i(1in)个数据元素时，前面的i-1个数据元素已经排好序，这时，用第i个数据元素的关键字与前面的i-1个数据元素的关键字顺序进行比较，找到插入位置后就将第i个数据元素插入，原来位置及其以后的数据元素都向后顺移一个位置。 如此进行n-1次插入就完成了排序。,顺序表上的直接插入排序,在顺序表上进行直接插入排序过程 ：,直接插入排序算法的C+描述： template void InsertionSort (sortlist ,在最好情况下，即在排序前数据元素已经按关键字大小从小到大排好序了， 每趟只需与前面的有序数据元素序列的最后一个数据元素的关键字比较1次，移动2次数据元素。 所以，总的关键字比较次数为n-1，数据移动次数为2(n-1)，因此最好情况下的时间复杂度为O(n）； 在最坏情况下，即第i趟插入时，第i+1个数据元素必须与前面i个数据元素都做关键字的比较，并且每做1次比较就要做1次数据元素移动， 则总的关键字比较次数和数据移动次数分别为：,因此最坏情况下的时间复杂度为O(n
