第9章排序 数据结构(C++描述)
第9章 排序 数据结构（C++描述）
目录 9.1基本概念 9.2插入排序 9.3交换排序 9.4选择排序 9.5归并排序 9.6分配排序 退出
目录 9．1 基本概念 9．2 插入排序 9．3 交换排序 9．4 选择排序 9．5 归并排序 *9. 6 分配排序 退出
9.1基本概念 9.1.1排序介绍 排序( Sorting)是数据处理中一种很重要的运算, 同时也是很常用的运算,一般数据处理工作25%的 时间都在进行排序。简单地说,排序就是把一组记 录(元素)按照某个域的值的递增(即由小到大) 或递减(即由大到小)的次序重新排列的过程 表9-1学生档案表 学号 姓名 年龄 性别 99001 王晓佳 18 男 99002 林一鹏 男 99003 谢宁 17 女 99004 张丽娟 18 99005 周涛 男 99006 李小燕 女
9．1 基本概念 9.1.1 排序介绍 排序（Sorting）是数据处理中一种很重要的运算， 同时也是很常用的运算，一般数据处理工作25%的 时间都在进行排序。简单地说，排序就是把一组记 录（元素）按照某个域的值的递增（即由小到大） 或递减（即由大到小）的次序重新排列的过程。 表9-1 学生档案表 学号 姓名 年龄 性别 99001 王晓佳 18 男 99002 林一鹏 19 男 99003 谢宁 17 女 99004 张丽娟 18 女 99005 周涛 20 男 99006 李小燕 16 女
?例如,在表9-1中,若以每个记录的学号为关键字,按 x排序码年龄的递增(由小到大)排序,则所有记录的排 序结果可简记为: y((990,16),(9903,17),(990,18) (99004,18),(99002,19),(99005,20)}; 也可能为 (99006,16),(99003,17),(99004,18) (99001,18),(99002,19),(99005,20)}; 这两个结果都是表9-1按年龄的递增排序结果。若按排序 码姓名来进行递增排序,则得到的排序结果为: (99006,李小燕),(990,林一鹏),(99001, 王晓佳),(99003,谢宁),(9004,张丽娟), (99005,周涛)} 当然,我们还可以按排序码性别来进行递增排序,在此 不再作进一步的分析
例如，在表9-1中，若以每个记录的学号为关键字，按 排序码年龄的递增（由小到大）排序，则所有记录的排 序结果可简记为： {（99006，16），（99003，17），（99001，18）， （99004，18），（99002，19），（99005，20）}； 也可能为： {（99006，16），（99003，17），（99004，18）， （99001，18），（99002，19），（99005，20）}； 这两个结果都是表9-1按年龄的递增排序结果。若按排序 码姓名来进行递增排序，则得到的排序结果为： {（99006，李小燕），（99002，林一鹏），（99001， 王晓佳），（99003，谢宁），（99004，张丽娟）， （99005，周涛）} 当然，我们还可以按排序码性别来进行递增排序，在此 不再作进一步的分析
飞它?9.12基本概念 1.排序码( Sort Key) 作为排序依据的记录中的一个属性。它可以是任何一种 可比的有序数据类型,它可以是记录的关键字,也可以 是任何非关键字。如上例中的学生年龄。在此我们认为 对任何一种记录都可找到一个取得它排序码的函数 Skey(一个或个关键字的组合)。 2.有序表与无序表 组记录按排序码的递增或递减次序排列得到的结果被 称之为有序表,相应地,把排序前的状态称为无序表。 3.正序表与逆序表 若有序表是按排序码升序排列的,则称为升序表或正序 表,否则称为降序表或逆序表。不失普遍性,我们一般 只讨论正序表
9.1.2 基本概念 1．排序码（Sort Key） 作为排序依据的记录中的一个属性。它可以是任何一种 可比的有序数据类型，它可以是记录的关键字，也可以 是任何非关键字。如上例中的学生年龄。在此我们认为 对任何一种记录都可找到一个取得它排序码的函数 Skey(一个或个关键字的组合)。 2．有序表与无序表 一组记录按排序码的递增或递减次序排列得到的结果被 称之为有序表，相应地，把排序前的状态称为无序表。 3．正序表与逆序表 若有序表是按排序码升序排列的，则称为升序表或正序 表，否则称为降序表或逆序表。不失普遍性，我们一般 只讨论正序表
定它?4.排序定义 若给定一组记录序列r1,r,,…,rn,其排序码分别 为s1 ,sn,将这些记录排成顺序为rk 2,…,rm的一个序列R,满足条件s1≤2≤…≤Sn, 获得这些记录排成顺序为rn,rn2,…,rmn的一个序 列R,满足条件25…m的过程称为排序。 也可以说,将一组记录按某排序码递增或递减排列的 过程,称为排序 5.稳定与不稳定 因为排序码可以不是记录的关键字,同一排序码值可能对应 多个记录。对于具有同一排序码的多个记录来说,若采用的 排序方法使排序后记录的相对次序不变,则称此排序方法是 稳定的,否则称为不稳定的。在上例中(见表9-1,按年龄排 序),如果一种排序方法使排序后的结果必为前一个结果, 则称此方法是稳定的;若一种排序方法使排序后的结果可能 为后一个结果,则称此方法是不稳定的
4．排序定义 若给定一组记录序列r 1 ，r 2 ，…，r n，其排序码分别 为s1，s2 ，…，sn ，将这些记录排成顺序为r k1 ， r k2 ，…，r kn的一个序列R’，满足条件sk1 ≤sk2 ≤ …≤skn， 获得这些记录排成顺序为r p1 ，r p2 ，…，r pn的一个序 列R”，满足条件sp1 ≤sp2 ≤ …≤spn的过程称为排序。 也可以说，将一组记录按某排序码递增或递减排列的 过程，称为排序。 5．稳定与不稳定 因为排序码可以不是记录的关键字，同一排序码值可能对应 多个记录。对于具有同一排序码的多个记录来说，若采用的 排序方法使排序后记录的相对次序不变，则称此排序方法是 稳定的，否则称为不稳定的。在上例中（见表9-1，按年龄排 序），如果一种排序方法使排序后的结果必为前一个结果， 则称此方法是稳定的；若一种排序方法使排序后的结果可能 为后一个结果，则称此方法是不稳定的
6.内排序与外排序 按照排序过程中使用内外存的不同将排序方法分为内排序 和外排序。若排序过程全部在内存中进行,则称为内排序 若排序过程需要不断地进行内存和外存之间的数据交换 则称为外排序。内排序大致可分为五类:插入排序、交换 排序、选择排序、归并排序和分配排序。本章仅讨论内排 序 入7.排序的时间复杂性 排序过程主要是对记录的排序码进行比较和记录的移动过 程。因此排序的时间复杂性可以算法执行中的数据比较次 数及数据移动次数来衡量。当一种排序方法使排序过程在 最坏或平均情况下所进行的比较和移动次数越少,则认为 该方法的时间复杂性就越好,分析一种排序方法,不仅要 分析它的时间复杂性,而且要分析它的空间复杂性、稳定 性和简单性等
6．内排序与外排序 按照排序过程中使用内外存的不同将排序方法分为内排序 和外排序。若排序过程全部在内存中进行，则称为内排序； 若排序过程需要不断地进行内存和外存之间的数据交换， 则称为外排序。内排序大致可分为五类：插入排序、交换 排序、选择排序、归并排序和分配排序。本章仅讨论内排 序。 7．排序的时间复杂性 排序过程主要是对记录的排序码进行比较和记录的移动过 程。因此排序的时间复杂性可以算法执行中的数据比较次 数及数据移动次数来衡量。当一种排序方法使排序过程在 最坏或平均情况下所进行的比较和移动次数越少，则认为 该方法的时间复杂性就越好，分析一种排序方法，不仅要 分析它的时间复杂性，而且要分析它的空间复杂性、稳定 性和简单性等
它:?为了以后讨论方便,我们直接将排序码写成一个一维数 ′组的形式,具体类型设为 Elemtype,并且在没有声明的情 形下,所有排序都按排序码的值递增排列 插入排序(直插排序、二分排序、希尔排序) 交换排序(冒泡排序、快速排序) 排序选择排序(直选排序、树型排序、堆排序) 归并排序(二路归并排序、多路归并排序) 分配排序(多关键字排序、基数排序)
为了以后讨论方便，我们直接将排序码写成一个一维数 组的形式，具体类型设为Elemtype，并且在没有声明的情 形下，所有排序都按排序码的值递增排列。 排序 插入排序（直插排序、二分排序、希尔排序） 交换排序（冒泡排序、快速排序） 选择排序 （直选排序、树型排序、堆排序） 归并排序（二路归并排序、多路归并排序） 分配排序 （多关键字排序、基数排序）
∴:?9.2插入排序 921直接插入排序 1,直接插入排序的基本思想 直接插入排序( Straight Insertion Sorting)的基本思想是:把 n个待排序的元素看成为一个有序表和一个无序表,开始时 有序表中只包含一个元素,无序表中包含有n-1个元素,排序 入过程中每次从无序表中取出第一个元素,把它的排序码依次 与有序表元素的排序码进行比较,将它插入到有序表中的适 当位置,使之成为新的有序表。 2.直接插入的算法实现
9．2 插入排序 9.2.1直接插入排序 1．直接插入排序的基本思想 直接插入排序（Straight Insertion Sorting）的基本思想是：把 n个待排序的元素看成为一个有序表和一个无序表，开始时 有序表中只包含一个元素，无序表中包含有n-1个元素，排序 过程中每次从无序表中取出第一个元素，把它的排序码依次 与有序表元素的排序码进行比较，将它插入到有序表中的适 当位置，使之成为新的有序表。 2．直接插入的算法实现
void insertsort(ElemType R[l,int n) 待排序元素用个数组R表示,数组有n个元素 for(inti=1;i=0)&&(temp<RiD) R[i+1]-Ri];j-;}∥顺序比较和移动 RL+ll=temp; i
void insertsort(ElemType R[],int n) //待排序元素用一个数组R表示，数组有n个元素 { for ( int i=1; i=0)&& (temp<R[j])) { R[j+1]=R[j]; j--; } // 顺序比较和移动 R[j+1]=temp;} }