数据结构PPT演示课件

第7章 排序,排序（sorting）是计算机程序设计的一个特别重要的技术，计算机的各个应用领域都有它的身影。如在处理学生考试成绩和元素的查找等都涉及到了对数据的排序。排列有序的折半查找要比顺序查找的效率要高许多。本章主要给大家介绍几种常用的排序技术：插入排序、选择排序、交换排序、归并排序和基数排序。 本章重点和难点： 1、希尔排序 2、快速排序 3、堆排序 4、归并排序 5、基数排序,7.1 基本概念,排序：把一个无序的元素序列按照元素的关键字递增或递减排列为有序的序列。 假设包含n个元素（记录）的序列 (E1,E2,En) 其对应的关键字为 (k1,k2,kn) 需确定1,2,n的一种排列p1,p2,pn，使关键字满足以下非递减（或非递增）关系： kp1kp2kpn 从而使元素构成一个非递减（或非递增）的序列： (Ep1,Ep2,Epn) 这样的一种操作被称为排序。,7.1 基本概念,稳定排序和不稳定排序：在待排序的记录序列中，若存在两个或两个以上关键字想到呢个的记录。假设ki=kj(1in,1jn,ij)，且排序前的对应的记录Ei领先于Ej（即ij）。若在排序之后，如果元素Ei仍领先于Ej，则称这种排序采用的方法是稳定的。如果经过排序之后，元素Ej领先于Ei（即i6，所以需要先将22向后移动一个位置，然后将6插入到第一个位置，如图7.2所示。其中，阴影部分表示无序集，白色部分表示有序集。第2趟排序：将无序集的元素17从右到左依次与有序集中的元素比较，即先与22比较，因为176，所以将17放在第2个元素的位置，如图7.3所示。,7.2 插入排序,第3趟排序：将待排序集合中的元素8与已经有序的元素集合从右到左依次比较，先与22比较。因为86，所以将8放在第2个位置，如图7.4所示。,7.2 插入排序,假设待排序元素有8个，分别是17、46、32、87、58、9、50、38。使用直接插入排序对该元素序列的排序过程如图7.5所示。,7.2 插入排序,直接插入排序算法描述如下。void InsertSort(SqList *L)/*直接插入排序*/int i,j;DataType t;for(i=1;ilength;i+)/*前i个元素已经有序，从第i+1个元素开始与前i个有序的关键字比较*/t=L-datai+1;/*取出第i+1个元素，即待排序的元素*/j=i;while(j0/*将当前元素插入合适的位置*/,7.2 插入排序,7.2.2 折半插入排序 折半插入排序算法是直接插入排序的改进。它的主要改进在于，在已经有序的集合中使用折半查找法确定待排序元素的插入位置。在找到要插入的位置后，将待排序元素插入到相应的位置。 假设待排序元素有7个：67、53、73、21、34、98、12。使用折半插入排序对该元素序列第一趟排序过程如图7.6所示。,7.2 插入排序,第2趟折半插入排序过程如图7.7所示。,7.2 插入排序,void BinInsertSort(SqList *L)/*折半插入排序*/int i,j,mid,low,high;DataType t;for(i=1;ilength;i+)t=L-datai+1;/*取出第i+1个元素，即待排序的元素*/low=1,high=i;while(lowdatamid.keyt.key)high=mid-1;elselow=mid+1;for(j=i;j=low;j-)/*移动元素，空出要插入的位置*/L-dataj+1=L-dataj;L-datalow=t;/*将当前元素插入合适的位置*/,7.2 插入排序,7.2.3 希尔排序 希尔排序（shells sort）也称为缩小增量排序（diminishing increment sort），它也属于插入排序类的算法，但时间效率比前几种排序有较大改进。 设待排序元素为：48、26、66、57、32、85、55、19，使用希尔排序算法对该元素序列的排序过程如图7.8所示。,7.2 插入排序,相应地，希尔排序的算法可描述如下。void ShellInsert(SqList *L,int c)/*对顺序表L进行一次希尔排序，c是增量*/int i,j;DataType t;for(i=c+1;ilength;i+)/*将距离为c的元素作为一个子序列进行排序*/if(L-datai.keydatai-c.key)/*如果后者小于前者，则需要移动元素*/t=L-datai;for(j=i-c;j0/*依次将元素插入到正确的位置*/,7.2 插入排序,void ShellInsertSort(SqList *L,int delta,int m)/*希尔排序，每次调用算法ShellInsert,delta是存放增量的数组*/int i;for(i=0;inext=NULL。指针p指向待排序的链表，若有序序列为空，将p指向的第一个结点插入到空链表L中。然后将有序链表即L指向的链表的每一个结点与p指向的结点比较，并将结点*p插入到L指向的链表的恰当位置。重复执行上述操作，直到待排序链表为空。此时，L就是一个有序链表。,7.3 交换排序,7.3.1 冒泡排序 冒泡排序(bubble sort)是一种简单的交换类排序算法，它是通过交换相邻的两个数据元素，逐步将待排序序列变成有序序列。它的基本算法思想描述如下： 假设待排序元素有n个，从第1个元素开始，依次交换相邻的两个逆序元素，直到最后一个元素为止。当第1趟排序结束，就会将最大的元素移动到序列的末尾。然后按照以上方法进行第2趟排序，次大的元素将会被移动到序列的倒数第2个位置。依次类推，经过n-1趟排序后，整个元素序列就成了一个有序的序列。每趟排序过程中，值小的元素向前移动，值大的元素向后移动，就像气泡一样向上升，因此将这种排序方法称为冒泡排序。,7.3 交换排序,例如，有5个待排序元素55、26、48、63和37。第1趟排序：,7.3 交换排序,第2趟排序：从第1个元素开始，依次比较第1个元素与第2个元素、第2个元素与第3个元素、第3个元素与第4个元素，如果前者大于后者，则交换之；否则不进行交换。第2趟排序过程如图7.12所示。,7.3 交换排序,第3趟排序：按照以上方法，依次比较两个相邻元素，交换逆序的元素。第3趟排序过程如图7.13所示。 第4趟排序：此时，待排序元素只剩下26和37，只需要进行一次比较即可。因为26L-dataj+1.key)t=L-dataj;L-dataj=L-dataj+1;L-dataj+1=t;flag=1;,7.3 交换排序,快速排序的算法思想是：从待排序记录序列中选取一个记录（通常是第一个记录）作为枢轴，其关键字设为key，然后将其余关键字小于key的记录移至前面，而将关键字大于key的记录移至后面，结果将待排序记录序列分为两个子表，最后将关键字key的记录插入到其分界线的位置。我们将这个过程称为一趟快速排序。通过这一趟划分后，就以关键字为key的记录为界，将待排序序列分为两个子表，前面的子表所有记录的关键字均不大于key，而后面子表的所有记录的关键字均不小于key。继续对分割后的子表进行上述划分，直至所有子表的表长不超过1为止，此时的待排序记录就成了一个有序序列。,7.3 交换排序,【算法步骤】设待排序序列存放在数组a1n中，n为元素个数，设置两个指针i和j，初值分别为1和n，令a1作为枢轴元素赋给pivot，a1相当于空单元，然后执行以下操作： （1）j从右往左扫描，若aj.keypivot.key，将ai移至aj中，并执行一次j-操作； （3）重复执行（1）和（2），直到出现ij，则将元素pivot移动到ai中。此时整个元素序列在位置i被划分成两个部分，前一部分的元素关键字都小于ai.key，后一部分元素的关键字都大于等于ai.key。即完成了一趟快速排序。,7.3 交换排序,例如，一组待排序元素序列为55,22,44,67,35,77,18,69，依据快速排序的算法思想，得到第1趟排序的过程如图7.16所示。,7.3 交换排序,设待排序元素为55、22、44、67、35、77、18、69，用快速排序算法对该元素序列的排序过程如图7.17所示。,7.3 交换排序,进行一趟快速排序，即将元素序列进行一次划分的算法描述如下所示。int Partition(SqList *L,int low,int high)/*对顺序表L.rlow.high的元素进行一趟排序，使枢轴前面的元素关键字小于枢轴元素的关键字，枢轴后面的元素关键字大于等于枢轴元素的关键字，并返回枢轴位置*/ DataType t;KeyType pivotkey;pivotkey=(*L).datalow.key;/*将表的第一个元素作为枢轴元素*/t=(*L).datalow;while(low=pivotkey)/*从表的末端向前扫描*/high-;if(lowhigh)/*将当前high指向的元素保存在low位置*/(*L).datalow=(*L).datahigh;low+;,while(lowhigh/*返回枢轴所在位置*/,7.3 交换排序,7.3 交换排序,通过多次递归调用一次划分算法即一趟排序算法，可实现快速排序，其算法描述如下所示。void QuickSort(SqList *L,int low,int high)/*对顺序表L进行快速排序*/ int pivot;if(lowdatai;L-datai=L-dataj;L-dataj=t;,7.4 选择排序,7.4 选择排序,一组元素的关键字序列为(76,31,19,20,6,83,60,52)，简单选择排序的过程如图7.19所示。,7.4.2 堆排序 1什么是堆和堆排序 堆排序(heap sort) 主要是利用了二叉树的树形结构，按照完全二叉树的编号次序，将元素序列的关键字依次存放在相应的结点。然后从叶子结点开始，从互为兄弟的两个结点中（没有兄弟结点除外），选择一个较大（或较小）者与其双亲结点比较，如果该结点大于（或小于）双亲结点，则将两者进行交换，使较大（或较小）者成为双亲结点。将所有的结点都做类似操作，直到根结点为止。这时，根结点的元素值的关键字最大（或最小）。,7.4 选择排序,这样就构成了堆，堆中的每一个结点都大于（或小于）其孩子结点。堆的数学形式定义为：假设存在n个元素，其关键字序列为(k1,k2,ki,kn)，如果有： 则称此元素序列构成了一个堆。如果将这些元素的关键字存放在一维数组中，将此一维数组中的元素与完全二叉树一一对应起来，则完全二叉树中的每个非叶子结点的值都不小于（或不大于）孩子结点的值。,7.4 选择排序,在堆中，堆的根结点元素值一定是所有结点元素值的最大值或最小值。例如，序列（89,77,65,62,32,55,60,48）和（18,37,29,48,50,43,33,69,77,60）都是堆，相应的完全二叉树表示如图7.20所示。,7.4 选择排序,如果将堆中的根结点（堆顶）输出之后，然后将剩余的n-1个结点的元素值重新建立一个堆，则新堆的堆顶元素值是次大（或次小）值，将该堆顶元素输出。然后将剩余的n-2个结点的元素值重新建立一个堆，反复执行以上操作，直到堆中没有结点，就构成了一个有序序列，这样的重复建堆并输出堆顶元素的过程称为堆排序。,7.4 选择排序,2建堆 堆排序的过程就是建立堆和不断调整使剩余结点构成新堆的过程。假设将待排序的元素的关键字存放在数组a中，第1个元素的关键字a1表示二叉树的根结点，剩下的元素的关键字a a2n分别与二叉树中的结点按照层次从左到右一一对应。例如，a1的左孩子结点存放在a2中，右孩子结点存放在a3中，ai的左孩子结点存放在a2*i中，右孩子结点存放在a2*i+1中。,7.4 选择排序,例如，给定一组元素序列(27,58,42,53,42,69,50,62)，建立大顶堆的过程如图7.21所示。,7.4 选择排序,相应地，建立大顶堆的算法描述如下所示。void CreateHeap(SqList *H,int n)/*建立大顶堆*/int i;for(i=n/2;i=1;i-)/*从序号n/2开始建立大顶堆*/AdjustHeap(H,i,n);,7.4 选择排序,void AdjustHeap(SqList *H,int s,int m)/*调整H.datas.m的关键字，使其成为一个大顶堆*/ DataType t;int j;t=(*H).datas;/*将根结点暂时保存在t中*/for(j=2*s;j(*H).dataj.key)/*如果孩子结点的值小于根结点的值，则不进行交换*/break;(*H).datas=(*H).dataj;s=j;(*H).datas=t;/*将根结点插入到正确位置*/,7.4 选择排序,3调整堆 具体实现：当堆顶元素输出后，可以将堆顶元素放在堆的最后，即将第1个元素与最后一个元素交换a1an，则需要调整的元素序列就是a1n-1。从根结点开始，如果其左、右子树结点元素值大于根结点元素值，选择较大的一个进行交换。即如果a2a3，则将a1与a2比较，如果a1a2，则将a1与a2交换，否则不交换。如果a2a3，则将a1与a3交换，否则不交换。重复执行此操作，直到叶子结点不存在，就完成了堆的调整，构成了一个新堆。,7.4 选择排序,7.4 选择排序,例如，一个大顶堆的关键字序列为(69,62,50,58,42,42,27,53)，当输出69后，调整剩余的元素序列为大顶堆的过程如图7.22所示。,7.4 选择排序,调整堆的算法实现如下。void HeapSort(SqList *H)/*对顺序表H进行堆排序*/ DataType t;int i;CreateHeap(H,H-length);/*创建堆*/for(i=(*H).length;i1;i-)/*将堆顶元素与最后一个元素交换，重新调整堆*/ t=(*H).data1;(*H).data1=(*H).datai;(*H).datai=t;AdjustHeap(H,1,i-1);/*将(*H).data1.i-1调整为大顶堆*/,7.4 选择排序,例如，一个大顶堆的元素的关键字序列为(69,62,50,58,42,42,27,53)，其相应的完整的堆排序过程如图7.23所示。,7.4 选择排序,7.4.3 选择排序应用举例【例7_4】编写算法，利用简单选择排序和堆排序算法对一组关键字序列 (69,62,50,58,42,42,27,53)进行排序，要求输出每趟排序的结果。【分析】简单选择排序和堆排序都是一种不稳定的排序方法。它们的主要思想：每次从待排序元素中选择关键字最小（或最大）的元素，经过不断交换，重复执行以上操作，最后形成一个有序的序列。,7.4 选择排序,【例7_5】编写算法，对关键字序列(76,20,99,32,60,53,11,8,42)进行选择排序，要求使用链表实现。【分析】主要考察选择排序的算法思想和链表的操作。具体实现时，设置两个指针p和q，分别指向已排序链表和未排序链表。初始时，先创建一个链表，q指向该链表，p指向的链表为空。然后从q指向的链表中找到一个元素值最小的结点，将其取出并插入到p指向的链表中。重复执行以上操作直到q指向的链表为空，此时p指向的链表就是一个有序链表。,7.5 归并排序,7.5.1 2路归并排序算法 主要思想是：假设元素的个数是n，将每个元素作为一个有序的子序列，然后将相邻的两个子序列两两归并，得到个长度为2的有序子序列。然后将相邻的两个有序子序列两两归并，得到个长度为4的有序子序列。如此重复，直至得到一个长度为n的有序序列为止。 关键字序列(50,22,61,35,87,12,19,75)的2路归并排序的过程如图7.26所示。,7.5 归并排序,void Merge(DataType s,DataType t,int low,int mid,int high)/*将有序的slow.mid和smid+1.high归并为有序的tlow.high*/ int i,j,k;i=low,j=mid+1,k=low;while(i=mid,7.5 归并排序,void MergeSort(DataType s,DataType t,int low, int high)/*2路归并排序，将slow.high归并排序并存储到tlow.high中*/ int mid;DataType t2MaxSize;if(low=high)tlow=slow;elsemid=(low+high)/2;/*将slow.high分为slow.mid和smid+1.high*/MergeSort(s,t2,low,mid);/*将slow.mid归并为有序的t2low.mid*/MergeSort(s,t2,mid+1,high);/*将smid+1.high归并为有序的t2mid+1.high*/Merge(t2,t,low,mid,high);/*将t2low.mid和t2mid+1.high归并到tlow.high*/,7.5 归并排序,7.5.2 归并排序应用举例【例7_6】编写算法，请使用2路归并排序对一组关键字 (50,22,61,35,87,12,19,75)进行排序。,7.6 基数排序,7.6.1 基数排序算法 基数排序正是借助这种思想，对不同类的元素进行分类，然后对同一类中的元素进行排序，通过这样的一种过程，完成对元素序列的排序。在基数排序中，通常将对不同元素的分类称为分配，排序的过程称为收集。 具体算法思想：假设第i个元素ai的关键字keyi，keyi是由d位十进制组成，即keyi=kidkid-1ki1，其中ki1为最低位，kid为最高位。关键字的每一位数字都可作为一个子关键字。首先将元素序列按照最低的关键字进行排序，然后从低位到高位直到最高位依次进行排序，这样就完成了排序过程。,7.6 基数排序,例如，一组元素的关键字序列为(236,128,34,567,321,793,317,106)。 对最低位进行分配和收集的过程如图7.28所示。其中，数组fi保存第i个链表的头指针，数组ri保存第i个链表的尾指针。,7.6 基数排序,对十位数字分配和收集的过程如图7.29所示。对百位数字分配和收集的过程如图7.30所示。,7.6 基数排序,基数排序的算法主要包括分配和收集。静态链表类型定义描述如下：#define MaxNumKey 6 /*关键字项数的最大值*/#define Radix 10/*关键字基数，此时是十进制整数的基数*/#define MaxSize 1000typedef int KeyType;typedef structKeyType keyMaxNumKey; /*关键字*/int next;SListCell;/*静态链表的结点类型*/typedef structSListCell dataMaxSize;/*存储元素，data0为头结点*/int keynum;/*每个元素的当前关键字个数*/int length;/*静态链表的当前长度*/SList;/*静态链表类型*/typedef int addrRadix; /*指针数组类型*/,7.6 基数排序,基数排序的分配算法实现如下所示。void Distribute(SListCell data,int i,addr f,addr r) /*为data中的第i个关键字keyi建立Radix个子表，使同一子表中元素的keyi相同*/*f0.Radix-1和r0.Radix-1分别指向各个子表中第一个和最后一个元素*/ int j,p;for(j=0;jRadix;j+)/*将各个子表初始化为空表*/fj=0;for(p=data0.next;p;p=datap.next)j=trans(datap.keyi);/*将关键字字符转化为整数类型*/if(!fj)/*fj是空表，则fj指示第一个元素*/fj=p;elsedatarj.next=p;rj=p;/*将p所指的结点插入第j个子表中*/,7.6 基数排序,其中，数组fj和数组rj分别存放第j个子表的第一个元素的位置和最后一个元素的位置。基数排序的收集算法实现如下所示。void Collect(SListCell data,addr f,addr r)/*按keyi将f0.Radix-1所指各子表依次链接成一个静态链表*/ int j,t;for(j=0;!fj;j+);/*找第一个非空子表，succ为求后继函数*/data0.next=fj;t=rj;/*r0.next指向第一个非空子表中第一个结点*/while(jRadix-1)for(j=j+1;jRadix-1/*t指向最后一个非空子表中的最后一个结点*/,7.6 基数排序,基数排序通过多次调用分配算法和收集算法，从而实现排序，其算法实现如下所示。 void RadixSort(SList *L) /*对L进行基数排序，使得L成为按关键字非递减的静态链表，L.r0为头结点*/ int i; addr f,r; for(i=0;i(*L).keynum;i+)/*由低位到高位依次对各关键字进行分配和收集*/ Distribute(*L).data,i,f,r);/*第i趟分配*/Collect(*L).data,f,r);/*第i趟收集*/ ,7.7 小结,排序可分为插入排序、选择排序、交换排序、归并排序和基数排序。 直接插入排序算法实现最为简单，时间复杂度在最好、最坏和平均情况下都为(n2)。 简单选择排序算法的时间复杂度在最好、最坏和平均情况下都是O(n2)，而堆排序的时间复杂度在最好、最坏和平均情况下都是O(nlog2n)。 冒泡排序的平均时间复杂度为O(n2)，快速排序在最好和平均情况下时间复杂度为O(nlog2n)，最坏情况下时间复杂度为O(n2)。 归并排序时间复杂度在最好、最坏和平均情况下都为O(nlog2n)。 基数排序是一种不需要对关键字进行比较的一种排序算法。在任何情况下，基数排序的时间复杂度均为O(d(n+rd)。 从稳定性来看，直接插入排序、冒泡排序、归并排序和基数排序属于稳定的排序算法，希尔排序、快速排序、简单选择排序、堆排序属于不稳定的排序算法。,