1、11 什么是算法？如何评判算法的好坏？什么是算法？如何评判算法的好坏？2 时间复杂度和空间复杂度如何表示？时间复杂度和空间复杂度如何表示？3 计算举例计算举例讨论：讨论：第四章第四章:排序和算法分析排序和算法分析2常用常用时间复杂度时间复杂度来衡量来衡量算法的基本特性：算法的基本特性：算法评价指标：算法评价指标：有穷性、确定性、可行性、必有输出有穷性、确定性、可行性、必有输出正确性、可读性、健壮性、高效率与低存储量需求正确性、可读性、健壮性、高效率与低存储量需求(见课本见课本P20)?常用常用空间复杂度空间复杂度来衡量来衡量好的程序设计：好算法好结构好的程序设计：好算法好结构算法：算法：是对特
2、定问题求解步骤的一种描述，它是指令是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。的有限序列，是一系列输入转换为输出的计算步骤。33n+2=O(n)因为因为 3n+2 4n for n 26*2n+n2=O(2n)因为因为6*2n+n2 7*2n for n 4例：例：渐进符号渐进符号（O）的定义：）的定义：当且仅当存在一个正的常当且仅当存在一个正的常数数 C C，使得对所有的，使得对所有的 n n n n0 0 ，有，有 f(n)f(n)Cg(n)Cg(n)，则：则：f(n)=f(n)=O(g(n)(g(n)?4该算法的运行时间由程序中所有语句的该算法的
3、运行时间由程序中所有语句的频度频度（即该语（即该语句重复执行的次数）句重复执行的次数）之和之和构成。构成。解：解：分析：分析：显然，语句的频度是显然，语句的频度是1。设语句。设语句2的频度是的频度是f(n)，则有：，则有：算法的时间复杂度由嵌套最深层语句的频度决定算法的时间复杂度由嵌套最深层语句的频度决定例：例：分析以下程序段的时间复杂度。分析以下程序段的时间复杂度。i=1;?while(i=n)?i=i*2;?即即f(n)log2n，取最大值取最大值f(n)=log2n所以该程序段的时间复杂度所以该程序段的时间复杂度T(n)=1+f(n)=1+?log2n=?O(?log2n)?()2f n
4、n5频度频度:?语句重复执行的次数称为该语句的频度，记语句重复执行的次数称为该语句的频度，记f(n)。设算法的问题规模为设算法的问题规模为n；时间复杂度时间复杂度:?算法执行时间度量算法执行时间度量,记记T(n)=O(?maxlevel(f(n)?)。对算法各基本操作的频度求和，便可得算法的时间复杂度。对算法各基本操作的频度求和，便可得算法的时间复杂度。但实际中我们所关心的主要是一个算法所花时间的数量但实际中我们所关心的主要是一个算法所花时间的数量级，即取算法各基本操作的最大频度数量级。级，即取算法各基本操作的最大频度数量级。f(n)?=?1?+?n?+?n2?+?n3T(n)?=?O(?n3
5、?)?6例，例，for?(?j?=?1 1?；j=n?；j+?)?X?=?X?+?1 1；X?=?X?+?1 1；for?(?i?=?1 1?；i=n?；i+?)?for?(?i?=?1 1?；i=n?；i+?)?X?=?X?+?1 1；X?=?X?+?1 1；算法执行总的时间花费为算法执行总的时间花费为1+n+2n2算法的时间复杂度为算法的时间复杂度为?T(n)?=?O(n2)?O(1)?，O(logn)?，O(nk)?，O(2n)?7有时，算法中基本操作重复执行的次数随问题的输入有时，算法中基本操作重复执行的次数随问题的输入不同而不同，通常分析不同而不同，通常分析最坏最坏情况下的时间复杂度
6、。情况下的时间复杂度。例，例，顺序查找算法顺序查找算法Status?serch?(?int?a?，int?n?，int?e?)?for?(?i?=?0?；i?=n?-?1 1?；+i?)?if?(?e?=?ai?)?return?TRUE?；最好最好?1?次比较，最坏次比较，最坏?n 次比较，平均次比较，平均?(n+1)/2?次比较。次比较。return?FALSE?；8注：注：1）?O（）为渐近符号。（）为渐近符号。2）?空间复杂度空间复杂度S(n)按数量级递增顺序也与上表类似。按数量级递增顺序也与上表类似。复杂度高复杂度高复杂度低复杂度低时间复杂度时间复杂度T(n)按数量级递增顺序为：按数
7、量级递增顺序为：多项式阶多项式阶9 排序介绍排序介绍 排序（排序（SortingSorting）是数据处理中一种）是数据处理中一种很重要的运算，同时也是很常用的运很重要的运算，同时也是很常用的运算，一般数据处理工作算，一般数据处理工作25%25%的时间都的时间都在进行排序。简单地说，排序就是把在进行排序。简单地说，排序就是把一组记录（元素）按照某个域的值的一组记录（元素）按照某个域的值的递增（即由小到大）或递减（即由大递增（即由小到大）或递减（即由大到小）的次序重新排列的过程。到小）的次序重新排列的过程。10 排序排序-将一个包含若干数据元素将一个包含若干数据元素（或记录）的任意序列，重新排列
8、成（或记录）的任意序列，重新排列成一个一个按关键字有序按关键字有序的序列的过程。的序列的过程。按待排序按待排序记录所在的位置记录所在的位置，可分为：，可分为：内部排序内部排序：待排序记录存放在内存。：待排序记录存放在内存。外部排序外部排序：当待排序记录数量很大时，：当待排序记录数量很大时，一部分记录需放在外存，在排序过程一部分记录需放在外存，在排序过程中就需要对外存进行访问。中就需要对外存进行访问。11内部排序分为：内部排序分为：插入排序插入排序 快速排序快速排序 选择排序选择排序 归并排序归并排序 基数排序基数排序(略过略过)?排序基本操作排序基本操作比较两个关键字大小比较两个关键字大小将记
9、录从一个位置移动到另一个位置将记录从一个位置移动到另一个位置12待排序记录在内存中怎样存储和处理？待排序记录在内存中怎样存储和处理？顺序顺序排序排序排序时直接移动记录；排序时直接移动记录；链表链表排序排序排序时只移动指针；排序时只移动指针；地址地址排序排序排序时先移动地址，最后再移动记录。排序时先移动地址，最后再移动记录。注：注：地址排序地址排序中可以增设一维数组来专门存放记录的地址。中可以增设一维数组来专门存放记录的地址。按排序算法的时间复杂度不同，可分为按排序算法的时间复杂度不同，可分为3类：类：简单的排序算法：时间效率低，简单的排序算法：时间效率低，O(n2)?先进的排序算法先进的排序算
10、法:?时间效率高，时间效率高，O(?nlog2n?)?基基?数数?排排?序序?算法：时间效率高，算法：时间效率高，O(?dn)?d关键字的位数关键字的位数(长度长度)?13 直接插入排序直接插入排序 希尔排序希尔排序14 基本操作是：基本操作是：将一个记录插入到已将一个记录插入到已排好序的有序表中，从而得到一个排好序的有序表中，从而得到一个新的、记录数增新的、记录数增1 1的有序表。的有序表。基本思想是：基本思想是：当插入第当插入第 i i(i i2)2)个个记录时，前面的记录时，前面的 r r 1,1,r r 2,2,r r i i-1-1已经排好序。这时已经排好序。这时,将将 r r i
11、i 的关键字依次与的关键字依次与r r i i-1,-1,r r i i-22的关键字进行比较的关键字进行比较，并同时将，并同时将相关记录位置后移，直到找到插入相关记录位置后移，直到找到插入 r r i i 的合适位置。的合适位置。15 有一组记录的关键字初始排列如下：有一组记录的关键字初始排列如下：49?38?65?97?76?13?27?49 请使用直接插入排序方法，将以上请使用直接插入排序方法，将以上记录按照记录按照关键字非递减关键字非递减排列。排列。16(49)?38?65?97?76?13?27?49初始关键字初始关键字：i=2:?(38)?(38?49)?65?97?76?13?2
12、7?49i=3:?(65)?(38?49?65)?97?76?13?27?49i=4:?(97)?(38?49?65?97)?76?13?27?49i=5:?(76)?(38?49?65?76?97)?13?27?49i=6:?(13)?(13?38?49?65?76?97)?27?49i=7:?(27)?(13?27?38?49?65?76?97)?49i=8:?(49)?(13?27?38?49?49?65?76?97)?结果结果17void InsertSort(DataType a,int n)/*用直接插入法对a0-an-1排序*/int i,j;DataType temp;for(
13、i=0;i -1&temp.key aj.key)aj+1=aj;j-;aj+1=temp;18void?main(void)?DataType?test6=64,5,7,89,6,24;?int?i,?n?=?6;?SeqList?myList;?ListInitiate(&myList);?for(i?=?0;?i?n;?i+)?ListInsert(&myList,?i,?testi);?InsertSort(myList.list,?myList.size);?for(i=0;?in;?i+)?printf(%d?,?myList.listi.key);#include#include
14、 typedef int KeyType;typedef int KeyType;typedef structtypedef structKeyType key;KeyType key;DataType;DataType;#define MaxSize 100#define MaxSize 100#include SeqList.h#include SeqList.h链表实现算法链表实现算法19 算法简便，容易实现。算法简便，容易实现。当待排序记录数当待排序记录数 n n 很小时，是一种很小时，是一种很好的排序方法。很好的排序方法。当待排序记录数当待排序记录数 n n 很大时，不宜使很大时，不
15、宜使用。用。时间复杂度为时间复杂度为O O(n n2 2)。空间复杂度为空间复杂度为S S(n n)=O=O(1)(1)，即使用一，即使用一个辅助单元（第个辅助单元（第0 0个单元）。个单元）。20基本思想：基本思想：1 1）先取一个正整数先取一个正整数d1d1（d1d1记录数记录数n n），把所有相隔），把所有相隔d1d1的记录放一组，的记录放一组，这样就把整个待排记录序列分割成若这样就把整个待排记录序列分割成若干个子序列，对每个子序列进行直接干个子序列，对每个子序列进行直接插入排序。插入排序。2 2）再取再取 d2 d1 d2 d1，把所有相隔，把所有相隔 d2 d2 的记录放一组，对每一
16、组内的记录进的记录放一组，对每一组内的记录进行直接插入排序。行直接插入排序。3 3）最后取最后取 di di1 1，即把所有记录放，即把所有记录放在一组进行直接插入排序。在一组进行直接插入排序。21对下列关键字进行希尔排序：对下列关键字进行希尔排序：49?38?65?97?76?13?27?48?55?4取取 d15，d23，d31。22 初始关键字初始关键字：49?38?65?97?76?13?27?48?55?4取取d1=5d1=5一趟分组：一趟分组：49?38?65?97?4?13?27?48?55?76 一趟排一趟排序结果：序结果：13?27?48?55?4?49?38?65?97?7
17、623取取d2=3d2=3二趟分组：二趟分组：13?27?48?55?4?49?38?65?97?76二趟排二趟排序结果：序结果：13?4?48?38?27?49?55?65?97?76取取d3=1d3=1三趟分组：三趟分组：13?4?48?38?27?49?55?65?97?76三趟排三趟排序结果：序结果：4?13?27?38?48?49?55?65?76?9724 子序列的构成不是简单的子序列的构成不是简单的“逐段分割逐段分割”，而是将相隔某个增量的记录组成一个子而是将相隔某个增量的记录组成一个子序列序列 关键字较小的记录跳跃式前移，在进行关键字较小的记录跳跃式前移，在进行最后一趟增量为最
18、后一趟增量为1 1的插入排序时，序列已的插入排序时，序列已基本有序基本有序 设设n n为待排序记录个数，一般为待排序记录个数，一般didi取值如下：取值如下：d1?n/2，d2?d1/2，直到，直到di1。25 交换排序的基本思想是：利用交换数据元交换排序的基本思想是：利用交换数据元素的位置进行排序的方法。素的位置进行排序的方法。交换排序的主要算法有：交换排序的主要算法有：?1)?冒泡排序冒泡排序?2)?快速排序快速排序261 1、基本思路：、基本思路：每趟不断将记录两两比较，并按每趟不断将记录两两比较，并按“前小后大前小后大”（或（或“前大后小前大后小”）规则交换。）规则交换。2 2、优点：
19、、优点：每趟结束时，不仅能挤出一个最大值到最后面位每趟结束时，不仅能挤出一个最大值到最后面位置，还能置，还能同时部分理顺其他元素同时部分理顺其他元素；一旦下趟没有交；一旦下趟没有交换发生，还可以换发生，还可以提前结束排序提前结束排序。例：例：关键字序列关键字序列?T=(21，25，49，25*，16，08），请按从），请按从小到大的顺序，写出冒泡排序的具体实现过程。小到大的顺序，写出冒泡排序的具体实现过程。初态：初态：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟21，25，49，?25*，16，?0821，25，25*，16，?08?，?4921，25，?16，?08?，25*，4921
20、，16，?08?，25，?25*，4916，08?，21，?25，?25*，4908，16，?21，?25，?25*，4927 void BubbleSort(DataType a,int n)void BubbleSort(DataType a,int n)?int i,j,flag=1;int i,j,flag=1;DataType temp;DataType temp;for(i=1;i n&flag=1;i+)for(i=1;i n&flag=1;i+)?flag=0;flag=0;for(j=0;j n-i;j+)for(j=0;j aj+1.key)if(aj.key aj+1.k
21、ey)flag=1;flag=1;temp=aj;temp=aj;aj=aj+1;aj=aj+1;aj+1=temp;aj+1=temp;282.1 2.1 冒泡排序的算法分析冒泡排序的算法分析最好情况：最好情况：初始排列已经有序，只执行一趟起泡，做初始排列已经有序，只执行一趟起泡，做?n-1?次关键码比较，不移动对象。次关键码比较，不移动对象。最坏情形：最坏情形：初始排列逆序，初始排列逆序，算法要执行算法要执行n-1 1趟起泡，第趟起泡，第i趟趟(1?i?n)做了做了n-i 次关键码比较，执行了次关键码比较，执行了n-i 次对象交换。次对象交换。此时的比较总次数此时的比较总次数KCN和记录移
22、动次数和记录移动次数RMN为：为：11111233121nininninRMNnninKCN)()()()(因此：因此：时间效率：时间效率：O O（n n2 2)因为要考虑最坏情况因为要考虑最坏情况空间效率：空间效率：O O（1 1）只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元稳稳 定定 性：性：稳定稳定 2525和和2525*在排序前后的次序未改变在排序前后的次序未改变292.2?快速排序快速排序冒泡排序的一种改进算法。冒泡排序的一种改进算法。思想思想:以以首记录首记录作为作为轴记录轴记录，从前、后双向扫描序列，通过交换，实，从前、后双向扫描序列，通过交换，实现大值记录后移，小值记录
23、前移，最终将轴记录安置在一个适现大值记录后移，小值记录前移，最终将轴记录安置在一个适当的位置。当的位置。(小值记录在前、大值记录在后小值记录在前、大值记录在后)?轴记录轴记录将原序列分割成两部分，依次对前后两部分重新设定轴将原序列分割成两部分，依次对前后两部分重新设定轴记录，继而分别再进行快速排序。记录，继而分别再进行快速排序。直至整个序列有序。直至整个序列有序。30Input:an array Ap,rQuicksort(A,p,r)if(p r)q=Partition(A,p,r)/q是基准关键字的位置Quicksort(A,p,q-1)Quicksort(A,q+1,r)31 一趟快速排
24、序的过程一趟快速排序的过程(partition)(partition)：附设两附设两个指针个指针 i i 和和j j，i i 指向第一个关键字指向第一个关键字(基基准关键字准关键字),),j j 指向最后一个关键字。指向最后一个关键字。首先首先从从 j j 所指位置开始所指位置开始向前查找向前查找第一个第一个关键字关键字小于小于 keykey 的记录，找到后将其的记录，找到后将其和和 i i 所指记录所指记录交换交换。然后再然后再从从 i i 所指位置开始所指位置开始向后查找向后查找第一第一个关键字个关键字大于大于 key key 的记录，找到后将其的记录，找到后将其和和 j j 所指记录所指
25、记录交换交换。重复上述两步，直到重复上述两步，直到 i?j 为止。此时，为止。此时，所有比所有比 keykey 小的关键字都放到左边，所有小的关键字都放到左边，所有比比 key key 大的关键字都放到右边大的关键字都放到右边32 4 6?5 5?1 3?4 2?9 4?0 5?1 7?7 0?i?j?4 6?5 5?1 3?4 2?9 4?0 5?1 7?7 0?i?j?1 7?5 5?1 3?4 2?9 4?0 5?4 6?7 0?i?j?1 7?4 6?1 3?4 2?9 4?0 5?5 5?7 0?i?j?1 7?0 5?1 3?4 2?9 4?4 6?5 5?7 0?i?j?1 7?
26、0 5?1 3?4 2?9 4?4 6?5 5?7 0?i?j?1 7?0 5?1 3?4 2?9 4?4 6?5 5?7 0?i?j?1 7?0 5?1 3?4 2?4 6?9 4?5 5?7 0?i?j?快快速速排排序序的的一一次次划划分分?33void?quicksort(ElemType?R,int?left?,?int?right)?int?i=left?,?j=right;?ElemType?temp=Ri;?while?(itemp)&(ji)?j=j-1;?if?(ji)?Ri=Rj;?i=i+1;?while?(Rii)?i=i+1;?if?(ij)?Rj=Ri;?j=j-1
27、;?/一次划分得到基准值的正确位置一次划分得到基准值的正确位置Ri=temp;?if?(lefti-1)?quicksort(R,left,i-1);?/递归调用左子区间递归调用左子区间?if?(i+1right)?quicksort(R,i+1,right);?/递归调用右子区间递归调用右子区间34时间复杂度：最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n)空间复杂度：需栈空间以实现递归最坏情况：S(n)=O(n)一般情况：S(n)=O(log2n)35 选择排序选择排序的基本思想是：的基本思想是：每次每次从待排序
28、的数据元从待排序的数据元素集合中素集合中选取选取关键字关键字最小（或最大）最小（或最大）的数据元素的数据元素放到放到数据元素集合的数据元素集合的最前（或最后）最前（或最后），数据元素集合不断，数据元素集合不断缩小，当数据元素集合为空时选择排序结束。缩小，当数据元素集合为空时选择排序结束。常用的选择排序算法：常用的选择排序算法：?（1）直接选择排序直接选择排序?（2）堆排序堆排序361 1、其基本思想、其基本思想 每经过一趟比较就找出一个最小值，与待排序列最前每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。面的位置互换即可。（即即从待排序的数据元素集合中从待排序的数据元素集合中选
29、取关键字最小选取关键字最小的数据元的数据元素并将它与原始数据元素集合中的素并将它与原始数据元素集合中的第一个第一个数据元素数据元素交换位交换位置置；然后从；然后从不不包括包括第一个位置第一个位置的数据元素集合中的数据元素集合中选取关键选取关键字最小字最小的数据元素并将它与原始数据集合中的的数据元素并将它与原始数据集合中的第二个第二个数据数据元素交换位置；如此重复，直到数据元素集合中只剩一个元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素为止。）数据元素为止。）2 2、优缺点、优缺点优点：优点：实现简单实现简单缺点：缺点：每趟只能确定一个元素，表长为每趟只能确定一个元素，表长为n n时
30、需要时需要n-1n-1趟趟37例：例：关键字序列关键字序列T=T=（2121，2525，4949，2525*，1616，0808），请给出简单选择排序的具体实现过程。，请给出简单选择排序的具体实现过程。原始序列：原始序列：?21，25，49，25*，16，08第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟08，25，49，25*，16，2108，16,?49，25*，25，2108，16,?21，25*，25，4908，16,?21，25*，25，4908，16,?21，25*，25，493、算法分析、算法分析时间效率：时间效率：?O(nO(n2 2)虽移动次数较少，但比较次数仍多。虽移动
31、次数较少，但比较次数仍多。空间效率：空间效率：O O（1 1）没有附加单元（仅用到没有附加单元（仅用到1 1个个temp)temp)?算法的稳定性：算法的稳定性：不稳定不稳定38void SelectSort(DataType a,int n)void SelectSort(DataType a,int n)?int i,j,small;int i,j,small;DataType temp;DataType temp;for(i=0;i n-1;i+)for(i=0;i n-1;i+)?small=i;small=i;for(j=i+1;jn;j+)for(j=i+1;jn;j+)if(aj
32、.key asmall.key)small=j;if(aj.key asmall.key)small=j;if(small!=i)temp=ai;if(small!=i)temp=ai;ai=asmall;ai=asmall;asmall=temp;asmall=temp;39堆的定义：堆的定义：n n个元素的序列（个元素的序列（k1,k2,k1,k2,，kn)kn)，当且，当且仅当满足下列关系时，称之为堆：仅当满足下列关系时，称之为堆：或或(?i=1,2,.n/2?)?kik2ikik2i+1kik2iKik2i+1若将此排序码按顺序组成一棵完全二叉树，则若将此排序码按顺序组成一棵完全二叉树
33、，则（1 1）称为小根堆（二叉树的所有根结点值小于或等于）称为小根堆（二叉树的所有根结点值小于或等于左右孩子的值），（左右孩子的值），（2 2）称为大根堆（二叉树的所有根）称为大根堆（二叉树的所有根结点值大于或等于左右孩子的值）。结点值大于或等于左右孩子的值）。40例例1?（96，83，27，38，11，9）例例2(13，38，27，50，76，65，49，97）962791138831327384965765097一个堆对应一棵完全二叉树。一个堆对应一棵完全二叉树。41 由例由例1 1和例和例2 2可以看出，如果一个序列可以看出，如果一个序列（k1,k2,k1,k2,，kn)kn)是堆，则是
34、堆，则堆顶元堆顶元素素（或完全二叉树的根结点）（或完全二叉树的根结点）必定为必定为序列中序列中n n个元素的最小值或最大值个元素的最小值或最大值。因此，在输出堆顶元素之后，如果把因此，在输出堆顶元素之后，如果把剩余的剩余的 n n1 1个元素重新建成一个堆，个元素重新建成一个堆，则可以得到则可以得到 n n个元素中的次小值。如个元素中的次小值。如此反复建立堆并输出堆顶元素，则可此反复建立堆并输出堆顶元素，则可以得到一个有序的序列。这个过程就以得到一个有序的序列。这个过程就称为称为堆排序堆排序。42由此可见，堆排序必须解决两个问题：由此可见，堆排序必须解决两个问题：如何由一个无序序列建成一个堆？
35、其如何由一个无序序列建成一个堆？其实本质就是一个反复筛选调新堆的过程实本质就是一个反复筛选调新堆的过程如何在输出堆顶元素之后，调整剩余如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？元素，使之成为一个新的堆？43 在输出堆顶元素之后，可以使用在输出堆顶元素之后，可以使用筛筛选法选法，来调整剩余的元素，使之成，来调整剩余的元素，使之成为一个新堆。为一个新堆。筛选法：输出堆筛选法：输出堆顶元素顶元素之后，以之后，以堆堆中最后一个元素替代之中最后一个元素替代之；然后；然后将根将根结点值结点值与左、右子树的根结点值进与左、右子树的根结点值进行比较，并行比较，并与其中小者进行交换与其中小者进行
36、交换；重复上述操作，直至叶子结点，将重复上述操作，直至叶子结点，将得到新的堆，称这个得到新的堆，称这个从堆顶至叶子从堆顶至叶子的调整过程为的调整过程为“筛选筛选”。44例1327384965765091 输出堆顶元素输出堆顶元素1313，将堆中最后一个元素将堆中最后一个元素9191代替代替1313。9127384965765013 堆被破坏，把根结点堆被破坏，把根结点9191与其右孩子与其右孩子2727交换交换452791384965765013 右子树不满足堆，右子树不满足堆，将其根将其根9191与右孩子与右孩子4949交换交换2749389165765013 新堆建成，新的新堆建成，新的堆
37、顶元素是堆顶元素是 27 2746练习题练习题1 1：关键字序列为：关键字序列为24，10，90，77，16，25，33，89，67，下图，下图为为由关键字序列建立的初始堆，请给出由关键字序列建立的初始堆，请给出删去堆顶元素删去堆顶元素1010之后整理堆的过程。之后整理堆的过程。10251633902467897747772516339024678910162577339024678910 把把1010和堆底元素和堆底元素7777交换后，需将交换后，需将7777和和1616交换。交换。将将7777和和2424交换。交换。48162524339077678910 重新整理好堆，新重新整理好堆，新
38、的堆顶元素是的堆顶元素是161649 现在讨论对现在讨论对 n n 个元素初始建堆的过程。个元素初始建堆的过程。建堆方法：对初始无序序列建堆的过建堆方法：对初始无序序列建堆的过程，就是一个反复进行筛选的过程。程，就是一个反复进行筛选的过程。对于有对于有 n n 个结点的完全二叉树，其个结点的完全二叉树，其最最后一个非终端结点后一个非终端结点是是第第 n/2n/2 个元素个元素，因此，筛选因此，筛选只需从第只需从第 n/2n/2 个元素开个元素开始对所有非终端结点进行始对所有非终端结点进行。505330362412479185?a.8个结点的初始状态个结点的初始状态例例5330362412479
39、185?b.从第从第4个结点开始筛选个结点开始筛选515330362412478591?c.对第对第3个结点开始筛选个结点开始筛选5312362430478591?d.以第以第2个结点为根的子个结点为根的子树已经是堆，不用筛选树已经是堆，不用筛选52?e.对根结点筛选对根结点筛选531236243047859112533624304785911224365330478591?初始堆如图：初始堆如图：53假设：关键字序列为假设：关键字序列为2424，1010，9090，7777，1616，2525，3333，8989，6767，请给出建初始堆的过程。，请给出建初始堆的过程。24901033251
40、6778967249010332516678977(3)(3)堆排序的过程：堆排序的过程：(实例讲解实例讲解)?对对n n个元素的序列进行堆排序，先将其建成堆，把根结个元素的序列进行堆排序，先将其建成堆，把根结点与第点与第n n个结点交换；调整前个结点交换；调整前n-1n-1个结点成为堆，再把根个结点成为堆，再把根结点与第结点与第n-1n-1个结点交换；重复上述操作，直到整个序个结点交换；重复上述操作，直到整个序列有序。列有序。5424251033901667897710252433901667897710251633902467897755（4）、堆排序算法分析：）、堆排序算法分析：时间效率
41、：时间效率：O(nlog2n)。因为整个排序过程中需因为整个排序过程中需要调用要调用n-1次堆顶点的调整，而每次堆排序算法次堆顶点的调整，而每次堆排序算法本身耗时为本身耗时为log2n；空间效率：空间效率：O(1)。仅在第二个仅在第二个for循环中交换记循环中交换记录时用到一个临时变量录时用到一个临时变量temptemp。稳定性：稳定性：不稳定。不稳定。优点：优点：对小文件效果不明显，但对大文件有效。对小文件效果不明显，但对大文件有效。564.1 4.1、归并排序的基本思想是：、归并排序的基本思想是：将两个（或以上）将两个（或以上）的有序表组成新的有序表。（归并排序主要是二路的有序表组成新的有
42、序表。（归并排序主要是二路归并排序）归并排序）4.2 4.2、二路归并排序：、二路归并排序：可以把一个长度为可以把一个长度为n n 的无序的无序序列看成是序列看成是 n n 个长度为个长度为 1 1 的有序子序列的有序子序列 ，首先，首先做两两归并，得到做两两归并，得到 n n/2/2 个长度为个长度为 2 2 的有序子的有序子序列序列 ；再做两两归并，；再做两两归并，如此重复，直到最后，如此重复，直到最后得到一个长度为得到一个长度为 n n 的有序序列。的有序序列。例：例：关键字序列关键字序列T=T=（2121，2525，4949，2525*，9393，6262，7272，0808，3737
43、，1616，5454），请给出归并排序的具体实），请给出归并排序的具体实现过程。现过程。5758void Merge(DataType a,int n,DataType swap,int k)/*k为有序子数组的长度，一次排序后的有序子序列存于数组swap中*/int m=0,u1,l2,i,j,u2;int l1=0;/*第一个有序子数组下界为0*/while(l1+k=n-1)l2=l1+k;/*计算第二个有序子数组下界*/u1=l2-1;/*计算第一个有序子数组上界*/u2=(l2+k-1=n-1)?l2+k-1:n-1;/*计算第二个有序子数组上界*/*两个有序子数组合并*/for(i
44、=l1,j=l2;i=u1&j=u2;m+)if(ai.key=aj.key)swapm=ai;i+;59 else swapm=aj;j+;/*子数组2已归并完，将子数组1中剩余的元素存到数组swap中*/while(i=u1)swapm=ai;m+;i+;/*子数组1已归并完，将子数组2中剩余的元素存到数组swap中*/while(j=u2)swapm=aj;m+;j+;l1=u2+1;/*将原始数组中只够一组的数据元素顺序存放到数组swap中*/for(i=l1;i n;i+,m+)swapm=ai;60因为在递归的归并排序算法中，函数因为在递归的归并排序算法中，函数Merge(?)做一
45、趟两路归做一趟两路归并排序，需要调用并排序，需要调用merge?(?)函数函数?n/(2len)?O(n/len)?次，次，而每次而每次merge(?)要执行比较要执行比较O(len)次，另外整个归并过程有次，另外整个归并过程有 log2n?“层层”?，所以算法总的时间复杂度为，所以算法总的时间复杂度为O(nlog2n)。因为需要一个与原始序列同样大小的辅助序列。这正是此因为需要一个与原始序列同样大小的辅助序列。这正是此算法的缺点。算法的缺点。61要讨论的问题：要讨论的问题：1.?什么是什么是“多关键字多关键字”排序？实现方法？排序？实现方法？2.?单逻辑关键字怎样单逻辑关键字怎样“按位值按位
46、值”排序？排序？基数排序的基本思想是：基数排序的基本思想是：借助多关键字排序的思想对单逻辑关键字进行排借助多关键字排序的思想对单逻辑关键字进行排序。即：用关键字序。即：用关键字不同的位值不同的位值进行排序。进行排序。62以上两例都是典型的多关键字排序！636465因为有分组，故此算法需递归实现。例：例：初始关键字序列初始关键字序列T=（32,?13,?27,?32*,?19，33），请分别），请分别用用MSD和和LSD进行排序，并讨论其优缺点。进行排序，并讨论其优缺点。法法1（MSD）：）：原始序列：原始序列：32,?13,?27,?32*,?19，?33?先按高位先按高位 排序：排序：（13
47、,?19）,?27,?（32,?32*，33）?再按低位再按低位排序排序?：?13,?19?，?27,?32,?32*,?33法法2（LSD）：）：?原始序列：原始序列：?32,?13,?27,?32*,?19?，33 先按低位先按低位排序：排序：?32,?32*,?13,?33,?27,?19?再按高位再按高位排序：排序：?13,?19?,?27,?32,?32*,?33无需分组，易编程实现！6611552164547077027755645402112170775554，64217002又称散列过程！又称散列过程！，1167排序时经过了反复的排序时经过了反复的“分配分配”和和“收集收集”过
48、程。当对关键字过程。当对关键字所有的位进行扫描排序后，整个序列便从无序变为有序了。所有的位进行扫描排序后，整个序列便从无序变为有序了。77556454021121707064542111027770645554211102，77，5568 设待排序的数据元素关键字是设待排序的数据元素关键字是m m位位d d进制整数（不足进制整数（不足 m m位的位的关键字在高位补关键字在高位补0 0），设置），设置d d个桶，令其编号分别为个桶，令其编号分别为0,1,2,d-10,1,2,d-1。(1)(1)首先，按关键字最低位的数值依次把各数据元素放到相应的桶首先，按关键字最低位的数值依次把各数据元素放到相
49、应的桶中中(2)(2)然后，按照桶号从小到大和进入桶中数据元素的先后次序收集然后，按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素；这样，就形成了数据元素集合的一分配在各桶中的数据元素；这样，就形成了数据元素集合的一个新的排列，称这样的一次排序过程为个新的排列，称这样的一次排序过程为一次基数排序一次基数排序。(3)(3)再对一次基数排序得到的数据元素序列按关键字次低位的数值再对一次基数排序得到的数据元素序列按关键字次低位的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大和依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶
50、中的数据元素进入桶中数据元素的先后次序收集分配在各桶中的数据元素(4)(4)这样的过程重复进行，当完成了第这样的过程重复进行，当完成了第m m次基数排序后，就得到了次基数排序后，就得到了排好序的数据元素序列。排好序的数据元素序列。69能！能！70e0?e1?e2?e3?e4?e5?e6?e7?e8?e9614738921485637101215530790306f0?f1?f2?f3?f4?f5?f6?f7?f8?f9r0f?e?eifi+1?530790921101614485215306637738r071e0?e1?e2?e3?e4?e5?e6?e7?e8?e96147389214856
