09 第9章 内部排序.pptx

第1页：第九章内部排序

第九章内部排序

第2页：第九章内容提要

本章内容:掌握内部排序的各种酸法和性能分析�9.1概述�9.2插入排序�9.3快速排序�9.4选择排序�9.5归并排序�9.7内部排序比较�本章重点

第3页：9.1概述

9.1概述

• 排序（Sorting）：将一组数据元素的任意系列，重新排列程一个按关键字的有序的序列（无序到有序）
• 排序结果与关键字有关
• 主关键字：任何一组数据元素的无序序列，排序后的结果是唯一的
• 次关键字：排序结果不唯一
• 根据数据量大小的不同，排序可以分为两种：
• 内部排序:在计算机的随机存储器中进行排序（内存）
• 外部排序：数据量大、内存放不下，需要外存操作返回

第4页：排序的基本操作

排序过程的两种基本操作：

• 比较关键字大小
• 记录移位
• 记录的移动方式与其存储结构有关：
• 顺序存储时，移动记录
• 连式存储时，修改指针
• 记录本身存储在一组连续的存储单元，并设置各存储位置的地址向量，排序时移动地址向量，排序结束后，按地址向量中的值调准记录的位置

第5页：9.2插入排序

9.2插入排序

• 插入排序的基本思想是：每一趟将一个待排的记录，按其关键字的大小插入到已经排好的子文件中适当位置上，直到全部记录插入完成为止。
• 常用的两种插入排序：
• 直接插入排序、希尔排序

第6页：直接插入排序

朋根

• 1）直接插入排序东华理工学院程
• 基本思想：将一个记录插入到已排好序的有序表中，有n个记录的插入排序要进行n-1趟排序；第i趟排序是在含有i-1个记录的有序表中插入第i个记录后变成含有i个记录的有序表

第7页：直接插入排序算法9.1

直接插入排序算法9.1

• VoidInsertSort(SqList&L){//对顺序表L作直接插入排序。for(i=2;i<=L.length;++i)ifLT(L.r[i].key,L.r[i-1].key){//将L.r[i]插入有序子表L.r[0] =L.r[i];//复制为哨兵for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];L.r[j+i]=L.r[0];//记录后移//插入到正确位置}
• }//InsertSort

第8页：直接插入排序的性能

时间复杂度：

• 最好为正序，比较次数为n-1
• 最坏为逆序，时间复杂度为i=(n+2)(n-1)/2;
• 平均约n2/4
• 时间复杂度为O(n2)

第9页：折半插入排序算法9.2

折半插入排序9.2

• 基本思想是在一个有序表中进行查找和插入
• VoidBInsertSort(SqList&L){//对顺序表L作折半插入顺序for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]Low=1;high=i-1;While(low<=high) {//在r[low..high]中折半查找有序插入的位置m=(low+high)/2;//折半ifLT(L.r[0].key,L.r[m].key)high=m-1;//插入点在低半区elselow= m+1;//插入点在高半区}//whilefor(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//记录后移L.r[high+1] =L.r[0];//插入}//for
• }//BInsertSort，时间复杂度为O(n2)

第10页：希尔排序

2）希尔排序

• 基本思想：选择一个记录间隔值d，把全部记录按此间隔值从第一记录起进行分组，所有相距为d的记录作为一组，先在各组内进行排序，然后缩小间距d重新分组，再进行组内排序，直到间隔值为１
• D的取值:d=n/2;di+1=di/2

第11页：希尔排序算法9.4

希尔排序算法9.4~5

• VoidShellInsert(SqList&L,intdk){//对顺序表L作一趟希尔插入排序。本算法和一趟直接插入排序相比，作了以下修改：//1、前后记录位置的增量是dk，而不是1；//2、r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。for(i=dk+1;i<=L.length;++i)ifLT(L.r[i].key,L.r[i-dk].key) {//需将L.r[i]插入有序增量子表L.r[0]=L.r[i];for(j=i-dk;//暂存在L.r[0]j>0&<(L.r[0].key,L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];L.r[j+dk]=L.r[0];//记录后移，查找插入位置//插入}
• }//ShellInsert//跟算法9.1一致，只是j的步长为dk而不是1

第12页：希尔排序算法9.5

VoidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0..t-1]对顺序表L作希尔排序。for(k=0;k<t;++t)Shellinsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序

• }//ShellSort

第13页：9.3快速排序

9.3快速排序

• 快速排序，有时叫交换排序
• 基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为准
• 常用的方法有
• 冒泡排序、快速排序

第14页：冒泡排序

基本思路

• 首先将第一个记录的关键字与第二个记录关键字比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字，依此类推，直到第n-1个记录和第n个记录的关键字进行比较为止，第一趟冒泡排序；
• 然后从第二个记录开始进行，第二趟，…，依此类推，进行n-1趟后就可达到目的
• 1）冒泡排序

第15页：冒泡排序算法

VoidBubble_Sort(inta[],intn){//将a中整数序列重排列成自小至大有序的整数序列for(i=n-1,change=TRUE;i>1&&chenge;--i){change=FALSEif([a[j]>a[j+1]) {a[j]七➔a[j+1];Change=TRUE;}

• }
• 算法的时间复杂度:
• 正序比较n-1次;O逆序为(i-1)=n(n-1)/2次
• 总时间复杂度为为O(n2)

