《零基础学数据结构-第12章-内排序》由会员分享，可在线阅读，更多相关《零基础学数据结构-第12章-内排序（63页珍藏版）》请在金锄头文库上搜索。
1、第12章 排序,排序（sorting）是计算机程序设计的一个特别重要的技术，计算机的各个应用领域都有它的身影。如在处理学生考试成绩和元素的查找等都涉及到了对数据的排序。排列有序的折半查找要比顺序查找的效率要高许多。本章主要给大家介绍几种常用的排序技术：插入排序、选择排序、交换排序、归并排序和基数排序。本章重点和难点：1、希尔排序2、快速排序3、堆排序4、归并排序5、基数排序,12.1 基本概念,排序：把一个无序的元素序列按照元素的关键字递增或递减排列为有序的序列。假设包含n个元素（记录）的序列(E1,E2,En)其对应的关键字为(k1,k2,kn)需确定1,2,n的一种排列p1,p2,pn，使
2、关键字满足以下非递减（或非递增）关系：kp1kp2kpn从而使元素构成一个非递减（或非递增）的序列：(Ep1,Ep2,Epn)这样的一种操作被称为排序。,12.1 基本概念,稳定排序和不稳定排序：在待排序的记录序列中，若存在两个或两个以上关键字想到呢个的记录。假设ki=kj(1in,1jn,ij)，且排序前的对应的记录Ei领先于Ej（即ij）。若在排序之后，如果元素Ei仍领先于Ej，则称这种排序采用的方法是稳定的。如果经过排序之后，元素Ej领先于Ei（即i6，所以需要先将22向后移动一个位置，然后将6插入到第一个位置，如图12.2所示。其中，阴影部分表示无序集，白色部分表示有序集。第2趟排序：
3、将无序集的元素17从右到左依次与有序集中的元素比较，即先与22比较，因为176，所以将17放在第2个元素的位置，如图12.3所示。,12.2 插入排序,第3趟排序：将待排序集合中的元素8与已经有序的元素集合从右到左依次比较，先与22比较。因为86，所以将8放在第2个位置，如图12.4所示。,12.2 插入排序,假设待排序元素有8个，分别是17、46、32、87、58、9、50、38。使用直接插入排序对该元素序列的排序过程如图12.5所示。,12.2 插入排序,直接插入排序算法描述如下。 void InsertSort(SqList *L) /*直接插入排序*/ int i,j;DataType
4、 t;for(i=1;ilength;i+) /*前i个元素已经有序，从第i+1个元素开始与前i个有序的关键字比较*/t=L-datai+1; /*取出第i+1个元素，即待排序的元素*/j=i;while(j0 /*将当前元素插入合适的位置*/ ,12.2 插入排序,12.2.2 折半插入排序折半插入排序算法是直接插入排序的改进。它的主要改进在于，在已经有序的集合中使用折半查找法确定待排序元素的插入位置。在找到要插入的位置后，将待排序元素插入到相应的位置。假设待排序元素有7个：67、53、73、21、34、98、12。使用折半插入排序对该元素序列第一趟排序过程如图12.6所示。,12.2 插入
5、排序,第2趟折半插入排序过程如图12.7所示。,12.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; /*将当前元素插入
6、合适的位置*/ ,12.2 插入排序,12.2.3 希尔排序希尔排序（shells sort）也称为缩小增量排序（diminishing increment sort），它也属于插入排序类的算法，但时间效率比前几种排序有较大改进。设待排序元素为：48、26、66、57、32、85、55、19，使用希尔排序算法对该元素序列的排序过程如图12.8所示。,12.2 插入排序,相应地，希尔排序的算法可描述如下。 void ShellInsert(SqList *L,int c) /*对顺序表L进行一次希尔排序，c是增量*/ int i,j;DataType t;for(i=c+1;ilength;i+
7、) /*将距离为c的元素作为一个子序列进行排序*/if(L-datai.keydatai-c.key) /*如果后者小于前者，则需要移动元素*/t=L-datai;for(j=i-c;j0/*依次将元素插入到正确的位置*/ ,12.2 插入排序,void ShellInsertSort(SqList *L,int delta,int m) /*希尔排序，每次调用算法ShellInsert,delta是存放增量的数组*/ int i;for(i=0;inext=NULL。指针p指向待排序的链表，若有序序列为空，将p指向的第一个结点插入到空链表L中。然后将有序链表即L指向的链表的每一个结点与p指向
8、的结点比较，并将结点*p插入到L指向的链表的恰当位置。重复执行上述操作，直到待排序链表为空。此时，L就是一个有序链表。,12.3 交换排序,12.3.1 冒泡排序冒泡排序(bubble sort)是一种简单的交换类排序算法，它是通过交换相邻的两个数据元素，逐步将待排序序列变成有序序列。它的基本算法思想描述如下：假设待排序元素有n个，从第1个元素开始，依次交换相邻的两个逆序元素，直到最后一个元素为止。当第1趟排序结束，就会将最大的元素移动到序列的末尾。然后按照以上方法进行第2趟排序，次大的元素将会被移动到序列的倒数第2个位置。依次类推，经过n-1趟排序后，整个元素序列就成了一个有序的序列。每趟排
9、序过程中，值小的元素向前移动，值大的元素向后移动，就像气泡一样向上升，因此将这种排序方法称为冒泡排序。,12.3 交换排序,例如，有5个待排序元素55、26、48、63和37。 第1趟排序：,12.3 交换排序,第2趟排序：从第1个元素开始，依次比较第1个元素与第2个元素、第2个元素与第3个元素、第3个元素与第4个元素，如果前者大于后者，则交换之；否则不进行交换。第2趟排序过程如图12.12所示。,12.3 交换排序,第3趟排序：按照以上方法，依次比较两个相邻元素，交换逆序的元素。第3趟排序过程如图12.13所示。第4趟排序：此时，待排序元素只剩下26和37，只需要进行一次比较即可。因为26L
10、-dataj+1.key)t=L-dataj;L-dataj=L-dataj+1;L-dataj+1=t;flag=1; ,12.3 交换排序,快速排序的算法思想是：从待排序记录序列中选取一个记录（通常是第一个记录）作为枢轴，其关键字设为key，然后将其余关键字小于key的记录移至前面，而将关键字大于key的记录移至后面，结果将待排序记录序列分为两个子表，最后将关键字key的记录插入到其分界线的位置。我们将这个过程称为一趟快速排序。通过这一趟划分后，就以关键字为key的记录为界，将待排序序列分为两个子表，前面的子表所有记录的关键字均不大于key，而后面子表的所有记录的关键字均不小于key。继续
11、对分割后的子表进行上述划分，直至所有子表的表长不超过1为止，此时的待排序记录就成了一个有序序列。,12.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。即完成了一趟快速排序。,
