文档详情

《数据结构》课件(C语言) 第10讲.ppt

发布:2017-06-20约字共72页下载文档
文本预览下载声明
《数据结构》 第十章 内部排序 第十章 内部排序 内容和要求 排序及有关的概念,直接插入排序、二分法插入排序、表插入排序,shell 排序,直接选择排序、树形选择排序、堆排序、冒泡排序和快速排序、基数排序、归并排序。 要求通过学习,掌握排序的各种方法,为解决实际问题奠定理论基础的技术基础。了解排序和排序码的概念, 熟悉直接插入排序、二分法插入排序、表插入排序、Shell排序的方法和时空复杂性; 掌握堆排序、快速排序、基数排序、归并排序的基本思路,排序方法,算法的主要步骤和时空复杂性; 知道 shell 排序和树形选择排序方法。 概 述 如何对一大批按关键字无序的数据元素或记录,高效率地将它们重新排列成一个按关键字有序的序列,是计算机应用中的重要课题之一。 可以假定被排序的对象是由一组记录组成的文件,而记录则由若干个数据项(或字段、域)组成,其中有一项可用来标识一个记录,称为关键字,它具关键字值。关键字是排序操作的依据。 概 述 定义1: 假设含 n 个记录的序列为 {R1,R2,···,Rn} (10-1) 其相应的关键字序列为 {K1,K2,···,Kn} 需确定 1,2,···,n 的一种排列 P1,P2,···,Pn ,使其相应的关键字满足如下的非递减(或非递增)关系 Kp1≤Kp2 ≤ ··· ≤ Kpn (10-2) 即使式 (10-1) 的序列成为一个按关键字有序的序列 {Rp1,Rp2 , ···, Rpn } (10-3) 这样一种操作称为排序。 概 述 定义2: 如果待排序的文件中,存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的;反之,若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。 概 述 概 述 在排序的过程中需进行的两种基本操作: (1) 比较两个关键字的大小; (2) 将记录从一个位置移动至另一个位置。 前一个操作对大多数排序方法来说都是必要的,而 后一种操作可以通过改变记录的存储方式来予以避免。 概 述 插 入 排 序 插入排序的基本思想是:每次将一个待排序的记录,按其关键字的大小插入到前面已经排好序的表或文件中的适当位置,直到全部插入完为止。 示例1 设待排关键字集合为 {49,38,65,97,76,13,27,49} [初始关键字] (49) 38 65 97 76 13 27 49 i=2 (38) (38 49) 65 97 76 13 27 49 i=3 (65) (38 49 65) 97 76 13 27 49 i=4 (97) (38 49 65 97) 76 13 27 49 i=5 (76) (38 49 65 76 97) 13 27 49 i=6 (13) (13 38 49 65 76 97) 27 49 i=7 (27) (13 27 38 49 65 76 97) 49 i=8 (49) (13 27 38 49 49 65 76 97) ↑监视哨 图 10.1 直接插入排序示例 直接插入排序算法描述(n 个记录,共进行 n-1 趟插入) straisort( SqList l ) //对 r[1..n] 进行直接插入排序,执行本算法后,r[1..n] 中的记录按关键字非递减有序排列 { for( i = 2; i = l.Length; i++ ) if( l.r[i].key l.r[i-1].key ) { l.r[0] = l.r[i]; for( j = i – 1; l.r[0].key l.r[j].key; j-- )
显示全部
相似文档