第16页：快速排序的基本思想

2）快速排序

• 基本思想：
• 通过一趟排序将待排序的记录分成两个独立的部分，其中一部分记录的关键字均比另一部分的关键字小，然后继续分别对这两部分记录继续进行排序，以此类推，直到达到整体有序为止
• 总而言之，每趟使表的第一个元素入终位，将表一分为二，对子表按递归方式继续这种划分，直到划分的子表长度为1

第17页：快速排序的划分过程

设置两个指针low,high和枢轴记录pivotkey,从high位置起向前搜索找到第一个关键字小于pivotkey的记录放到low位置；

• 从low位置起向后搜索找到第一个关键字大于pivotkey的记录放到high位置
• 直到low＝high时将枢轴记录赋给位置

第18页：快速排序分割算法9.6(a)

快速排序算法——分割一9.6(a)

• intPartition(SqList&L,intlow,inthigh){//交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大（小）于它pivotkey=L.r[low].key;//用子表的第一个记录作枢轴记录while(low<high){//从表的两端交替地向中间扫描while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]f-开L.r[high];//将比枢轴记录小的记录交换到低端while(low<high&&L.r[high].key<=pivotkey)++low;L.r[low]f-开L.r[high];//将比枢轴记录大的记录交换到高端}returnlow;
• }//Partition//返回枢轴所在位置//交换记录，每次交换记录时做三次赋值操作

第19页：快速排序分割算法9.6(b)

快速排序算法——分割二9.6(b)

• intPartition(SqList&L,intlow,inthigh){L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录Pivotkey=L.r[low].key;//枢轴记录关键字While(low<high){//从表的两端交替地向中间扫描While(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];//将比枢轴记录小的记录移到低端while(low<high&&L.r[high].key<=pivotkey)++low;L.r[high]=L.r[low];//将比枢轴记录大的记录移到高端}L.r[low]=L.r[0];returnlow;//枢轴记录到位//返回枢轴位置
• }// Partition//只需要在一趟排序结束后才移动枢纽记录

第20页：快速排序算法QSort

快速排序算法

• voidQSort(Sqlist&L,intlow,lowhigh){//对顺序表L中的子序列L.r[low..high]作快速排序if(low<high){//长度大于1pivotloc=Partition(L,low,high);//将L.r[low..high]一分为二QSort(L,low,pivotloc-1);//对低子表递归排序//pivotloc是枢轴位置QSort(L,pivotloc+1,high);//对高子表递归排序}
• }//QSort
• voidQuickSort(SqList&L){//对顺序表L作快速排序。QSort(L,1,L.length);
• }//QSort

第21页：快速排序的时间复杂度

快速排序是目前公认最好的一种内部排序，时间复杂度为O(nlogn)

第22页：9.4选择排序

9.4选择排序

• 选择排序的基本思想是：每一趟从待排的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕
• 例如，在第i（i=1,2,…,n-1）趟排序中，在n-i+1个记录中选出关键字最小的记录作为有序序列中第i个记录
• 常用的两种排序：
• 直接选择排序（简单选择排序）、堆排序

第23页：简单选择排序的过程

一趟简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选出最小的记录j，并和第i个记录交换7654321ji趟次27137697653849原27497697653813611384976976527137226549769738271373365977649382713644769765493827137559776654938271376

• 1）简单选择排序

第24页：简单选择排序算法

简单选择排序算法

• voidSelectSort(SqList&L){//对顺序表L作简单选择排序。for(i=1;i<L.length;++i){并交换到位//选择第i小的记录，j=SelectMinKey(L,i);key最小的记录if(i! =j)L.r[i]七➔L.r[j];}
• }//SelectSort//在L.r[i..L.length]中选择//与第i个记录交换

第25页：堆排序的基本思想

2）堆排序

• 堆排序是在排序过程中，将顺序表中存储的数据看成是一棵安全二叉树，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小的记录

第26页：堆的构造

具体做法是：

• 把待排序的关键字放在数组r[1…n]中，将r看成是一棵二叉树，每个结点表示一个记录，原数组的第一个记录r[1]作为二叉树的根，以下各记录r[2…n]依次逐层从左到右顺序排列，构成一棵完全二叉树（任意结点r[i]的左孩子是r[2i]，右孩子是r[2i+1]，双亲是r[i/2]）
• 堆排序的关键是够造堆：假设完全二叉树的某一个结点i对于它的左子树、右子树已是堆，需要将r[2i].key与r[2i+1].key之中最大者与r[i].key比较，若r[2i].key较小则交换，这时可能破坏下一级的堆。于是继续采用上述方法构造下一级的堆，直到完全二叉树中结点构构成堆为止
• 对于任意一棵完全二叉树，从i=[n/2]到1反复利用上述思想建堆
• 输出堆顶元素后，以堆中最后一个元素替代它，剩下的n-1元素系列重新又建成一个堆，输出次小值，反复执行，则可得到一个有序序列

