北邮数据结构排序课件

第八章排序北京邮电大学信息与通信工程学院《数据结构与STL》第八章排序学习内容：1.概述2.插入排序3.交换排序4.选择排序5.归并排序6.排序比较7.外部排序8.STL中相关排序算法2020/4/2621.概述《数据结构与STL》1概述排序给定一个记录序列，按照每个记录的关键码将记录进行重新排列，使关键码从小到大/从大到小有序。正序：关键码从小到大排列逆序：关键码从大到小排列2020/4/263《数据结构与STL》1概述趟在排序算法中，将待排序的记录扫描一遍称为一趟。稳定性待排序记录中具有相同关键码的记录，若排序前后，这些记录的相对位置不变，则为稳定排序；否则为不稳定。2020/4/264《数据结构与STL》1概述排序的分类根据是否将全部记录放进内存，分为内部排序和外部排序根据排序的原则，可以将排序分成：•插入排序•交换排序•选择排序•归并排序2020/4/265《数据结构与STL》1概述如何评价一个排序算法？排序的基本操作:比较和移动主要:比较的次数或移动次数较少的算法性能较好。次要:空间复杂度.算法本身的复杂度2020/4/266《数据结构与STL》第八章排序学习内容：1.概述2.插入排序3.交换排序4.选择排序5.归并排序6.排序比较7.外部排序8.STL中相关排序算法2020/4/2672.插入排序《数据结构与STL》插入排序主要内容1．存储结构2．直接插入排序3．希尔排序2020/4/268《数据结构与STL》1．存储结构排序使用顺序结构为了关注排序算法本身，所以本章所有排序的存储结构是0号位置留空的整型一维数组。intr[n];2020/4/269《数据结构与STL》2.插入排序插入排序的特征类似于玩纸牌时整理手中纸牌的过程。寻找一个指定记录在待排序记录中的位置，然后插入的排序算法。2020/4/2610《数据结构与STL》2.直接插入排序基本思想每次将一个待排序的记录按其关键码的大小插入到一个已经排序好的有序序列中，直到全部记录排序好。2020/4/2611《数据结构与STL》r1≤r2≤……≤ri-1|riri+1……rn有序区无序区插入到合适的位置2.直接插入排序需要解决的问题1）如何构造初始有序序列？2）如何找到插入的位置？2020/4/2612《数据结构与STL》r1≤r2≤……≤ri-1|riri+1……rn有序区无序区插入到合适的位置1）如何构造初始有序序列？2020/4/2613有序序列r[1]无序序列r[3..n]r[2]第一趟有序序列r[1..2]无序序列r[4..n]r[3]第二趟第n-1趟有序序列r[1..n-1]r[n]……《数据结构与STL》直接插入排序的过程2020/4/2614初始序列[12]15920103124第一趟[1215]920103124第二趟[91215]20103124第三趟[9121520]103124第四趟[910121520]3124第五趟[91012152031]24第六趟[9101215202431]《数据结构与STL》2）如何找到插入的位置？基本思想设置r[0]为“哨兵”，从后向前查找有序区，边查找边后移，直到找到合适的位置，将r[0]插入。2020/4/2615r1≤r2≤……≤ri-1|riri+1……rn有序区无序区插入到合适的位置r[0]=r[i];for(intj=i-1;r[0]r[j];j--)r[j+1]=r[j];r[j+1]=r[0];《数据结构与STL》if(r[i]r[i-1]){r[0]=r[i];for(intj=i-1;r[0]r[j];j--)r[j+1]=r[j];r[j+1]=r[0];}2.直接插入排序的算法voidInsertSort(intr[],intn)//升序排列{for(inti=2;i=n;i++)//i从2~n循环，共n-1趟排序{r[0]=r[i];for(intj=i-1;r[0]r[j];j--)r[j+1]=r[j];r[j+1]=r[0];}}2020/4/2616《数据结构与STL》2.直接插入排序的性能分析最好情况正序序列：比较移动最坏情况逆序序列：比较移动平均情况时间复杂度O(n2)空间复杂度O(1)nii2nii2)1(2020/4/26《数据结构与STL》17n-102.直接插入排序的特点稳定性插入排序是一种稳定的排序算法适用性尤其适合待排序记录基本有序的情况2020/4/2618《数据结构与STL》3.希尔排序希尔排序是对插入排序的一种改进,原因1)基本有序的序列，直接插入最快2)无序序列，记录数很少时，也很快基本思想将待排序的记录集分成多个子集，分别对这些子集进行排序，待整个序列基本有序时，在对记录进行一次直接插入排序。2020/4/2619《数据结构与STL》3.希尔排序2020/4/2620《数据结构与STL》49386597761327495504原始序列d=10/2=513274955044938659776第一趟d=5/2=23.希尔排序2020/4/2621《数据结构与STL》04271349385549659776第二趟d=2/2=104132738494955657697第三趟3.希尔排序（缩小增量排序）具体排序过程设待排序对象序列有n个记录,先取dn，比如d=n/2作为间隔,将全部对象分为d个子序列,对每一个子序列中分别施行直接插入排序。然后缩小间隔d,例如取d=d/2，重复上述的子序列划分和排序工作。直到最后取d=1,将所有对象放在同一个序列中排序为止。2020/4/2622《数据结构与STL》3.希尔排序希尔排序的子序列划分for(intd=n/2;d=1;d=d/2)//以d为增量{以d为增量，在子序列中进行插入排序。}2020/4/2623《数据结构与STL》希尔排序假设增量=d，则一趟希尔排序的过程for(inti=d+1;i=n;i++)//一趟希尔排序{if(r[i]r[i-d]){r[0]=r[i];for(intj=i-d;j0&&r[0]r[j];j=j-d)r[j+d]=r[j];r[j+d]=r[0];}}2020/4/2624《数据结构与STL》2020/4/26《数据结构与STL》251338557613274955044938659776042765494997假设增量=3，则一趟希尔排序的过程3.希尔排序voidShellInsert(intr[],intn){for(intd=n/2;d=1;d=d/2)//以d为增量{for(inti=d+1;i=n;i++)//一趟希尔排序{if(r[i]r[i-d]){r[0]=r[i];for(intj=i-d;j0&&r[0]r[j];j=j-d)r[j+d]=r[j];r[j+d]=r[0];}}}}2020/4/2626《数据结构与STL》3.希尔排序的性能分析时间复杂度希尔排序的时间与“增量序列”有关，不同的“增量序列”时间复杂度不同。经过大量的实验，时间复杂度O(n2)和O(nlog2n)之间稳定性希尔排序是一种不稳定的排序算法2020/4/2627《数据结构与STL》第八章排序学习内容：1.概述2.插入排序4.选择排序5.归并排序6.排序比较7.外部排序8.STL中相关排序算法2020/4/26283.交换排序《数据结构与STL》交换排序主要内容1．存储结构2．起泡排序3．起泡排序（改进）4．快速排序5．快速排序（改进）2020/4/2629《数据结构与STL》1．存储结构排序使用顺序结构为了关注排序算法本身，所以本章所有排序的存储结构是0号位置留空的整型一维数组。intr[n];交换排序的特征在待排序的记录中选择两个记录，将它们的关键码进行比较，如果反序则交换它们的位置。2020/4/2630《数据结构与STL》2.起泡排序基本思想两两比较相邻的记录,如果反序,则交换位置,直到没有反序的记录为止。2020/4/2631无序序列r[1..i]有序序列r[i+1..n]反序则交换标记《数据结构与STL》起泡排序的过程2020/4/2632第一趟初始状态《数据结构与STL》第二趟无序区有序区无序区有序区2020/4/2633《数据结构与STL》2.起泡排序voidBubbleSort(intr[],intn){//外循环：总共需要遍历的趟数for(inti=1;in;i++)//n-1趟{//内循环：每一趟需要比较的次数for(intj=1;j=n-i;j++){if(r[j]r[j+1])//相邻元素比较{r[0]=r[j];r[j]=r[j+1];r[j+1]=r[0];}}}}2020/4/2634《数据结构与STL》3.起泡排序（改进）2020/4/26《数据结构与STL》35初始序列[5013559727384965]第一趟[1350559727384965][1350552797384965][1350552738974965][1350552738499765][13505527384965]97pos第二趟[13502755384965]97[13502738554965]97[1350273849]556597pospos=n3.起泡排序（改进）2020/4/26《数据结构与STL》36第三趟[1327503849]556597[1327385049]556597[13273849]50556597pos第四趟[13273849]50556597pos3.起泡排序（改进）具体过程1）初始状态无序区为r[1..n]2）对无序区从前向后，依次比较相邻记录，若反序则交换，并记录交换的位置pos。最后一次交换的位置pos，就是下一趟无序区r[1..pos]3）反复执行2），直到无序区中没有反序的记录2020/4/2637《数据结构与STL》3.起泡排序（改进）已知无序区r[1..pos]，则如何进行反序交换?intbound=pos;//带排序记录右边界pos=0;//标记，记录交换的位置for(inti=1;ibound;i++){if(r[i]r[i+1]){r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];pos=i;//记录最后交换的位置}}2020/4/2638《数据结构与STL》3.起泡排序（改进）voidBubbleSort(intr[],intn){intpos=n;while(pos!=0){intbound=pos;//本次无序记录的范围pos=0;for(inti=1;ibound;i++)if(r[i]r[i+1])//相邻记录比较{r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];//交换pos=i;}}}2020/4/2639《数据结构与STL》3.起泡排序的性能分析11)(niin2020/4/2640《数据结构与STL》最好情况正序序列：比较移动最坏情况逆序序列：比较移动平均情况时间复杂度O(n2)空间复杂度O(1)11)(*3niinn-104.快速排序快速排序是起泡排序的改进改进着眼点起泡排序：记录的比较和移动是在相邻位置进行，需要比较移动多次才能到最终的位置。快速排序：记录的比较和移动从两端向中间进行的，记录移动的距离较远。2020/4/2641《数据结构与STL》4.快速排序快速排序又叫分区交换排序，其基本思想：1.选择一个记录作为轴值，将记录分成2部分。2.分别对这两部分重复上述过程。2020/4/2642《数据结构与STL》[r1r2……ri-1]ri[ri+1ri+2……rn]全部=ri轴值全部=ri递归4.快速排序需要解决的问题1.如何选择基准记录？•记录集中的第一个记录。2.如何分区，使大于基准的记录后移，小于基准的记录前移？3.如何判决快速排序结束？•递归缩小分区，直到分区只有一个记