数据结构-排序

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Chapter 9Sorting,1,、插入排序（直接插入排序、希尔排序）,2,、交换排序（起泡排序、快速排序）,3,、选择排序（简单选择排序、堆排序）,4,、归并排序,教,学,内,容,排序：,将数据元素的一个任意序列，重新排列成一,个,按关键字有序,的序列。,9.1,概述,假设含,n,个记录的序列为,R,1,R,2,R,n,，其相应的关键字序列为,K,1,K,2,K,n,这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：,K,p,1,K,p,2,K,pn,按此固有关系将上式记录序列重新排列为,R,p,1,R,p,2,R,pn,的操作称作,排序,。,例：将关键字序列：,52 49 80 36 14 58 61 23,调整为：,14 23 36 49 52 58 61 80,设,K,i,=,K,j,(1,i,n,1,j,n,ij,),，,且在排序前的序列中,R,i,领先于,R,j,（,即,i,j,）。,若在排序后的序列中,R,i,仍领先于,R,j,，则称所用的,排序方法是稳定的,；反之，则称所用的,排序方法是不稳定的,。,设排序前的关键字序列为：,52,49,80,36,14,58,36,23,若排序后的关键字序列为：,14,23,36,36,49,52,58,80,，,则,排序方法是稳定的,。,若排序后的关键字序列为：,14,23,36,36,49,52,58,80,，,则,排序方法是不稳定的,。,内部排序和外部排序,若,整个排序过程不需要访问外存,便能完成，则称此类排序问题,为内部排序；,反之，若参加排序的记录数量很大，整个序列的排序过程,不可能在内存中完成,，则称此类排序问题,为外部排序,。,内部排序的方法,逐步扩大记录的有序序列的过程,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,经过一趟排序,9.2,插入排序,有序序列,R1.,i,-1,R,i,无序序列,R,i,.,n,有序序列,R1.,i,无序序列,R,i,+1.,n,实现“一趟插入排序”可分,三步,进行：,3,将,R,i,插入（复制）到,R,j,+1,的位置上。,2,将,R,j,+1.,i,-1,中的所有记录均后移一个位置；,1,在,R1.,i,-1,中查找,R,i,的插入位置，,R1.,j,.key,R,i,.key R,j,+1.,i,-1.key,；,一趟直接插入排序的基本思路,9.2.1,直接插入排序,初始状态,49,38,65,97,76,13,27,49,R,0,R,1,R,2,R,3,R,4,R,5,R,6,R,7,i,=1,i,=2,38,49,65,97,76,13,27,49,i,=3,38,49,65,97,76,13,27,49,i,=4,38,49,65,76,97,13,27,49,i,=5,38,49,65,76,97,13,27,49,i,=6,38,49,65,76,97,13,27,49,i,=7,38,49,65,76,97,13,27,49,49,38,65,97,76,13,27,49,49,38,排序过程：,先将序列中第,1,个记录看成是一个有序子序列，,然后从第,2,个记录开始，逐个进行插入，直至整个序列有序。,template,void Insert(,ElemType,elem,int,n),/,在数组,elem,中作插入排序,for(,int,i=1;i0j-),/,将比,elemj,大的元素交换到后面,Swap (elemj,elemj-1);,当,elemj,比它前面元素的关键字小时，就向前移动，直到遇到一个关键字比它大或相等的为止,T,(,n,)=,O,(,n,),算法评价,时间复杂度：,比较次数：,最好的情况：,待排序记录按关键字从小到大排列（正序）,比较次数：,最坏的情况：,待排序记录按关键字从大到小排列（逆序）,一般情况：,待排序记录是随机的，取平均值。,直接插入排序是稳定排序,9.2.2,希尔排序（缩小增量排序）,思路：,对待排序列先“宏观”调整，再“微观”调整。,排序过程：,先取一个正整数,d,1,n,，,把所有相隔,d,1,的记录放在一组内，组内进行直接插入排序；然后取,d,2,0;i-),for(int,j=0;jelemj+1.key),elem,j,elem,j,+1,9.3,交换排序,1,、冒泡排序,排序过程,初,始,关,键,字,49,38,65,97,76,13,27,49,第,一,趟,排,序,38,49,76,97,13,97,27,97,49,97,38,49,65,76,13,27,49,97,38,49,65,13,27,49,76,第,二,趟,排,序,38,49,13,27,49,65,第,三,趟,排,序,38,13,27,49,49,第,四,趟,排,序,13,27,38,49,第,五,趟,排,序,13,27,38,第,六,趟,排,序,时间复杂度,T,(,n,)=,O,(,n,2,),13,27,第,七,趟,排,序,一般取第一个记录,基本思想：,任选,一个记录，以它的关键字作为“,枢轴,”，凡关键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录均移至枢轴之后。,2,、一趟快速排序（一次划分）,low,high,设,Rs=52,为枢轴。,例：,52,52,49,80,36,14,58,61,97,23,75,high,23,low,low,80,high,high,high,high,14,low,low,52,课本,270,页,3,、快速排序,首先对无序的记录序列进行,“,一次划分,”,，之后分别对分割所得两个子序列,“,递归,”,进行一趟快速排序。,无 序 的 记 录 序 列,无序记录子序列,(1),无序子序列,(2),枢轴,一次划分,分别进行一趟快速排序,有 序 的 记 录 序 列,void QSort(,elem,int,low,int high),/,对顺序表,L,中的子序列,L.rlow.high,进行快速排序,if(low high)/,长度大于,1,/,QSort,int,pivotloc,=,Partition(elem,low,high);,/,对,L.rlow.high,进行一次划分,QSort(elem,low,pivotloc-1);,/,对低子序列递归排序，,pivotloc,是,枢轴位置,QSort(elem,pivotloc+1,high);/,对高子序列递归排序,第一次调用函数,Qsort,时,，待排序记录序列的上,下界分别为,0,和,n-1,。,void QuickSort(,elem,int,n),/,对顺序表进行快速排序,QSort(elem,0,n-1);,/,QuickSort,快速排序的时间分析,若待排序列中记录的关键字是随机分布的，则,k,取,1,至,n,中任一值的可能性相同。,由此可得快速排序所需时间的平均值为：,结论：,快速排序的时间复杂度为,O,(,n,log,n,),。,一次划分所需时间和表长成正比,到目前为止快速排序是,平均速度最大,的一种排序方法。,9.4,选择排序,9.4.1,简单选择排序,首先通过,n,1,次关键字比较，从,n,个记录中找出,关键字最小,的记录，将它与第一个记录交换。,再通过,n,2,次比较，从剩余的,n,1,个记录中找出关键字次小的记录，将它与第二个记录交换。,重复上述操作，共进行,n,1,趟排序后，排序结束。,例,一趟,:,13,38 65 97 76 49 27,i,=0,二趟,:,13 27,65 97 76 49 38,三趟,:,13 27 38,97 76 49 65,四趟,:,13 27 38 49,76 97 65,五趟,:,13 27 38 49 65,97 76,六趟,:,13 27 38 49 65 76,97,i,=4,i,=1,i,=2,i,=3,n,-1,n,-2,n,-6,初始,：,49 38 65 97 76 13 27,j,j,j,j,j,j,k,13,49,k,k,i,=5,排序结束,比较次数,for(,j,=,i,+1;,j,n,;,j,+),if(,elem,j,.key,elem,k,.key,),k,=,j,;,elem,i,elem,k,;,/,与第,i,个记录交换,void,SelectSort,(,ElemType,elem,int,n),/,SelectSort,比较次数：,时间复杂度：,O,(,n,2,),for(,i,=0;,i,n-1;+,i,),int,k=i;,堆的定义：,n,个元素的序列,(,k,1,k,2,k,n,),，,当且仅当满足下列关系时，称之为,堆,。,或,(,i,=1,2,n,/2),k,i,k,2,i,k,i,k,2,i,+1,k,i,k,2,i,k,i,k,2,i,+1,9.4.2,堆排序,可将堆序列看成完全二叉树，则：,k,2,i,是,k,i,的左孩子；,k,2,i,+1,是,k,i,的右孩子。,例,(96,83,27,38,11,09),(13,38,27,49,76,65,49,97),96,27,09,11,38,83,13,27,38,49,65,76,49,97,所有非终端结点的值均不大,(,小,),于其左右孩子结点的值。,堆顶元素必为序列中,n,个元素的最小值或最大值,。,小顶,堆,大顶堆,堆排序：,堆排序需解决的两个问题：,1,、如何由一个无序序列建成一个堆？,2,、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？,将无序序列建成一个堆,，得到关键字最小（大）的,记录；,输出堆顶的最小（大）值后，将剩余的,n,-1,个元,素重又建成一个堆,，则可得到,n,个元素的次小值；如此,重复执行，,直到堆中只有一个记录为止，每个记录出堆,的顺序就是一个有序序列,，这个过程叫,堆排序,。,堆,堆,筛选,所谓“筛选”指的是，对一棵左,/,右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。,第二个问题解决方法,筛选：,输出堆顶元素之后，,以堆中最后一个元素替代之,；,然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；,重复上述操作直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为,“,筛选,”,。,13,27,38,49,65,76,49,97,97,97,27,97,49,97,38,97,97,49,65,65,49,76,49,76,97,97,65,76,27,65,49,38,49,97,13,76,对深度为,k,的堆，“筛选”,所需进行的关键字比较的,次数至多为,2(,k,-1),。,81,73,64,27,98,12,第一个问题解决方法：,建堆是一个从下往上进行,“,筛选,”,的过程。,例,:,排序之前的关键字序列为：,40,55,49,36,12,36,73,49,98,81,98,49,40,现在，左,/,右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个,“,堆,”,即可。,81,73,55,从无序序列的下标为,(n-2)/2,的,元素（即无序序列对应的完全二叉树的最后一个内部结点）起，至第一个元素止，进行反复筛选。,堆排序的时间复杂度：,1.,对深度为,k,的堆，“筛选”所需进行的关键字比较的次数至多为,2(,k,-1),；,3.,调整“堆顶”,n,-1,次，总共进行的关键字比较的次数不超过,2(,log,2,(,n,-1),+,log,2,(,n,-2),+log,2,2)2,n,(,log,2,n,),因此，堆排序的时间复杂度为,O,(n,log,2,n,),，,与简单选择排序,O,(,n,2,),相比时间效率提高了很多。,2.,对,n,个关键字，建成深度为,h,(=,log,2,n,+1),的堆，,所需进行 的关键字比较的次数至多,4,n,；,堆排序是一种,速度快,且,省空间,的排序方法。,不稳定。,将两