14《数据结构》第十章 内部排序(下)

《14《数据结构》第十章 内部排序(下)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构北京邮电大学信息安全中心武斌上次课内容上一次课程（内部排序(上)）内容：理解排序的定义和各种排序方法的特点，并能加以灵活应用了解排序方法有不同的分类方法，基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类掌握各种排序方法的时间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。2本次课程学习目标学习完本次课程（内部排序(下)），您应该能够：理解选择排序、归并排序和基数排序等的定义和各种排序方法的特点，并能加

2、以灵活应用掌握选择排序、归并排序和基数排序等方法的时间复杂度的分析方法理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的通过各种内部排序方法的比较讨论，领会各种方法的特点3本章课程内容（第十章内部排序）10.1概述10.2插入排序10.3快速排序10.4选择排序10.5归并排序10.6基数排序10.7各种内部排序方法的比较讨论4选择排序选择排序(SelectionSort)的基本思想是：每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。其

3、中最简单且为读者最熟悉的是简单选择排序(SimpleSelectionSort)。1、简单选择排序第i(i=1,2,…,n-1)趟的简单选择排序（序列中前i-1个记录的关键字均小于后n-i+1个记录的关键字）的作法是，在后n-i+1个记录中选出关键字最小的记录，并将它和第i个记录进行互换。如图所示。5选择排序6选择排序算法10.11voidSelectSort(SqList&L){//对顺序表L作简单选择排序for(i=1;i

4、//在L.r[i..L.length]中选择关键字最小的记录if(i!=j)L.r[i]←→L.r[j];//与第i个记录互换}//for}//SelectSort无论待排序列处于什么状态，选择排序所需进行的“比较”次数都相n1n(n1)同，为(ni)，而“移动”次数在待排序列为“正序”时达最2i1小为0，在“逆序”时达最大为3(n-1)。因此其时间复杂度为：O(n2)7树形选择排序2、树形选择排序简单选择排序没有利用上次选择的结果，是造成速度慢的主要原因。如果能够加以改进，将会提高排序的速度。13选出最小者1

5、338133865132749386597761327498树形选择排序选出次最小者，应利用上次比较的结果。从被13打败的结点27、76、38中加以确定。1338133865132749386597761327499树形选择排序10选择排序3、堆排序“堆排序”也是一种选择类的排序方法，每一趟从记录的无序序列中选出一个关键字最大或最小的记录，和简单选择所不同的是，在第一趟选最大或最小关键字记录时先“建堆”，从而减少之后选择次大或次小关键字等一系列记录时所需的比较和移动次数

6、。定义：若含n个元素的序列{k,k,…,k}满足下列关系则称作“小12n顶堆”或“大顶堆”。“堆顶”元素为序列中的“最小值”或“最大值”。kik2ikik2in或,其中i1,2,...,kik2i1kik2i1211选择排序例如，{12,39,20,65,47,34,98,81,73,56}为“小顶堆”；{98,81,34,73,56,12,20,39,65,47}为“大顶堆”。若将上述数列视作为一个完全二叉树，则堆顶元素k即为二叉树的根结1点，k和k分别为k的“左子树根”和“右子树根”，

7、如下图所示。2i2i+1i12选择排序利用堆的特性进行的排序方法即为“堆排序”，其两个关键问题是：1)如何将一个无序序列调整为堆？2)如何在输出堆顶元素之后，调整剩余元素为一个新的堆？首先看第二个问题输出堆顶元素，以堆中最后一个元素代替之此时，堆顶元素的左右子树都为堆，仅需自上至下进行调整重新形成堆，这种自堆顶至叶子的调整过程叫做“筛选”。13堆排序valuesroot[1]7070[2]601[3]126012[4]4023[5]304030810[6]84567[7]1014堆排序valuesroot[1]7070

8、[2]601[3]126012[4]4023[5]304030810[6]84567[7]1015堆排序valuesroot[1]1010[2]601[3]126012[4]40234030870[5]304567[6]8NONEEDTOCONSI