新教案第十章内部排序课件

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,10.1,概述,10.2,插入排序,10.2.1,直接插入排序,10.2.2,希尔排序,10.3,交换排序,10.3.1,起泡排序,10.3.2,快速排序,第十章 内部排序,10.5,归并排序,10.4,选择排序,10.4.1,简单选择排序,10.4.2,堆排序,10.1 概述 第十章 内部排序10.5,基本术语,将一个数据元素(记录)的任意序列,重新排列成一个按关键字有序的序列。,-,排序,-稳定性,内部排序/外部排序,基本操作,-约定,概述,关键字相同的记录在排序过程中是否保持前后次序不变。,排序过程全在内存中进行,(1)比较关键字的大小;(2)移动记录。,#define MAXSIZE 20,typedef int KeyType;,typedef struct,KeyType key;,InfoType otherinfo;,RedType;,typedef struct,RedType rMAXSIZE+1;,int length;,SqList;,基本术语将一个数据元素(记录)的任意序列,重新排列成一个按关,10.2 插入排序,直接插入排序,直接插入排序,基本思想,:每次将一个记录插入到已排好序的有序表中,直到记录全部插入为止。,例1:已知待排序的记录的初始排列如下,R(49),R(38),R(65),R(97),R(76),R(13),R(27),R(49*),R(49),R(38),R(49),R(38)R(49),R(65),R(38)R(49)R(65),R(97),R(38)R(49)R(65),R(76),R(97),R(13),R(38)R(49)R(65)R(76)R(97),R(13),R(27),R(38)R(49)R(65)R(76)R(97),R(13)R(27)R(38)R(49)R(49*)R(65)R(76)R(97),10.2 插入排序直接插入排序 直接插入排序基本思想:,10.2 插入排序,算法,直接插入排序,算法,void InsertSort(SqList&L),for(i=2;i=L.length;+i),if LT(L.ri.key,L.ri-1.key),L.r0=L.ri;,for(j=i-1;LT(L.r0.key,L.rj.key);-j),L.rj+1=L.rj;,L.rj+1=L.r0;,10.2 插入排序算法 直接插入排序算法,例子,R(49),0 1 2 3 4 5 6 7 8,R(49),R(38)R(65)R(97)R(76)R(13)R(27)R(49*),2,3,4,5,6,7,8,R(49),R(38)R(65)R(97)R(76)R(13)R(27)R(49*),R(38),R(49),R(38)R(49)R(65),R(97)R(76)R(13)R(27)R(49*),R(65),R(49),R(38)R(49)R(65)R(97),R(76)R(13)R(27)R(49*),R(97),R(49),R(38)R(49)R(65)R(76)R(97),R(13)R(27)R(49*),R(76),R(49),R(13)R(38)R(49)R(65)R(76)R(97),R(27)R(49*),R(13),R(49),R(13)R(27)R(38)R(49)R(65)R(76)R(97),R(49*),R(27),R(49),R(13)R(27)R(38)R(49)R(49*)R(65)R(76)R(97),R(49*),R(49),R(49)R(65)R(97)R(76)R(13)R(27)R(49*),R(38),R(38),R(49),R(65)R(97)R(76)R(13)R(27)R(49*),R(38),i,稳定的排序方法,例子R(49)0 1 ,10.2 插入排序,算法效率,直接插入排序,void InsertSort(SqList&L),for(i=2;i=L.length;+i),if LT(L.ri.key,L.ri-1.key),L.r0=L.ri;,for(j=i-1;LT(L.r0,L.rj.key);-j),L.rj+1=L.rj;,L.rj+1=L.r0;,算法效率,10.2 插入排序算法效率 直接插入排序void In,10.2 插入排序,希尔排序,希尔排序,基本思想,:先将待排序记录序列分割成若干子序列分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。,10.2 插入排序希尔排序 希尔排序基本思想:先将待排,希尔排序例子,49 38 65 97 76 13 27 49*55 04,13,49,27,38,49*,65,55,97,13,27,49*,55,04,49,38,65,97,76,13,38,55,76,04,27,65,49*,49,97,13,04,49*,38,27,49,55,65,97,76,04,13,27,38,49*,49,55,65,76,97,不稳定的排序方法,希尔排序例子 49 38,10.2 插入排序,算法,希尔排序,算法,void ShellInsert(SqList&L,int dk),for(i=dk+1;i0j-=dk),L.rj+dk=L.rj;,L.rj+dk=L.r0;,void ShellSort(SqList&L,int dlta ,int t),/按照增量序列dlata0.t-1对顺序表L作希尔排序,for(k=0;kt;+t),ShellInsert(L,dltak);,10.2 插入排序算法 希尔排序算法,10.3 交换排序,起泡排序,起泡排序,基本思想,:,反复比较两两相邻元素，若不符合顺序要求，则交换相邻元素，直至有序为止,。,49,38,65,97,76,13,27,49*,38,49,65,13,27,49*,76,97,38,49,65,76,13,27,49*,97,38,49,65,97,76,13,27,49*,38,49,65,76,97,13,27,49*,38,49,65,76,13,27,97,49*,38,49,65,76,13,97,27,49*,38,49,13,27,49*,65,76,97,38,13,27,49,49*,65,76,97,13,27,38,49,49*,65,76,97,13,27,38,49,49*,65,76,97,稳定的排序方法,10.3 交换排序起泡排序 起泡排序基本思想:反复比较,10.3 交换排序,起泡排序算法,起泡排序,算法,void BubbleSort(SqList&L),noswap=FALSE;,for(i=1;iL.length+i),noswap=TRUE;,for(j=1;j=L.length-i;j+),if LT(L.rj+1.key,L.rj.key),tempL.rj+1;,L.rj+1=L.rj;,L.rjtemp;,nowapFALSE;,/if,/for,10.3 交换排序起泡排序算法 起泡排序算法void,10.3 交换排序,快速排序基本思想,快速排序,基本思想,:划分,49,38,65,97,76,13,27,49*,27,38,13,49,76,97,65,49*,(1)对待排序序列进行划分；,(2)对前半子序列进行快速排序；,(3)对后半子序列进行快速排序.,10.3 交换排序快速排序基本思想 快速排序基本思想:,例子,一趟快速排序结束,49,38,65,97,76,13,27,49*,49,low,high,high,27,38,65,97,76,13,49*,49,low,high,low,27,38,97,76,13,65,49*,49,high,low,27,38,13,97,76,65,49*,49,high,low,high,27,38,13,76,97,65,49*,49,high,low,low,high,27,38,13,49,76,97,65,49*,49,例子一趟快速排序结束4938659776132749*49l,例子,27,38,13,49,76,97,65,49*,49,49,38,65,97,76,13,27,49*,27,38,13,27,13,27,38,76,97,65,49*,76,49*,65,76,97,49*,65,49*,49*,65,13,27,38,49,49*65,76 97,例子2738134976976549*49493865977,10.3 交换排序,算法,快速排序,算法,int Partition(SqList&L,int low,int high),/对顺序表L中子表L.rlow.high进行一次划分,L.r0=L.rlow;/子表第一个记录作为枢轴记录,pivotkey=L.rrow.key;,while(lowhigh)/从表的两端交替地向中间扫描,while(low=pivotkey)-high;,L.rlow=L.rhigh;,while(lowhigh,L.rhigh=L.rlow;,L.rlow=L.r0;,return low;,10.3 交换排序算法 快速排序算法int Parti,10.3 交换排序,算法,快速排序,算法,void QSort(Sqlist&L,int low,int high),/对顺序表L中的子序列L.rlow.hight作快速排序,if(lowhigh)/长度大于1,pivotloc=Partition(L,low,high);,QSort(L,low,pivotloc-1);,QSort(L,pivotloc+1,high);,void QuickSort(SqList&L),/对顺序表L作快速排序,QSort(L,1,L.length);,10.3 交换排序算法 快速排序算法void QSor,10.4 选择排序,选择排序,基本思想,每趟在n-i+1(i=1,2,.,n-1)个记录中选取关键字最小的记录作为,有序序列中第i个记录,简单选择排序,一趟排序:通过n-i次关键字间的比较,从n-i+1个记录中选出关键字,最小的记录,并和第i个记录交换,13,27,65,97,76,49,38,49*,13,27,38,97,76,49,65,49*,10.4 选择排序选择排序基本思想 每趟在n-i+1(,例子,49,38,65,97,76,13,27,49*,13,38,65,97,76,49,27,49*,13,27,65,97,76,49,38,49*,13,27,38,97,76,49,65,49*,13,27,38,49,76,97,65,49*,13,27,38,49,49*,97,65,76,13,27,38,49,49*,65,97,76,13,27,38,49,49*,65,76,97,13,27,38,49,49*,65,76,97,例子4938659776132749*13386597764,10.4 选择排序,算法,简单选择排序,算法,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;,时间复杂度:O(n,2,),10.4 选择排序算法 简单选择排序算法时间复杂度:O,10.4 选择排序,堆的定义,堆,堆排序,n个元素的序列K,1,K,2,.,K,n,当且仅当满足如下关系时,称为堆。,或,小根堆（大根堆）实质上是满足如下性质的完全二叉树：,树中任一非叶子结点的值均小于（大于）或等于它的孩子结点的值；,根结点（堆顶元素）为序列中n个元素的最小（大）值。,小根堆,大根堆,10.4 选择排序堆的定义堆 堆排序 n个元素的序列,10