资源描述
第八章排序,8.1排序的基本概念8.2插入类排序8.3选择类排序8.4交换类排序8.5归并排序,排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列排序过程的组成步骤：首先比较两个关键字的大小然后将记录从一个位置移动到另一个位置排序的分类：根据排序过程中所使用的内、外存情况内部排序外部排序,8.1排序的基本概念,排序方法的稳定性：对于具有同一排序码的多个纪录来说，采用的排序方法使排序后的记录的相对次序是否发生变化没有发生变化排序方法是稳定的发生了变化排序方法是不稳定的,例如：排序前：（45，32，67，24，32，86）排序后：（24，32，32，45，67，86）是稳定的排序（24，32，32，45，67，86）是不稳定的排序,8.1排序的基本概念,向量结构：将待排序的记录存放在一组地址连续的存储单元中链表结构：记录之间逻辑上的相邻性是靠指针来维持的记录向量与地址向量结合：将待排序的记录存放在一组地址连续的存储单元中，同时另设一个指示各个记录位置的地址向量,存储方法,记录结构,head,head,p,head,head,p,head,链表结构,记录向量与地址向量相结合,假设待排序的记录存放在地址连续的一组存储单元中，那么这种存储方式下的数据类型可描述为：,MAX,0,1,2,3,4,key,info,#defineMAX20typedefstructintkey;intotherinfo;RecordType;typedefstructRecordTypestMAX+1;intlength;RecordList;,0号元素为监视哨,直接插入排序基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。,8.2插入类排序,该算法适合于n较小的情况，时间复杂度为O(n2).,待排元素序列：532736156942第一次排序：275336156942第二次排序：273653156942第三次排序：152736536942第四次排序：152736536942第五次排序：152736425369,对于有n个数据元素的待排序列，插入操作要进行n-1次,8.2.1直接插入排序,voidinsertSort(RedTypeL,intn)inti,j;for(i=2;i=n;i+)if(Li.keyLi-1.key)L0=Li;/*作为监视哨*/for(j=i-1;L0.keyLj.key;j)Lj+1=Lj;/*记录后移*/Lj+1=L0;/*插入*/,8.2插入类排序,平均时间复杂度：O(n2)稳定性：稳定的排序方法,直接插入类排序分析,折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。折半插入排序的条件：在有序序列中插入一个关键字,8.2.2折半插入排序,(high36),(4253),折半插入排序过程,voidBinsertSort(RedTypeL,intn)inti,low,high,mid;for(i=2;i=high+1;j)Lj+1=Lj;/*记录后移*/Lhigh+1=L0;/*插入*/*for*/*折半插入排序*/,折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同。,/*折半后的位置*/,基本思想：先在待插入记录之前的有序子链表中查找应插入位置，然后将待插入记录插入链表,8.2.3表插入排序,基本思想：先将整个待排记录序列分割成若干序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序,8.2.4希尔排序,初始关键字序列：4655134294460770,第一趟排序结果：4646074294551370,4694465507134270,d1=4,1342464670940755,d2=3,第二趟排序结果：1346074270554694,希尔排序过程,第三趟排序结果：0742134646557094,0713467042465594,d3=2,d4=1,第二趟排序结果：1346074270554694,第四趟排序结果：0713424646557094,0713424646557094,希尔排序是一种不稳定的排序方法,希尔排序过程,简单选择排序基本思想：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并与第i个记录交换特点：其比较次数与关键字的初始排列状态无关,8.3选择类排序,初态,83916,83916,83916,83916,13986,13986,13986,简单选择排序过程,voidSelectSort(RedTypeL,intn)inti,j,k,t;for(i=1,i=n;+i）/*选择第i小的元素，并交换到位*/k=i；for(j=i+1;j=n;+j)if(Lj.keyLk.key)k=j;/*Lk中存放的是第I小的元素*/if(k!=i)t=Li;/*交换*/Li=Lk;Lk=t；/*FOR*/*SelectSort*/,8.3.1简单选择排序,平均时间复杂度：O(n2)稳定性：不稳定的排序方法例如：,简单选择排序分析,基本思想：每一趟在n-i+1个记录中选出关键字最小的记录作为有序序列中第i个记录,8.3.2树形选择排序,初始关键字序列：4655134294460770,07,第一趟选择结果,树形选择排序过程,初始关键字序列：4655134294460770,第二趟选择结果,树形选择排序过程,初始关键字序列：4655134294460770,第三趟选择结果,树形选择排序过程,初始关键字序列：4655134294460770,第四趟选择结果,树形选择排序过程,堆排序：也是一种选择排序。是具有特定条件的顺序存储的完全二叉树，其特定条件是：任何一个非叶子结点的关键字大于等于（或小于等于）子女的关键字的值。堆的示例,8.3.3堆排序,(a):堆顶元素取最大值,(b):堆顶元素取最小值,实现堆排序需解决两个问题：如何由一个无序序列建成一个堆？输出堆顶元素后，如何将剩余元素调整成一个新的堆？,8.3.3堆排序,把自堆顶至叶子的调整过程称为“筛选”。从一个无序序列建堆的过程就是一个反复”筛选“的过程。,调整堆的过程,具体做法：把待排序的记录的关键字存放在数组r1.n之中，将r看成是一棵完全二叉树的顺序表示，每个结点表示一个记录，第一个记录r1作为二叉树的根，以下各记录r2.n依次逐层从左到右顺序排列。然后对这棵完全二叉树进行调整。,建立堆的过程,(c):49被筛选后的状态,(d):56被筛选后的状态,(e):被筛选之后建成小根堆,初始关键字序列：2556497811654136,初始关键字序列：2556497811654136,A:,堆排序,交换排序的特点在于交换。有冒泡和快速排序两种。,8.3交换类排序,冒泡排序（起泡排序）思想：小的浮起，大的沉底。从左端开始比较。第一趟：第1个与第2个比较，大则交换；第2个与第3个比较，大则交换，关键字最大的记录交换到最后一个位置上；第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换到第n-1个位置上；依次类推，则完成排序。正序：时间复杂度为O(n)逆序：时间复杂度为O(n2)适合于数据较少的情况。排序n个记录的文件最多需要n-1趟冒泡排序。,8.3.1冒泡排序,第六趟排序后,第五趟排序后,第四趟排序后,第三趟排序后,第二趟排序后,第一趟排序后,初始关键字,思想：小的浮起，大的沉底。,冒泡排序的过程,冒泡排序的C程序段：Voidbubsort(RedTypeL,intn)chang=TRUE;for(i=1;i=n-1/*while*/*Bobsort*/,8.3.1冒泡排序,平均时间复杂度：O(n2)稳定性：稳定的排序方法例如：,初始关键字序列：4655134294460770,冒泡排序的性能分析,思想：通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。关键字通常取第一个记录的值为基准值。做法：附设两个指针low和high，初值分别指向第一个记录和最后一个记录，设关键字为key，首先从high所指位置起向前搜索，找到第一个小于基准值的记录与基准记录交换，然后从low所指位置起向后搜索，找到第一个大于基准值的记录与基准记录交换，重复这两步直至low=high为止。,8.3.2快速排序,有序序列618235267,key,low,high,一次交换185266723,low,high,二次交换182366752,high,三次交换186236752/完成一趟排序后分别进行快速排序,low,high,快速排序的过程,平均时间复杂度：O(log2n)稳定性：不稳定的排序方法,初始关键字序列：4862357755143598,快速排序的性能分析,初始序列23526761810一趟归并后23526671018二趟归并后62352671018三趟归并后61018235267,归并排序示例,功能：将两个或两个以上的有序表组成一个新的有序表。思想：把具有n个记录的表看成是n个有序的子表，每个子表的长度为1，然后两两归并，得到n/2个长度为2或为1的有序子表；再两两归并，如此重复，直到得到一个长度为n的有序表为止。,8.5归并排序,
展开阅读全文