数据结构排序算法.ppt

安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找第九章第九章排序排序本章要求本章要求【教学目的教学目的】掌握内排序方法的插入排序；选择排序；交掌握内排序方法的插入排序；选择排序；交换排序；基数排序；归并排序；排序的存储方式：连续地换排序；基数排序；归并排序；排序的存储方式：连续地址、静态链表、索引；稳定的和不稳定的排序方法的判定址、静态链表、索引；稳定的和不稳定的排序方法的判定方法，常见的稳定的排序方法和的不稳定的排序方法。了方法，常见的稳定的排序方法和的不稳定的排序方法。了解外部排序的方法以及外部排序方法的特点。解外部排序的方法以及外部排序方法的特点。【教学重点教学重点】每种排序方法的算法及算法的性能分析每种排序方法的算法及算法的性能分析【教学难点教学难点】排序方法的比较及稳定性的确定排序方法的比较及稳定性的确定安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找第八章第八章查找查找一、基本概念一、基本概念二、插入排序二、插入排序三、交换排序三、交换排序四、选择排序四、选择排序五、归并排序五、归并排序安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找一、基本概念一、基本概念排序的目的排序的目的排序是为了通过关键字高效的查找相关的记录排序是为了通过关键字高效的查找相关的记录排序排序就是要调整原文件中的记录顺序，使之按关键字就是要调整原文件中的记录顺序，使之按关键字递增递增(或递减或递减)次序排列起来。其形式化定义描述如下：次序排列起来。其形式化定义描述如下：输入：输入：n个记录个记录r1，r2，rn，其相应的关键字分别，其相应的关键字分别为为k1，k2，kn输出：输出：rl，r2，rn，使得，使得k1k2kn。(或或k1k2kn)/有序升序或者降序有序升序或者降序安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找一、基本概念一、基本概念排序的数据结构排序的数据结构待排序的记录采用顺序存储，待排序记录的定义为：待排序的记录采用顺序存储，待排序记录的定义为：#defineMAXSIZE100/*假定顺序表的最大长度为假定顺序表的最大长度为100*/typedefintKeyType；/*假定关键字类型为整数类型假定关键字类型为整数类型*/typedefstructKeyTypekey；/*关键字项关键字项*/OtherTypeother；/*其他项其他项*/DataType；/*数据元素类型数据元素类型*/typedefstructDataTyperMAXSIZE+1；/*r0闲置或充当哨兵*/intlength；/*顺序表长度顺序表长度*/SqList；/*顺序表类型顺序表类型*/安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找一、基本概念一、基本概念排序的数据结构排序的数据结构排序的排序的稳定性稳定性：若存在关键字相同的多个记录，经过：若存在关键字相同的多个记录，经过排序后这些具有相同关键字的记录之间的相对次序排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；否则则称这种排保持不变，该排序方法是稳定的；否则则称这种排序方法是不稳定的。序方法是不稳定的。排序的排序的分类分类：按是否涉及数据的内、外存交换分类：按是否涉及数据的内、外存交换分类：内排序、外排序。内排序、外排序。内部排序内部排序方法方法有：插入排序、选择排序、交换排序、有：插入排序、选择排序、交换排序、归并排序归并排序排序的排序的效率分析效率分析：时间代价和空间代价：时间代价和空间代价安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找二、插入排序二、插入排序基本思想基本思想通过构建有序序列，将待排序的数据，在已通过构建有序序列，将待排序的数据，在已排好序的序列中从后向前扫描，找到其相应位排好序的序列中从后向前扫描，找到其相应位置并进行插入操作。置并进行插入操作。直接插入排序直接插入排序二分法插入排序二分法插入排序Shell排序排序安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找二、插入排序二、插入排序直接插入排序直接插入排序算法思想：算法思想：将待插入子序列元素逐步插入到有序子序列中，设将待插入子序列元素逐步插入到有序子序列中，设有一待排序序列有一待排序序列S=r1，r2，r3，ri，rn,其中其中r1，r2，ri(1in)是按照关键字是按照关键字k1k2ki有序的子序列，有序的子序列，序列序列ri+1，rn无序。从序列无序。从序列ri+1，rn的第一个元的第一个元素素ri+1开始取数据元素，每取一个元素就将其插入到前面的有开始取数据元素，每取一个元素就将其插入到前面的有序序列中，并使插入后的序列有序，直到所有元素插入完成，序序列中，并使插入后的序列有序，直到所有元素插入完成，得到一个有序序列。得到一个有序序列。安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找二、插入排序二、插入排序直接插入排序直接插入排序算法：算法：voidStraightInsertSort(SqList*S)/*对顺序表对顺序表s中的中的s-r1.length作直接插入排序作直接插入排序*/for(i=2；ilength；i+)S-r0=S-ri；/*复制为哨兵复制为哨兵*/j=i-1;while(S-r0.keyrj.key)S-rj+1=S-rj；j-;/*记录后移记录后移*/S-rj+1=S-r0；/*插入到正确位置插入到正确位置*/能不能能不能改为改为=?安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找二、插入排序二、插入排序直接插入排序直接插入排序效率分析：效率分析：空间效率：空间效率：用了一个辅助单元用了一个辅助单元r0，因此辅助空间为，因此辅助空间为O(1)时间效率：时间效率：最好情形：待排序序列中各数据元素在排序前已按关键字大小最好情形：待排序序列中各数据元素在排序前已按关键字大小排好序，总的比较次数排好序，总的比较次数=n-1次次,总的移动次数总的移动次数=n-1次次,所以时间复所以时间复杂度为杂度为O（n）最坏情形：待排序序列中各数据元素为逆序状态时，最坏情形：待排序序列中各数据元素为逆序状态时，直接插入直接插入排序是稳排序是稳定的排序定的排序算法算法安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找二、插入排序二、插入排序二分插入排序二分插入排序算法思想：在插入第算法思想：在插入第i个关键码时，前个关键码时，前i1个关键已经有序，可个关键已经有序，可以通过折半的方式找到插入点。以通过折半的方式找到插入点。但是，虽然可以更快地找到插入点，但意义不大？但是，虽然可以更快地找到插入点，但意义不大？因为，找到插入点后还需要进行移动元素，并没有改变移动元因为，找到插入点后还需要进行移动元素，并没有改变移动元素的次数，因此其时间复杂度并没有发生改变。素的次数，因此其时间复杂度并没有发生改变。安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找二、插入排序二、插入排序Shell排序排序算法思想：先将待排序列分割为若干个子序列分别进行直接插算法思想：先将待排序列分割为若干个子序列分别进行直接插入排序；待整个序列基本有序时，再对全体记录进行一次直入排序；待整个序列基本有序时，再对全体记录进行一次直接插入排序接插入排序。也称缩小增量的直接插入排序。也称缩小增量的直接插入排序。安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找二、插入排序二、插入排序Shell排序排序算法：算法：voidShellInsert(SqList*s，intgap)/步长为步长为gap的插入排序的插入排序for(i=gap+1；ilength；i+)if(S-ri.keyri-gap.key)/*小于时，需将小于时，需将ri插入有序表插入有序表*/S-r0=S-ri；/*为统一算法设置监视哨为统一算法设置监视哨*/for(j=i-gap；j0&S-r0.keyrj.key；j=j-gap)S-rj+gap=S-rj；/*记录后移记录后移*/S-rj+gap=S-r0；/*插入到正确位置插入到正确位置*/*if*/endShellInsert安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找二、插入排序二、插入排序Shell排序排序算法：算法：voidShellSort(SqList*s，intgaps，intt)/*按增量序列按增量序列gaps0，1，t-1对顺序表对顺序表S作希尔排序作希尔排序*/for(k=0；kr2.key，则将两个，则将两个记录交换，紧接着依次比较记录交换，紧接着依次比较r2和和r3，直至，直至rn-1与与rn为止。这样一为止。这样一趟将关键字值最大的记录移至趟将关键字值最大的记录移至rn位置；位置；第二趟：比较第二趟：比较r1至让至让rn-1，关键字值次大的记录移动到第，关键字值次大的记录移动到第n-1位置，位置，方法同第一趟；方法同第一趟；依次完成第依次完成第3趟，第趟，第4趟，趟，n-1趟，直到所有记录都完成排序趟，直到所有记录都完成排序安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找三、交换排序三、交换排序起泡排序起泡排序算法：算法：voidBubbleSort(SqList*s)/*对顺序表对顺序表S作冒泡排序作冒泡排序*/inti,j;for(i=1；ilength-1；i+)/*进行进行n-1趟排序趟排序*/for(j=2;jlength-i;j+)if(S-rj.keyrj-1.key)S-r0=S-rj；/*S-rj与与S-rj-1交换交换*/S-rj=S-rj-1;S-rj-1=S-r0;安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找三、交换排序三、交换排序起泡排序起泡排序效率分析：效率分析：算法空间：算法空间：复杂度为复杂度为O(1)总的交换次数最多为总的交换次数最多为O(n2)，最少为，最少为0起泡排序起泡排序是稳定的是稳定的排序算法排序算法安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找三、交换排序三、交换排序快速排序快速排序算法思想：将一趟排序将待排序记录分割成独立的两部分，其算法思想：将一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字比另一部分记录的关键字小，然后分中一部分记录的关键字比另一部分记录的关键字小，然后分别对这两部分记录继续使用该方法排序，以达到整个序列有别对这两部分记录继续使用该方法排序，以达到整个序列有序。序。1.待排序序列待排序序列S中任意选择一个记录中任意选择一个记录r作为轴值作为轴值（设记录（设记录r的关键的关键字为字为k)。2.将剩余的记录分割成两个子序列将剩余的记录分割成两个子序列L和和R,子序列子序列L中的关键字均中的关键字均小于或等于小于或等于k，子序列，子序列R中所含记录的关键字均大于或等于中所含记录的关键字均大于或等于k。3.将子序列将子序列L中所有记录放在记录中所有记录放在记录r左边，子序列左边，子序列R中所有记录放中所有记录放在记录在记录r右边右边4.对于子序列对于子序列L和和R递归进行快速排序，直到子序列中只含有递归进行快速排序，直到子序列中只含有0或或1个元素个元素安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找三、交换排序三、交换排序快速排序快速排序算法：算法：intQuickSort1(SqList*s,intlow,inthigh)S-r0=S-rlow;/*以子表的第一个记录作为轴值记录以子表的第一个记录作为轴值记录*/pivotkey=S-rlow.key;/*取轴值记录关键字取轴值记录关键字*/while(lowhigh)/*从表的两端交替地向中间扫描从表的两端交替地向中间扫描*/while(lowrhigh.key=pivotkey)high-;S-rlow=S-rhigh;/*将比轴值记录小的交换到低端将比轴值记录小的交换到低端*/While(lowrlow.keyrhigh=S-rlow;/*将比轴值记录大的交换到高端将比轴值记录大的交换到高端*/S-rlow=S-r0;/*轴值（支点）记录到位轴值（支点）记录到位*/returnlow;/*返回轴值（支点）记录所在位置返回轴值（支点）记录所在位置*/安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找三、交换排序三、交换排序快速排序快速排序算法：算法：voidQuickSort(SqList*s,intlow,inthigh)/*对顺序表对顺序表S中的子序列中的子序列rlowhigh作快速排序作快速排序*/intpivotloc;if(lowhigh)pivotloc=QuickSort1(S,low,high);/*对小于轴值序列实现递归排序对小于轴值序列实现递归排序*/QuickSort(S,low,pivotloc-1);/*对大于轴值序列实现递归排序对大于轴值序列实现递归排序*/QuickSort(S,pivotloc+1,high);安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找三、交换排序三、交换排序快速排序快速排序效率分析：效率分析：算法空间：算法空间：复杂度为复杂度为O(logn)最坏情况：最坏情况：是每次划分选取的基准都是当前无序区中关键字最是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分前后无序区的元素个数减少一个，因此，排序必须做空，划分前后无序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做趟，每一趟中需做n-i次比较，所以最大比较次数为次比较，所以最大比较次数为安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找三、交换排序三、交换排序快速排序快速排序最好情况：最好情况：每次所取的每次所取的pivotkey是当前无序区的是当前无序区的“中值中值”，划，划分的结果是分的结果是pivotkey的左右两个无序子区的长度大致相等的左右两个无序子区的长度大致相等设设C(n)表示长度为表示长度为n的序列快速排序的比较次数，它等于长度为的序列快速排序的比较次数，它等于长度为n的无序区进行比较次数的无序区进行比较次数n-1，加上对划分所得的左右两个无序，加上对划分所得的左右两个无序子区进行快速排序所需的比较次数，假设文件长度子区进行快速排序所需的比较次数，假设文件长度n=2k，k=log2n，有：，有：快速排序快速排序不稳定不稳定安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找四、选择排序四、选择排序基本思想基本思想每一趟从待排序列中选取一个关键字最小的记每一趟从待排序列中选取一个关键字最小的记录，即第一趟从录，即第一趟从n个记录中选取关键字最小的个记录中选取关键字最小的记录，第二趟从剩下的记录，第二趟从剩下的n-1个记录中选取关键个记录中选取关键字次小的记录，直到整个序列的记录选完为止。字次小的记录，直到整个序列的记录选完为止。这样根据选取记录的顺序，可得到按关键字有这样根据选取记录的顺序，可得到按关键字有序的序列序的序列。简单选择排序简单选择排序堆排序堆排序安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找四、选择排序四、选择排序简单选择排序简单选择排序算法思想：算法思想：设待排序记录设待排序记录S=r1,r2,rn,假设待排序记录长为假设待排序记录长为n第一趟，从第一趟，从n个待排序记录中找出关键字最小的记录与第一个个待排序记录中找出关键字最小的记录与第一个记录交换；记录交换；第二趟，从第二个记录开始的第二趟，从第二个记录开始的n-1个待排序记录中再选出关键个待排序记录中再选出关键字最小的记录与第二个记录交换；字最小的记录与第二个记录交换；第第i趟，则从第趟，则从第i个记录开始的个记录开始的n-i+1个待排序记录中选出关键个待排序记录中选出关键字最小的记录与第字最小的记录与第i个记录交换，直到整个序列有序个记录交换，直到整个序列有序安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找四、选择排序四、选择排序简单选择排序简单选择排序算法：算法：voidSelectSort(SqList*s)for(i=1；ilength；i+)/*作作S-length-1趟选取趟选取*/for(j=i+1，t=i；jlength；j+)if(S-rt.keyS-rj.key)t=j；/*t中存放关键字最小的记录下标中存放关键字最小的记录下标*/tmp=S-rt;S-rt=S-ri;S-ri=tmp;/*关键字最小的记录与第关键字最小的记录与第i条记录交换条记录交换*/安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找四、选择排序四、选择排序简单选择排序简单选择排序效率分析：效率分析：算法空间：算法空间：复杂度为复杂度为O(1)简单选择排序第简单选择排序第i趟排序中选出关键字最小的记录，趟排序中选出关键字最小的记录，需做需做n-i次比较，因此总的比较次数为：次比较，因此总的比较次数为：简单选择排序简单选择排序是不稳定是不稳定安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找四、选择排序四、选择排序堆排序堆排序堆的定义：设有堆的定义：设有n个记录的关键字序列个记录的关键字序列k1，k2，kn，当且仅，当且仅当满足下述关系之一时，称之为当满足下述关系之一时，称之为堆。算法思想：算法思想：(1).建堆建堆(2).输出输出堆顶元素，堆顶元素，重建堆重建堆(3).重复重复2，直至输出所有元素，完成堆排序直至输出所有元素，完成堆排序安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找四、选择排序四、选择排序堆排序堆排序建堆算法示例：建堆算法示例：安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找四、选择排序四、选择排序堆排序堆排序建堆算法的一趟调整堆算法：建堆算法的一趟调整堆算法：voidHeapAdjust(SqList*s，intn，intm)/*S-rnm中的记录关键字除中的记录关键字除rn外均满足堆的定义，本外均满足堆的定义，本函数将对第函数将对第n个结点为根的子树筛选，使其成为大顶堆个结点为根的子树筛选，使其成为大顶堆*/rc=S-rn；i=n;for(j=2*i；j=m；j=j*2)/沿关键字较大的孩子结点向下筛选沿关键字较大的孩子结点向下筛选if(jrj.keyrj+1.key)j=j+1；/*j为为i两个孩子中关键字较大的元素下标两个孩子中关键字较大的元素下标*/if(rc.keyS-rj.key)break；/*rc应插入在位置应插入在位置i上上*/S-ri=S-rj；i=j；/*使使i结点满足堆定义结点满足堆定义*/S-ri=rc；/*插入插入*/安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找四、选择排序四、选择排序堆排序堆排序算法：算法：voidHeapSort(SqList*s)inti;for(i=S-length/2；i0；i-)/从第一个分支节点开始建堆从第一个分支节点开始建堆/*将将r1.length建成堆建成堆*/HeapAdjust(S，i，S-length)；for(i=S-length；i1；i-)/*堆顶与堆底元素交换堆顶与堆底元素交换,将最大元素移到后面将最大元素移到后面*/S-r1S-ri；HeapAdjust(S，1，i-1)；/*将将r1.i-1重新调整为堆重新调整为堆*/安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找四、选择排序四、选择排序堆排序堆排序效率分析：效率分析：堆排序适合记录很多的情形，它的时间复杂度为堆排序适合记录很多的情形，它的时间复杂度为O(nlog2n)。堆排序中初始建堆虽然时间复杂度为堆排序中初始建堆虽然时间复杂度为O(n)，但每次调整后面的，但每次调整后面的花费时间很少。花费时间很少。堆排序算法中增加了一个辅助空间，辅助空间为堆排序算法中增加了一个辅助空间，辅助空间为O(1)。堆排序时间效率基本与待排序记录的初始状态无关堆排序时间效率基本与待排序记录的初始状态无关堆排序算法是堆排序算法是不稳定不稳定安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找五、归并排序五、归并排序算法思想：算法思想：设有两个有序表设有两个有序表A和和B，对象个数分别为，对象个数分别为al和和bl，变，变量量i和和j分别是两表的当前指针。设表分别是两表的当前指针。设表C是归并后的新是归并后的新有序表，变量有序表，变量k是它的当前指针。是它的当前指针。i和和j对对A和和B遍历时，遍历时，依次将关键字小的对象放到依次将关键字小的对象放到C中，当中，当A或或B遍历结束遍历结束时，将另一个表的剩余部分照抄到新表中。时，将另一个表的剩余部分照抄到新表中。安徽工程大学计算机与信息学院电子教案第第八八章章 查查找找五、归并排序五、归并排序简单选择排序简单选择排序效率分析：效率分析：对对n个元素的归并排序，两两过程对应由叶向根生个元素的归并排序，两两过程对应由叶向根生成一棵二叉树的过程。所以归并趟数约等于二叉树的成一棵二叉树的过程。所以归并趟数约等于二叉树的高度高度-1，即，即log2n，每趟归并需移动记录，每趟归并需移动记录n次，故时间次，故时间复杂度为复杂度为O(nlog2n)。归并排序在最好和最坏情况下的时间复杂度都为归并排序在最好和最坏情况下的时间复杂度都为O(nlog2n)归并排序算法归并排序算法是稳定是稳定