第27页：堆排序筛选过程示例

例如：8个元素的无序序列{49,38,65,97,76,13,27,49}38659749494938654997761327(a)无序表，考虑i=4,97761327(b)筛选97之后，考虑i=3,654938134997766527(c)筛选65之后，考虑i=2,38,不变4938134997766527(d)筛选38之后，考虑i=1,49

第28页：输出堆顶与重新筛选

(e)筛选49之后，生成的堆堆顶元素最小1338274976654997382749766549971937输出13之后，用最后一个元素97代替它

第29页：9.5归并排序

9.5归并排序

• 所谓归并排序就是将两个或两个以上的有序表合并成一个新的有序表的过程
• 假设表中有n个记录，则可以看成是n个有序的子序，每个子序的长度为1，然后两两合并，得到[n/2]个长度为2或1的有序子表
• 再两两合并，…，直到得到一个长度为n的表
• 时间复杂度为O(nlog2n)

第30页：

第31页：两表归并算法9.12

两表归并算法9.12

• voidMerge(RcdTypeSR[],rcdType&TR[],inti,intm,intn){//2路归并排序的核心是：将一维数组中前后相邻的两个有序表归并为一个有序序列，即将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]for(j=m+1,k=i;i<=m&&j<=n;++k){//将SR中记录由小到大地并入TRifLQ(SR[i].key,SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)TR[k..n] =SR[i..m];//将剩余的SR[i..m]复制到TRif(j<=n)TR[k..n] =SR[j..n];//将剩余的SR[j..n]复制到TR
• }//Merge

第32页：归并排序算法9.13

归并排序算法9.13~14

• voidMSort(RcdTypeSR[],RcdType&TR1[],ints,intt){//递归形式的2路归并排序，将SR[s..t]归并排序为TR1[s..t]。if(s= =t)TR1[s]=SR[s];//长度等于1else{m= (s+t)/2;//将SR[s..t]平分为SR[s..m]和SR[m+1..t]MSort(SR,TR2,s,m);//递归地将SR[s..m]归并为有序的TR2[s..m]MSort(SR,TR2,m+1,t);//递归地将SR[m+1..t]归并为有序的TR2[m+1..t]Merge(TR2,TR1,s,m,t);//将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]}
• }//MSort

第33页：归并排序算法9.14

voidMergeSort(SqList&L){//对顺序表L作归并排序。MSort(L.r,L.r,1,length);

• }//MergeSort
• //顺序表数据结构
• typedefstruct{RedTyper[MAXSIZE+1];intlength;
• }SqList;

第34页：9.6基数排序

9.6基数排序

• 基数排序的基本思想类似与扑克牌排队的方法
• 先按花色归类，然后按面值大小排序
• 先按面值大小排序，然后按花色分开归类
• 假设记录的关键字key由d位数字组成，即k1k2…kd，k1为高位，kd为低位，每一位的值都在0≦ki<rd范围内，rd称为基数
• 排序时先按低位的值对记录进行排序，在此基础上再进行次低位排序，依此类推，直到高位，则完成基数排序的整个过程

第35页：9.7内部排序比较

9.7内部排序比较

• 本章介绍的排序可以分为：
• 简单的直接排序：直接插入、冒泡法和直接选择排序，它门的时间复杂度一般是O(n2)，比较稳定
• 改进算法排序：希尔排序、快速排序、堆排序、归并排序的时间复杂度一般是O(nlog2n)，不够稳定
• 通常情况下，排序是按关键字进行的，排序方法是否稳定无关紧要
• 一般认为快速排序方法最快，其次是归并排序、希尔排序
• 各种方法有其特点和优势，由于各种情况的数据结构不同，很难确定用那种方法最好，要具体问题具体分析；有时将多种方法综合使用

第36页：本章重点

本章重点

• 了解各种排序的实现思想
• 重点掌握插入排序、快速排序、归并排序、希尔排序
• 要求：给出一组关键字，能利用各种排序方法描绘其实现过程，或经过一定步骤后的结果

第37页：习题（一）

1、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为插入排序。

• 2、在待排序的元素序列基本有序的前提下，效率最高的排序方法是插入排序。
• 3、对记录关键字为{50,26,38,80，70,90,8,30,40,20}进行排序，各趟排序结束时的结果为2040308907080382650708038269020403085070903850802040308269070805040383026208
• 其使用的排序方法是希尔排序。习题：

第38页：习题（二）

4、在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为O(n)。

• 5、一组记录的排序码为（17,48,24,35,69,82,23,79,36,72)，其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并排序后的结果为：17,24,35,48,23,69,79,82,36,72。
• 6、已知序列{10，18，4，3，6，12，1，9，15，8}，请给出采用归并排序法对该序列作升序排序的第一、二趟结果。第一趟结果：[10，18][3，4][6，12][1，9][8，15]第二趟结果：[3，4，10，18][1，6，9，12][8，15]

第39页：习题（三）

6、已知系列{503，87，512，61，908，170，897，275，653，462}，以第一个记录为枢轴（基准），写出采用快速排序法对该序列作升序排序时的第一趟的结果：[462，87，275，61，170]503[897，908，653，503]。