林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序十章内部排序Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序10.1概述概述排序排序(sort)(sort): :将一组杂乱无序的数据按一定的将一组杂乱无序的数据按一定的规律规律顺次排列起来叫做排序。顺次排列起来叫做排序。关键字关键字(key)(key): :对一批记录的排序，应该指定是根对一批记录的排序，应该指定是根据记录中某个域的数据进行排列。这个作为排序据记录中某个域的数据进行排列。这个作为排序依据的依据的数据域数据域我们称之为关键字。我们称之为关键字。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序稳定与不稳定：稳定与不稳定：一种排序方法，如果排序后具有一种排序方法，如果排序后具有相同关键字的记录仍相同关键字的记录仍维持排序之前的相对次序维持排序之前的相对次序，则称之为稳定的，否则称为不稳定的。则称之为稳定的，否则称为不稳定的。例：例：初始关键字：初始关键字：4949，3838，6565，9797，7676，1313，2727，4949排序结果：排序结果：1313，2727，3838，4949，4949，6565，7676，97 97 稳定的稳定的1313，2727，3838， 4949 ， 4949，6565，7676，97 97 不稳定不稳定的的基本概念基本概念林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序内部排序：内部排序：大多数的排序方法数据是存储在内存大多数的排序方法数据是存储在内存中，并在内存中加以处理的，这种排序方法叫内中，并在内存中加以处理的，这种排序方法叫内部排序。部排序。外部排序外部排序：如果在排序过程中，数据的主要部分：如果在排序过程中，数据的主要部分存放在外存储器中（如软盘、硬盘、磁带），借存放在外存储器中（如软盘、硬盘、磁带），借助内存进行内、外存数据交换，逐步排列记录之助内存进行内、外存数据交换，逐步排列记录之间的顺序，则称之为外部排序。间的顺序，则称之为外部排序。基本概念基本概念林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序内部排序的大致可分五类：内部排序的大致可分五类： 插入排序插入排序 交换排序交换排序 选择排序选择排序 归并排序归并排序 计数排序计数排序基本概念基本概念林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序/待排记录的静态存储结构待排记录的静态存储结构#define MAXSIZE 20typedef int KeyType; /为了方便表述定义关键字类型为为了方便表述定义关键字类型为inttypedef structKeyType key; /关键字项关键字项InfoType otherinfo; /其他信息其他信息 RedType;typedef structRedType rMAXSIZE +1; /r0作为哨兵作为哨兵int length; SqList;林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序10.2 插入排序插入排序插入排序插入排序(Insertion Sort)(Insertion Sort)的基本思想的基本思想：每次将：每次将一个待排序的记录，按其关键字大小插入到前面一个待排序的记录，按其关键字大小插入到前面已经排好序的文件中的适当位置，直到全部记录已经排好序的文件中的适当位置，直到全部记录插入完成为止。插入完成为止。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序10.2.1直接插入排序直接插入排序直接插入排序直接插入排序(straight insertion sort)(straight insertion sort)思想：思想： 设一记录的序列为设一记录的序列为RnRn；R1,R2,Ri-1R1,R2,Ri-1为为有序区有序区，Ri,RnRi,Rn为无序区为无序区，将，将 Ri Ri插入到有序区；插入到有序区；下一次再将下一次再将Ri+1 Ri+1 插入有序区，直到无序区中所有的记录插入有序区，直到无序区中所有的记录都插到有序区中。都插到有序区中。 开始时，开始时，有序区只有有序区只有R1R1，无序区为，无序区为R2, R2, RnRn，第一次将，第一次将R2R2插入有序区，第二次将插入有序区，第二次将R3R3插入有序插入有序区，经过区，经过n-1n-1次插入后，整个序列即为有序序列。次插入后，整个序列即为有序序列。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序49386597761327494938659776132749493865977613274949386597761327494938659776132749132749493865977613274949386597761327494938659776初始关键字初始关键字j=2 (38)j=3 (65)j=4 (97)j=5 (76)j=6 (13)j=7 (27)j=8 (49)直接插入排序直接插入排序-举例举例林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序算法算法10.1直接插入排序算法直接插入排序算法void InsertSort(SqList &L) / 对顺序表对顺序表L作直接插入排序。作直接插入排序。for (i=2; i=L.length; +i)if (L.ri.key L.ri-1.key) L.r0 = L.ri; / 复制为哨兵复制为哨兵for (j=i-1; L.r0.key L.rj.key; -j)L.rj+1 = L.rj; / 记录后移记录后移L.rj+1 = L.r0; / 插入到正确位置插入到正确位置 / InsertSort林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序空间效率：空间效率：仅用了一个辅助单元（仅用了一个辅助单元（ R0 R0）。）。 时间效率：时间效率：向有序表中逐个插入记录的操作，向有序表中逐个插入记录的操作，进行了进行了n-1n-1趟，每趟操作分为趟，每趟操作分为比较关键字比较关键字和和移动移动记录记录，而比较的次数和移动记录的次数取决于，而比较的次数和移动记录的次数取决于待排序列按关键码的待排序列按关键码的初始排列初始排列。 直接插入排序直接插入排序-效率分析效率分析林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序直接插入排序直接插入排序-效率分析效率分析最好情况下最好情况下：即待排序列：即待排序列已按关键码有序已按关键码有序，每趟操作只需，每趟操作只需1 1次比较。次比较。 总比较次数总比较次数=n-1=n-1次次最坏情况下最坏情况下：即第：即第j j趟操作，插入记录需要同前面的趟操作，插入记录需要同前面的i i个记个记录进行录进行i i次关键码比较，移动记录的次数为次关键码比较，移动记录的次数为i+2i+2次。次。 林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序平平均均情情况况下下：即即第第i i趟趟操操作作，插插入入记记录录大大约约同同前前面面的的i/2i/2个个记记录录进进行行关关键键码码比比较较，移移动动记记录录的的次次数数为为i/2+2i/2+2次。次。直接插入排序直接插入排序-效率分析效率分析由此，直接插入排序的由此，直接插入排序的时间复杂度为时间复杂度为O(nO(n2 2) )。是一个是一个稳定的稳定的排序方法。排序方法。 林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序10.2.210.2.2其他插入排序其他插入排序1.1.折半插入排序折半插入排序 在有序表中确定插入位置，可以不断二分有序在有序表中确定插入位置，可以不断二分有序表来确定插入位置，即一次比较，通过待插入记表来确定插入位置，即一次比较，通过待插入记录与有序表居中的记录按关键码比较，将录与有序表居中的记录按关键码比较，将有序表有序表一分为二一分为二，下次比较在其中一个有序子表中进行，下次比较在其中一个有序子表中进行，将子表又一分为二。这样继续下去，直到要比较将子表又一分为二。这样继续下去，直到要比较的子表中只有一个记录时，比较一次便确定了插的子表中只有一个记录时，比较一次便确定了插入位置。入位置。 林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序void BInsertSort(SqList &L) for (i=2; i=L.length; +i) L.r0 = L.ri; / 将将L.ri暂存到暂存到L.r0low = 1; high = i-1;while (low=high+1; -j) L.rj+1 = L.rj; / 记录后移记录后移L.rhigh+1 = L.r0; / 插入插入 / BInsertSort算法算法10.2 对顺序表对顺序表L作折半插入排序作折半插入排序林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序2.二路插入排序二路插入排序 利用一个大小为利用一个大小为n的辅助空间，以的辅助空间，以r1为基准点，分开两为基准点，分开两路插入排序；参考路插入排序；参考P268图图10.23、表插入排序、表插入排序 表插入排序，就是通过链接指针，按关键码的大小，实表插入排序，就是通过链接指针，按关键码的大小，实现从小到大的链接过程，为此需增设一个指针项。操作方现从小到大的链接过程，为此需增设一个指针项。操作方法与直接插入排序类似，所不同的是直接插入排序要移动法与直接插入排序类似，所不同的是直接插入排序要移动记录，而表插入排序是修改链接指针。记录，而表插入排序是修改链接指针。 林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序/采用静态链表存储结构采用静态链表存储结构#define SIZE 100typedef struct RcdType rc； /记录项记录项 int next； /指针项指针项 SLNode； /*表结点类型表结点类型*/typedef struct SLNode rSIZE； /*静态链表静态链表*/ int length； /*表长度表长度*/SLinkListType； /*静态链表类型静态链表类型*/林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序表插入排序示例表插入排序示例 林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序表插入排序得到一个有序的链表，查找则只能进行顺序表插入排序得到一个有序的链表，查找则只能进行顺序查找，而不能进行随机查找，如折半查找。为此，还需查找，而不能进行随机查找，如折半查找。为此，还需要对记录进行重排。要对记录进行重排。 重排记录方法：按链表顺序扫描各结点，将第重排记录方法：按链表顺序扫描各结点，将第i i个结点个结点中的数据元素调整到数组的第中的数据元素调整到数组的第i i个分量数据域。因为第个分量数据域。因为第i i个结点可能是数组的第个结点可能是数组的第j j个分量，数据元素调整仅需将两个分量，数据元素调整仅需将两个数组分量中数据元素交换即可，但为了能对所有数据个数组分量中数据元素交换即可，但为了能对所有数据元素进行正常调整，指针域也需处理。元素进行正常调整，指针域也需处理。 林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序对表插入排序结果进行重排示例对表插入排序结果进行重排示例 林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序void Arrange(SLinkList &SL) p = SL.r0.next; / p指示第一个记录的当前位置指示第一个记录的当前位置 for (i=1; iSL.length; +i) / 第第i个记录在个记录在SL中的当前位置应不小于中的当前位置应不小于i while (ptti+1i+1，t tk k=1=1；2 2、 按步长序列个数按步长序列个数k k，对序列进行，对序列进行k k趟排序；趟排序；3 3、每每趟趟排排序序，根根据据对对应应的的步步长长t ti i，将将待待排排序序列列分分割割成成若若干干长长度度为为m m的的子子序序列列，分分别别对对各各子子表表进进行行直直接接插插入入排排序序。仅仅步步长长因因子子为为1 1时时，整整个个序序列列作作为为一一个个表表来来处处理理，表表长长度度即即为为整整个序列的长度。个序列的长度。希尔排序希尔排序-算法描述算法描述林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序希尔排序希尔排序-举例举例493865977613274949133827455654997557644938659776132749455387613556527449974949386597761327494554938659776132749455初始关键字初始关键字一趟排序结果一趟排序结果二趟排序结果二趟排序结果三趟排序结果三趟排序结果林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序 void ShellInsert(SqList &L, int dk) for (i=dk+1; i0 & LT(L.r0.key, L.rj.key); j-=dk) L.rj+dk = L.rj; / 记录后移，查找插入位置记录后移，查找插入位置 L.rj+dk = L.r0; / 插入插入 / ShellInsert算法算法10.4 对顺序表对顺序表L作一趟希尔插入排序作一趟希尔插入排序林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序 void ShellSort(SqList &L, int dlta, int t) for (int k=0; kt; +k) ShellInsert(L, dltak); / 一趟增量为一趟增量为dltak的插入排序的插入排序 / ShellSort算法算法10.5 按增量序列按增量序列dlta0.t-1对顺序表对顺序表L作希尔排序。作希尔排序。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序时效分析时效分析：希希尔尔排排序序时时效效分分析析很很难难，关关键键字字的的比比较较次次数数与与记记录录移移动次数依赖于步长因子序列的选取。动次数依赖于步长因子序列的选取。特定情况下可以准确估算出关键码的比较次数和记录特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的步长因子序列的移动次数。目前还没有人给出选取最好的步长因子序列的方法。步长因子序列可以有各种取法。但需要注意，的方法。步长因子序列可以有各种取法。但需要注意，最最后一个步长因子必须为后一个步长因子必须为1 1。希尔排序方法是一个希尔排序方法是一个不稳定的排序方法不稳定的排序方法。 希尔排序希尔排序-时效分析时效分析林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序10.3 10.3 快速排序快速排序 交换排序主要是通过两两比较待排记录的关键码，若交换排序主要是通过两两比较待排记录的关键码，若发生与发生与排序要求相逆排序要求相逆，则交换之。，则交换之。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序10.3.110.3.1起泡排序起泡排序起泡排序起泡排序(bubble sort)(bubble sort)：首先将第：首先将第n n个记录的关键个记录的关键字和第字和第n-1n-1个记录的关键字进行比较，若为逆序，个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第则将两个记录交换之，然后比较第n-1n-1个记录和第个记录和第n-2n-2个记录的关键字。依此类推，直到第个记录的关键字。依此类推，直到第2 2个记录和个记录和第第1 1个记录的关键字进行比较为止。上述过程称第个记录的关键字进行比较为止。上述过程称第一趟起泡排序。一趟起泡排序。 林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序4938659776132749初始关键字13 49386597762749第一趟排序后13 27 493865977649第二趟排序后13 27 38 4949659776第三趟排序后13 27 38 49496576 97第四趟排序后13 27 38 4949657697第五趟排序后13 27 38 4949657697第六趟排序后起泡排序起泡排序-举例举例13 27 38 4949657697第七趟排序后林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序起泡排序起泡排序-效率分析效率分析 空间效率：空间效率：仅用了一个辅助单元。仅用了一个辅助单元。 时间效率：时间效率：最好情况下：最好情况下：仅需要一次扫描，即仅需要一次扫描，即n-1n-1次比较次比较待排序列已有序，不需移动。待排序列已有序，不需移动。 最坏情况下：最坏情况下：总共要进行总共要进行n-1n-1趟冒泡，对趟冒泡，对i i个记录的表进行一个记录的表进行一趟冒泡需要趟冒泡需要i-1i-1次关键码比较次关键码比较 每次比较后均需要进行三次移动。每次比较后均需要进行三次移动。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序快速排序（快速排序（quick sortquick sort）是对起泡排序的一种改是对起泡排序的一种改进。进。基本思想基本思想: : 通过通过一趟排序一趟排序将待排记录分割将待排记录分割成独立的成独立的两部分两部分，其中一部分记录的关键字均比，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分另一部分记录的关键字小，然后分别对这两部分记录继续进行排序，直到整个序列有序。记录继续进行排序，直到整个序列有序。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序快速排序快速排序-描述描述设待排序的记录为：设待排序的记录为：R1R h : R1R h : 一趟快速排序的具体做法是：一趟快速排序的具体做法是：附设两个指针附设两个指针i i和和j j，它，它们的初值分别为们的初值分别为 i=1 i=1和和 j=h j=h，设基准记录，设基准记录temp=R1,temp=R1,首先从首先从 j j 所指位置向前搜索找到第一个关键字小于所指位置向前搜索找到第一个关键字小于temp.keytemp.key的记录的记录r j r j ，将，将r j r j 移至移至i i所指的位置，所指的位置，i+,i+,然后从然后从i i所指位置向后搜索，找到第一个关键字大于所指位置向后搜索，找到第一个关键字大于temp.keytemp.key的记录的记录r i ,r i ,将将r i r i 移至移至j j所指的位置。所指的位置。重复这两步直到重复这两步直到i=ji=j为止为止; i ; i 便是基准便是基准temptemp的最终位的最终位置。置。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序快速排序快速排序- -举例举例4938659776132749初始关键字初始关键字j向左扫描向左扫描第一次交换后第一次交换后i向右扫描向右扫描第二次交换后第二次交换后j向左扫描，位置不向左扫描，位置不变，第三次交换后变，第三次交换后i向右扫描向右扫描,位置不变，位置不变，第四次交换后第四次交换后,j向左扫描向左扫描4938659776132749ijji27386597761349ji27386597761349ij27386597761349ij273865977649ij2738659776491313ij27386597764913i j49一次划分过程一次划分过程林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序97382713764965492738659776491349132765977649384913276597764938491327659776493849初始关键字：初始关键字：一趟排序之一趟排序之后：后：二趟排序之二趟排序之后：后：三趟排序之三趟排序之后：后：最后的排序结果：最后的排序结果：各趟排序之后的状态各趟排序之后的状态快速排序快速排序- -举例（续）举例（续）林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序算法算法10.6(b)快速排序快速排序-算法（一趟排序）算法（一趟排序）int Partition(SqList &L, int low, int high) KeyType pivotkey; L.r0 = L.rlow; / 用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录 pivotkey = L.rlow.key; / 枢轴记录关键字枢轴记录关键字 while (lowhigh) / 从表的两端交替地向中间扫描从表的两端交替地向中间扫描 while (low=pivotkey) -high; L.rlow = L.rhigh; / 将比枢轴记录小的记录移到低端将比枢轴记录小的记录移到低端 while (lowhigh & L.rlow.key=pivotkey) +low; L.rhigh = L.rlow; / 将比枢轴记录大的记录移到高端将比枢轴记录大的记录移到高端 L.rlow = L.r0; / 枢轴记录到位枢轴记录到位 return low; / 返回枢轴位置返回枢轴位置 / Partition林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序 void QSort(SqList &L, int low, int high) int pivotloc; if (low high) / 长度大于长度大于1 pivotloc = Partition(L, low, high); QSort(L, low, pivotloc-1); QSort(L, pivotloc+1, high); / 对高子表递归排序对高子表递归排序 / QSort算法算法10.7快速排序快速排序-算法（递归调用）算法（递归调用）林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序快快速速排排序序的的递递归归过过程程可可用用生生成成一一棵棵二二叉叉树树形象地给出，下图对应递归调用过程的二叉树。形象地给出，下图对应递归调用过程的二叉树。272776761313383897974949494965林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序快速排序快速排序-效率分析效率分析 空间效率：空间效率：快速排序是递归的，每层递归调用时的快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层次数与上指针和参数均要用栈来存放，递归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况述二叉树的深度一致。因而，存储开销在理想情况下为下为O(logO(log2 2n)n)，即树的高度；在最坏情况下，即二，即树的高度；在最坏情况下，即二叉树是一个单链，为叉树是一个单链，为O(n)O(n)。 林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序快速排序快速排序-效率分析效率分析 时时间间效效率率：在在n n个个记记录录的的待待排排序序列列中中，一一次次划划分分需需要要约约n n次次关关键键码码比比较较, ,时时效效为为O(n)O(n)，若若设设c(n)c(n)为为对对n n个个记记录录的的待待排排序序列列进进行快速排序所需时间。行快速排序所需时间。理想情况下理想情况下: :每次划分，正好将分成两个等长的子序列，则每次划分，正好将分成两个等长的子序列，则 c(n)n+2c(n/2) c(n)n+2c(n/2) n+2(n/2+2c(n/4)=2n+4c(n/4)n+2(n/2+2c(n/4)=2n+4c(n/4) 2n+4(n/4+c(n/8)=3n+8c(n/8) 2n+4(n/4+c(n/8)=3n+8c(n/8) kn+2kC(n/2k) =nlog =nlog2 2n+nc(1)=n+nc(1)=O(nlogO(nlog2 2n)n) c(1) c(1)是一个常数是一个常数最坏情况下：即每次划分，只得到一个子序列，时效为最坏情况下：即每次划分，只得到一个子序列，时效为O(nO(n2 2) )。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序快速排序是通常被认为在同数量级快速排序是通常被认为在同数量级（O(nlogO(nlog2 2n)n)）的排序方法中平均性能最好的。的排序方法中平均性能最好的。 快速排序是快速排序是不稳定不稳定的，对于有相同关键字的，对于有相同关键字的记录，排序以后次序可能会颠倒。的记录，排序以后次序可能会颠倒。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序10.4 10.4 选择排序选择排序基本思想基本思想：选择排序主要是每一趟从待排序：选择排序主要是每一趟从待排序列列n-i+1(i=1,2.n-1)n-i+1(i=1,2.n-1)个记录中选取关键字最小的个记录中选取关键字最小的记录作为有序序列中第记录作为有序序列中第i i个记录；第一趟从个记录；第一趟从n n个记录个记录中选取关键码最小的记录，第二趟从剩下的中选取关键码最小的记录，第二趟从剩下的n-1n-1个个记录中选取关键码最小的记录，直到整个序列的记记录中选取关键码最小的记录，直到整个序列的记录选完。录选完。 包括：包括：简单选择排序、树型选择排序、堆排序简单选择排序、树型选择排序、堆排序。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序10.4.1 10.4.1 简单选择排序简单选择排序思想思想： 第一趟，在第一趟，在r1,r2,rnr1,r2,rn中，选择关键字最小中，选择关键字最小的的rkrk，并与，并与r1r1交换。交换。 第二趟，在第二趟，在r2,r3,rnr2,r3,rn中，选择关键字最小的中，选择关键字最小的rkrk，并与，并与r2r2交换。交换。 第三趟，在第三趟，在r3,r4,rnr3,r4,rn中，选择关键字最小的中，选择关键字最小的rkrk，并与，并与r3r3交换。交换。 共进行共进行n-1n-1趟。趟。 n-1 n-1趟后，趟后，关键字的比较次数：关键字的比较次数：n(n-1)/2n(n-1)/2林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序493865977613274913386597764927491327659776493849132738977649654913273849769765491327384976976549132738497697654913273849769765491327384976976549初始关键字：初始关键字：第一趟排序之后：第一趟排序之后：第二趟排序之后：第二趟排序之后：第三趟排序之后：第三趟排序之后：第四趟排序之后：第四趟排序之后：第五趟排序之后：第五趟排序之后：第六趟排序之后：第六趟排序之后：第七趟排序之后：第七趟排序之后：最后排序结果：最后排序结果：直接选择排序直接选择排序-举例举例林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序 void SelectSort(SqList &L) for (i=1; iL.length; +i) / 在在L.ri.L.length中选择中选择key最小的记录最小的记录j = SelectMinKey(L, i); if (i!=j) / L.riL.rj; 与第与第i个记录交换个记录交换temp=L.ri;L.ri=L.rj;L.rj=temp; / SelectSort10.910.9直接选择排序直接选择排序-算法算法林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序从程序中可看出，简单选择排序移动记录从程序中可看出，简单选择排序移动记录的次数较少，但关键码的比较次数依然是的次数较少，但关键码的比较次数依然是 n(n- n(n-1)/2,1)/2,所以时间复杂度仍然是所以时间复杂度仍然是O(nO(n2 2).).直接选择排序是直接选择排序是不稳定的不稳定的。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序10.4.2树形选择排序树形选择排序 树型选择排序树型选择排序(Tree Selection Sort),又称锦标赛又称锦标赛(Tournament Sort),是一种按照锦标赛的思想进行排序的方是一种按照锦标赛的思想进行排序的方法。法。首先对首先对n个记录的关键字进行两两比较，然后在其中个记录的关键字进行两两比较，然后在其中 个较小者之间再进行两两比较，如此重复，直到选出最个较小者之间再进行两两比较，如此重复，直到选出最小的关键字的记录为止。小的关键字的记录为止。其次，在选出次小的关键字记录，可以借助首次比较其次，在选出次小的关键字记录，可以借助首次比较的部分结果。的部分结果。参考参考P279 图图10.9时间复杂度为时间复杂度为O(nlong 2n)林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序10.4.310.4.3堆排序堆排序堆堆：n n个元素的序列个元素的序列 k k1 1,k,k2 2,.,k,.,kn n 当且仅当满足当且仅当满足下列关系时，称为堆。下列关系时，称为堆。 或或 若将此序列对应的一维数组看成是一个完全二若将此序列对应的一维数组看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端叉树，则堆的含义表明，完全二叉树中所有非终端结点的值结点的值均不大于（或不小于）均不大于（或不小于）其左右孩子结点的其左右孩子结点的值。值。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序96963838272783830909111191915353303047478585242436361212序列：序列：96,83,27,38,11,09 96,83,27,38,11,09 序列：序列：12,36,24,85,47,30,53,9112,36,24,85,47,30,53,91 对应的完全二叉树对应的完全二叉树 对应的完全二叉树对应的完全二叉树 （大根堆）（大根堆） （小根堆）（小根堆）96968383272738381111090912123636242485854747303053539191堆排序堆排序-基本概念基本概念林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序堆排序：堆排序：在大根堆中，将堆顶和最后一个记录交换，即得第在大根堆中，将堆顶和最后一个记录交换，即得第一趟的结果；再使剩余一趟的结果；再使剩余n-1n-1个元素的序列重又建成一个堆，个元素的序列重又建成一个堆，则得到则得到n n个元素的次大值。如此反复执行，便能得到一个有个元素的次大值。如此反复执行，便能得到一个有序序列，这个过程称为堆排序。序序列，这个过程称为堆排序。堆排序堆排序-基本概念基本概念林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序实现堆排序需要解决两个问题：实现堆排序需要解决两个问题： 1 1）如何由一个无序序列）如何由一个无序序列建成一个堆建成一个堆？ 2 2）如何在一趟排序之后，调整剩余元素）如何在一趟排序之后，调整剩余元素成为一个新的堆？成为一个新的堆？ 堆排序堆排序-基本概念基本概念林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序先解决：先解决：2）如何在一趟排序之后，调整剩余元素成为一个新的堆？）如何在一趟排序之后，调整剩余元素成为一个新的堆？思路：首先在堆顶元素与最后一个元素交换之后，树的新的思路：首先在堆顶元素与最后一个元素交换之后，树的新的根结点不满足堆的要求，此时用该根结点与其左右子树的根根结点不满足堆的要求，此时用该根结点与其左右子树的根结点比较，选满足要求的结点交换；结点比较，选满足要求的结点交换；其次被交换的子树不满足堆的要求，继续向下传递，其次被交换的子树不满足堆的要求，继续向下传递，直到叶子结点；直到叶子结点；称自堆顶到叶子结点的调整过程为称自堆顶到叶子结点的调整过程为筛选。筛选。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序typedef SqList Heaptype;void HeapAdjust(HeapType &H, int s, int m) / 已知已知H.rs.m中记录的关键字除中记录的关键字除H.rs.key之外均满足堆的之外均满足堆的定义，本函数调整定义，本函数调整H.rs的关键字，使的关键字，使H.rs.m成为一个大顶堆成为一个大顶堆 RedType rc; rc = H.rs; for (j=2*s; j=m; j*=2) / 沿沿key较大的孩子结点向下筛选较大的孩子结点向下筛选 if (jm & H.rj.key H.rj.key) break; H.rs = H.rj; s = j; H.rs = rc; / rc应插入在位置应插入在位置s上上 / HeapAdjust算法算法10.10筛选算法筛选算法林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序 1 1）如何由一个无序序列）如何由一个无序序列建成一个堆建成一个堆？把单个结点看成堆；把单个结点看成堆；把叶子结点看成堆。把叶子结点看成堆。算法的理论基础算法的理论基础91915353303047478585242436361212121236362424858547473030535391910 1 2 3 4 5 6 7 80 1 2 3 4 5 6 7 8为叶子结点为叶子结点林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序从一个无序序列建堆的过程就是一个反复从一个无序序列建堆的过程就是一个反复“筛选筛选”的过程。若的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是将此序列看成是一个完全二叉树，则最后一个非终端结点是 个元素，由此个元素，由此“筛选筛选”只需从第只需从第 个元素开始。个元素开始。for(i=H.length/2;i=1;i- -) HeapAdjust(H,i,H.length);for(i=H.length/2;i=1;i- -) HeapAdjust(H,i,H.length);建堆的基本思路建堆的基本思路121236362424858547473030535391910 1 2 3 4 5 6 7 80 1 2 3 4 5 6 7 8为叶子结点为叶子结点林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序void HeapSort(HeapType &H) RedType temp;for (i=H.length/2; i0; -i) / 把把H.r1.H.length建成大顶堆建成大顶堆HeapAdjust ( H, i, H.length );for (i=H.length; i1; -i) / 将堆顶记录和当前未经排序子序列将堆顶记录和当前未经排序子序列Hr1.i中中temp=H.ri; H.ri=H.r1; H.r1=temp; / 最后一个记录相互交换最后一个记录相互交换HeapAdjust(H, 1, i-1); / 将将H.r1.i-1 重新调整为大顶重新调整为大顶堆堆 / HeapSort算法算法10.11 堆排序算法堆排序算法林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序堆排序堆排序-效率分析效率分析 设树的高为设树的高为k, k, 则则 。 从根到从根到叶的筛选，关键字的比较次数至多叶的筛选，关键字的比较次数至多2(k-1)2(k-1)次次 ；交换记录至；交换记录至多多 k k 次。所以，在建好堆后，排序过程中的筛选次数不超次。所以，在建好堆后，排序过程中的筛选次数不超过下式：过下式： ( ( loglog2 2(n(n 1)1) + + loglog2 2(n(n 2)2) + + log + + log2 22 2 ) ) nlognlog2 2n n而建堆时的比较次数不超过而建堆时的比较次数不超过4n4n次次( P282( P282注解注解 ) )，因此堆排序，因此堆排序最坏情况下，时间复杂度也为最坏情况下，时间复杂度也为O(nlogO(nlog2 2n)n)。 林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序归并：归并：是指将若干个已排序好的有序表合并成一个是指将若干个已排序好的有序表合并成一个有序表。有序表。二路归并：二路归并：两个有序表的归并称为二路归并。两个有序表的归并称为二路归并。10.5 10.5 归并排序归并排序林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序归并排序：归并排序：就是利用归并过程；就是利用归并过程；（1 1）开始时先将）开始时先将n n个数据看成个数据看成n n个长度为个长度为1 1的已排好序的的已排好序的表；表；（2 2）将相邻的表成对合并，得到长度为）将相邻的表成对合并，得到长度为2 2的的 个有序个有序表，每个表含有表，每个表含有2 2个或个或 1 1个个 数据；数据；（3 3）进一步再将相邻表成对合并，得到长度为）进一步再将相邻表成对合并，得到长度为4 4的的 个有序表；个有序表；如此重复做下去，直至所有数据均合并到一个长度为如此重复做下去，直至所有数据均合并到一个长度为n n的有序表为止，就完成了排序。的有序表为止，就完成了排序。归并排序归并排序-基本思路基本思路林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序归并排序归并排序-举例举例林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序void Merge (RedType SR, RedType TR, int i, int m, int n) for (j=m+1, k=i; i=m & j=n; +k) / 将将SR中记录由小到大地并入中记录由小到大地并入TR if LQ(SRi.key,SRj.key) TRk = SRi+; else TRk = SRj+; if (i=m) / TRk.n = SRi.m; 将剩余的将剩余的SRi.m复制到复制到TR while (k=n & i=m) TRk+=SRi+; if (j=n) / 将剩余的将剩余的SRj.n复制到复制到TR while (k=n &j =n) TRk+=SRj+; / Merge算法算法10.12将有序的将有序的SRi.m和和SRm+1.n归并为有序的归并为有序的TRi.n林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序void MSort(RedType SR , RedType TR1 , int s, int t) RedType TR220; if ( s = = t ) TR1t = SRs; else m=(s+t)/2; / 将将SRs.t平分为平分为SRs.m和和SRm+1.t MSort(SR,TR2,s,m); / 递归地将递归地将SRs.m归并为有序的归并为有序的TR2s.m MSort(SR,TR2,m+1,t); / 将将SRm+1.t归并为有序的归并为有序的TR2m+1.t Merge(TR2, TR1, s , m ,t ); / 将将TR2s.m和和TR2m+1.t归并到归并到TR1s.t / MSort 算法算法10.13 将将SRs.t归并排序为归并排序为TR1s.t林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序void MergeSort(SqList &L) MSort(L.r, L.r, 1, L.length); / MergeSort算法算法10.14 对顺序表对顺序表L作归并排序作归并排序林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序mergepass(r,r1,length) mergepass(r,r1,length) /*/*对对R做一趟归并，结果放在做一趟归并，结果放在R1中中*/ rectype r ,r1 ; rectype r ,r1 ; int length; int length; int i, j; int i, j; i=0; i=0; while (i+2*length-1n) while (i+2*length-1n) merge(r,r1,i,i+length-1,i+2*length-1); merge(r,r1,i,i+length-1,i+2*length-1); i=i+2*length; i=i+2*length; /*/*剩余部分的起点剩余部分的起点*/*/ if (i+length-1 if (i+length-1n-1n-1) ) /*/*其中后部长度小于其中后部长度小于length*/length*/ merge(r,r1,i,i+length-1,n-1); merge(r,r1,i,i+length-1,n-1); else else /*/*只有一个长度小于只有一个长度小于lengthlength的部分的部分*/*/ for(j=i;jn;j+) r1j=rj; for(j=i;jn;j+) r1j=rj; 一趟归并的非递归算法（存储结构没改）一趟归并的非递归算法（存储结构没改）林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序Mergesort(r，r1) rectype r,r1 int length; length=1; while (lengthn) mergepass(r,r1,length); length=2*length; mergepass(r1,r,length); length=2*length; 二路归并二路归并-算法算法林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序第第i i趟归并后，有序子文件长度为趟归并后，有序子文件长度为2 2i i, ,因此，对有因此，对有n n个个记录的文件排序，必须做记录的文件排序，必须做 趟归并，每趟归并，每趟归并所花的时间是趟归并所花的时间是O(n);O(n);二路归并排序的时间复杂性为二路归并排序的时间复杂性为O(nlogO(nlog2 2n n ) )。归并排序是稳定的归并排序是稳定的。归并排序分析归并排序分析林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序10.6基数排序基数排序基数排序：是一种借助于多关键码排序的思想，是将单关键基数排序：是一种借助于多关键码排序的思想，是将单关键码按基数分成码按基数分成“多关键码多关键码”进行排序的方法。进行排序的方法。 林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序10.6.1 多关键字排序多关键字排序多关键码排序按照从多关键码排序按照从最主位关键码最主位关键码到到最次位关键码最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：或从最次位到最主位关键码的顺序逐次排序，分两种方法：最高位优先最高位优先(Most Significant Digit first)法，简称法，简称MSD法法：先按：先按k0排序分组，同一组中记录，关键码排序分组，同一组中记录，关键码k0相等，相等，再对各组按再对各组按k1排序分成子组，之后，对后面的关键码继续排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码这样的排序分组，直到按最次位关键码kd-1对各子组排序对各子组排序后。再将各组连接起来，便得到一个有序序列。扑克牌按后。再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是花色、面值排序中介绍的方法一即是MSD法。法。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序最低位优先最低位优先(Least Significant Digit first)法，简称法，简称LSD法法：先从：先从kd-1开始排序，再对开始排序，再对kd-2进行排序，依次重复，进行排序，依次重复，直到对直到对k0排序后便得到一个有序序列。扑克牌按花色、排序后便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法二即是面值排序中介绍的方法二即是LSD法。法。林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序10.6.2链式基数排序链式基数排序将关键码拆分为若干项，每项作为一个“关键码”，则对单关键码的排序可按多关键码排序方法进行。基数排序：从最低位关键码起，按关键码的不同值将序列中的记录“分配”到RADIX个队列中，然后再“收集”之。如此重复d次即可。链式基数排序是用RADIX个链队列作为分配队列，关键码相同的记录存入同一个链队列中，收集则是将各链队列按关键码大小顺序链接起来。 林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序#define MAX_KEY_OF_NUM 8 /*关键码项数最大值关键码项数最大值*/#define RADIX10/*关键码基数关键码基数 */#define MAX_SPACE 10000/*分配的最大可利用存储空间分配的最大可利用存储空间*/typedef structKeyTypekeysMAX_KEY_OF_NUM；/*关键码字段关键码字段*/InfoTypeotheritems；/*其它字段其它字段*/intnext；/*指针字段指针字段*/SLCell；/*表结点类型表结点类型*/typedef structSLCell rMAX_SPACE； /*静态链表，静态链表，r0为头结点为头结点*/intkeynum；/*关键码个数关键码个数*/intrecnum；/*当前表中记录数当前表中记录数*/SLList；/*静态链表类型静态链表类型*/typedef intArrayTyperadix；/*数组指针，分别指向各队列数组指针，分别指向各队列*/林焕祥林焕祥林焕祥林焕祥D a t a S t r u c t u r e第十章第十章 排序排序参考 P286算法10.15算法10.16算法10.17