第六章排序与选择2课件

第六章第六章 排序与选择排序与选择本章主要介绍以下内容：本章主要介绍以下内容：6.1、简单排序算法、简单排序算法 6.2、快速排序算法、快速排序算法 6.3、合并排序算法、合并排序算法 6.4、排序算法的应用、排序算法的应用.第六章第六章 排序与选择排序与选择n首先对排序下一个定义：首先对排序下一个定义：n假设含假设含n个记录的序列个记录的序列R为为 R1,R2,Rn其相应其相应的关键字为的关键字为K1,K2,Kn需确定需确定1，2，,n的一的一种排列种排列P1,P2,Pn,使其相应的关键字满足如下的使其相应的关键字满足如下的非递减（或非递增关系）非递减（或非递增关系）Kp1=Kp2=Kpn 即使序列即使序列R成为一个成为一个按关键字有序的序列按关键字有序的序列 Rp1,Rp2,Rpn 这样一种操作称为排序。这样一种操作称为排序。.第六章第六章 排序与选择排序与选择n上述排序定义中的关键字上述排序定义中的关键字Ki可以是记录可以是记录Ri（i=1,2,n)的主关键字，也可以是记录的主关键字，也可以是记录Ri的次关键的次关键字，甚至是若干数据项的组合。若字，甚至是若干数据项的组合。若Ki是主关键字，则是主关键字，则任何一个记录的无序序列经排序后得到的结果是唯任何一个记录的无序序列经排序后得到的结果是唯一的；若一的；若Ki是次关键字，则排序的结果不唯一，因为是次关键字，则排序的结果不唯一，因为待排序的记录序列中可能存在两个或两个以上关键待排序的记录序列中可能存在两个或两个以上关键字相等的记录。假设字相等的记录。假设Ki=Kj(1=i=n,1=j=n,i!=j),且在排列前的序列中且在排列前的序列中Ri领先领先Rj(即即ij).若在排序后的若在排序后的序列中序列中Ri仍领先仍领先Rj，则称所有的，则称所有的排序方法是稳定的；排序方法是稳定的；反之，若可能使排序后的序列中反之，若可能使排序后的序列中Rj领先领先Ri，则称所用，则称所用的的排序方法是不稳定的。排序方法是不稳定的。.第六章第六章 排序与选择排序与选择n为了查找方便，通常希望计算机中的表是按关键为了查找方便，通常希望计算机中的表是按关键字有序的。因为有序的顺序表可以采用查找效率字有序的。因为有序的顺序表可以采用查找效率较高的折半查找法，其平均查找长度为较高的折半查找法，其平均查找长度为log2(n+1)-1,而无序的顺序表只能进行顺序查找而无序的顺序表只能进行顺序查找其平均查找长度为其平均查找长度为(n+1)/2，如建造树表（无论如建造树表（无论是排序二叉树或是排序二叉树或B-树）的过程本身就是一个排序树）的过程本身就是一个排序的过程。因此学习和研究排序方法是计算机工作的过程。因此学习和研究排序方法是计算机工作者的重要课题之一。者的重要课题之一。.第六章第六章 排序与选择排序与选择n由于待排序的记录数量不同，使得排序过由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分程中涉及的存储器不同，可将排序方法分为两大类：一类是为两大类：一类是内部排序内部排序，指的是待排，指的是待排序记录存放在计算机随机存储器中进行的序记录存放在计算机随机存储器中进行的排序过程；另一类是排序过程；另一类是外部排序外部排序，指的是待，指的是待排序记录的数量很大，以致内存一次不能排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外村容纳全部记录，在排序过程中尚需对外村进行访问的排序过程。进行访问的排序过程。.第六章第六章 排序与选择排序与选择n6.1、简单排序算法、简单排序算法n1 1、排序问题：输入、排序问题：输入n n个数个数a0a0、a1a1、a2 a2 an-1an-1的一个序列，要设计一个有效的排序算法，产生输的一个序列，要设计一个有效的排序算法，产生输入序列的一个重排，使序列元素按从小到大的顺序排列。入序列的一个重排，使序列元素按从小到大的顺序排列。n2 2、输入序列，通常是一个有、输入序列，通常是一个有n n个元素的数组，当然也可以个元素的数组，当然也可以用其他形式来表示输入，如链表等。用其他形式来表示输入，如链表等。n3 3、在实际中，待排序的对象往往不是一个单一的数，而、在实际中，待排序的对象往往不是一个单一的数，而是一个记录，其中有一个关键字域是一个记录，其中有一个关键字域keykey，它是排序的根据。它是排序的根据。.第六章第六章 排序与选择排序与选择 n4 4、排序：是把一组无序地数据元素按照关键字值递增排序：是把一组无序地数据元素按照关键字值递增（或递减）地重新排列。如果排序依据的是主关键字，排（或递减）地重新排列。如果排序依据的是主关键字，排序的结果将是唯一的。序的结果将是唯一的。n5 5、排序的基本方法排序的基本方法 ：简单排序主要有：冒泡排序、插简单排序主要有：冒泡排序、插入排序、选择排序。入排序、选择排序。n6 6、计算时间分析：、计算时间分析：通常以排序过程所需要的算法步数作为度量，有时通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所做的键值比较次数作为度量。也以排序过程中所做的键值比较次数作为度量。.第六章第六章 排序与选择排序与选择n6.1.1 冒泡排序冒泡排序n基本思想基本思想:从第一个记录从第一个记录RnRn开始，对每两个相邻的开始，对每两个相邻的两个关键字两个关键字K Ki i和和K Ki+1i+1进行比较，若进行比较，若KiKiKi+1Ki+1，则交，则交换换RiRi和和Ri+1Ri+1的位置。使关键字较小的记录换至关的位置。使关键字较小的记录换至关键字较大的记录之前，使得经过一趟冒泡排序后，键字较大的记录之前，使得经过一趟冒泡排序后，关键最小的记录达到最前端，接着，再在剩下的关键最小的记录达到最前端，接着，再在剩下的记录中找出关键字次小的记录，并把它换至第二记录中找出关键字次小的记录，并把它换至第二个位置上。依次类推，一直到所有记录都有序。个位置上。依次类推，一直到所有记录都有序。.第六章第六章 排序与选择排序与选择n冒泡排序的算法如下：冒泡排序的算法如下：n Void BubbleSort(RecType R,int n)n int i,j;n RecType temp;n for(i=0;ii;j-)n if(Rj.keyRj-1.key)n temp=Rj;n Rj=Rj-1;n Rj-1=temp;n n.n 改进的冒泡排序算法n 在冒泡排序过程中，一旦发现某一趟没有进行交换操作，就表明此时待排序记录序列已经成为有序序列，冒泡排序再进行下去已经没有必要，应立即结束排序过程。.n进一步地改进冒泡排序算法进一步地改进冒泡排序算法n在给出的冒泡排序算法的基础上，如果我们同时记录第在给出的冒泡排序算法的基础上，如果我们同时记录第i趟趟冒泡排序中最后一次发生交换操作的位置冒泡排序中最后一次发生交换操作的位置m（m=n-i），），就会发现从此位置以后的记录均已经有序，即无序区范围就会发现从此位置以后的记录均已经有序，即无序区范围缩小在缩小在a1am之间，所以在进行下一趟排序操作时，之间，所以在进行下一趟排序操作时，就不必考虑就不必考虑am+1an范围内的记录了，而只在范围内的记录了，而只在a1am范围内进行。范围内进行。.冒泡排序小结冒泡排序小结1 1、冒泡排序比较简单，当初始序列基本有序时，冒泡排、冒泡排序比较简单，当初始序列基本有序时，冒泡排 序有较高的效率，反之效率较低；其次冒泡排序只需序有较高的效率，反之效率较低；其次冒泡排序只需要一个记录的辅助空间，用来作为记录交换的中间暂要一个记录的辅助空间，用来作为记录交换的中间暂存单元；存单元；2 2、冒泡排序是一种稳定的排序方法。、冒泡排序是一种稳定的排序方法。.n6 6.1.1.2 2 插入排序插入排序n基本思想基本思想:依次将记录序列中的每一个记录插入到依次将记录序列中的每一个记录插入到有序段中，使有序段的长度不断地扩大。有序段中，使有序段的长度不断地扩大。n其具体的排序过程可以描述如下：其具体的排序过程可以描述如下：首先将待排序记录序列中的第一个记录作为一首先将待排序记录序列中的第一个记录作为一个有序段，将记录序列中的第二个记录插入到上述个有序段，将记录序列中的第二个记录插入到上述有序段中，形成由两个记录组成的有序段，再将记有序段中，形成由两个记录组成的有序段，再将记录序列中的第三个记录插入到这个有序段中，形成录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的有序段，由三个记录组成的有序段，依此类推，每一趟都依此类推，每一趟都是将一个记录插入到前面的有序段中。是将一个记录插入到前面的有序段中。.n直接插入排序算法：直接插入排序算法：假设待排序的记录存放在数组假设待排序的记录存放在数组R0.n-1R0.n-1中，中，排序过程的某一中间时刻，排序过程的某一中间时刻，R R被划分成两个子区间，被划分成两个子区间，R0.i-1R0.i-1和和R0.n-1R0.n-1。其中：前一个子区间是已。其中：前一个子区间是已排好序的有序区；后一个子区间则是当前未排序的排好序的有序区；后一个子区间则是当前未排序的部分，不妨称其为无序区。直接插入排序的基本操部分，不妨称其为无序区。直接插入排序的基本操作时将当前无序区的第作时将当前无序区的第1 1个记录个记录RiRi插入到有序区插入到有序区R0.i-1R0.i-1中适当的位置上，使中适当的位置上，使R0.iR0.i变为新的有变为新的有序区。这种方法通常称为增量法，因为它每次使有序区。这种方法通常称为增量法，因为它每次使有区增加区增加1 1 个记录。个记录。.n插入排序函数插入排序函数insert(a,l,i):n void insertSort(RecType R,int n)n int i,j;n RecType temp;n for(i=1;i=0&temp.keyRj.key)n Rj+1=Rj;/将关键字大于将关键字大于Ri.Key的记录后移的记录后移n j-;n n Rj+1=temp;/在在j+1处插入处插入temp；n nn .n直接插入排序算法简单、容易实现，只需要一个记录大小直接插入排序算法简单、容易实现，只需要一个记录大小的辅助空间用于存放待插入的记录（在的辅助空间用于存放待插入的记录（在C C语言中，我们利语言中，我们利用了数组中的用了数组中的0 0单元）和两个单元）和两个intint型变量。当待排序记录较型变量。当待排序记录较少时，排序速度较快。少时，排序速度较快。n但是，当待排序的记录数量较大时，大量的比较和移动操但是，当待排序的记录数量较大时，大量的比较和移动操作将使直接插入排序算法的效率降低；然而，当待排序的作将使直接插入排序算法的效率降低；然而，当待排序的数据元素基本有序时，直接插入排序过程中的移动次数大数据元素基本有序时，直接插入排序过程中的移动次数大大减少，从而效率会有所提高。大减少，从而效率会有所提高。n 插入排序是一种稳定的排序方法。插入排序是一种稳定的排序方法。.n6.1.3 6.1.3 选择排序选择排序n基本思想：在排序过程序中，依次从待排序的记基本思想：在排序过程序中，依次从待排序的记录序列中选择出关键字值最小的记录、关键字值录序列中选择出关键字值最小的记录、关键字值次小的记录、次小的记录、，并分别将它们定位到序列左，并分别将它们定位到序列左侧的第侧的第1 1个位置、第二个位置、个位置、第二个位置、，最后剩下一，最后剩下一个关键字值最大的记录位于序列的最后一个位置，个关键字值最大的记录位于序列的最后一个位置，从而使待排序的记录序列成为按关键字值由小到从而使待排序的记录序列成为按关键字值由小到大排列的的有序序列。大排列的的有序序列。.n1.1.简单选择排序的基本思想简单选择排序的基本思想n 简单选择排序的基本思想是：每一趟在简单选择排序的基本思想是：每一趟在n-i+1(i=1,2,3,.,n-1)个记录中选取关键字最小的记录作个记录中选取关键字最小的记录作为有序序列中的第为有序序列中的第i i个记录。个记录。n假设对待排序的元素序列假设对待排序的元素序列a l a r 进行进行r-1r-1遍处理，遍处理，第第i i遍处理是将遍处理是将a l+i-1,a r 中的最小者与中的最小者与a l+i-1 交换位置。这样，经过交换位置。这样，经过i i遍处理之后，较小的遍处理之后，较小的i i个个元素的位置已经是确定的了。元素的位置已经是确定的了。.n算法实现：算法实现：nVoid SelectSort(Rectype R,int n)n int i,j,k;n RecType temp;n for(i=0;in-1;i+)/做第做第i 趟排序；趟排序；n k=i；n for(j=i+1;jn;j+)/在当前无序区在当前无序区Ri.n-1中选最中选最小的记录小的记录n if(Rj.keyRk.key)n k=j;/k记下目前找到的最小关键字所在的位置记下目前找到的最小关键字所在的位置n if(k!=i)n temp=Ri;Ri=Rk;Rk=temp;n n .简单选择排序算法小结简单选择排序算法小结n简单选择排序算法简单，但是速度较慢，并且是一种不稳简单选择排序算法简单，但是速度较慢，并且是一种不稳定的排序方法定的排序方法.，但在排序过程中只需要一个用来交换记，但在排序过程中只需要一个用来交换记录的暂存单元。录的暂存单元。.6.1.4 简单排序算法的计算复杂性简单排序算法的计算复杂性n1、冒泡排序：由于、冒泡排序：由于compswap运算需要运算需要o(1)计算时间，因此，冒泡排序算法的循环计算时间，因此，冒泡排序算法的循环体耗时体耗时o(1)，由此可知整个算法所需的时间，由此可知整个算法所需的时间为：为：o(1)=o()=o(n2)最坏情况最坏情况,输入元素序列完全逆序。输入元素序列完全逆序。最好情况，输入元素序列完全排好序。最好情况，输入元素序列完全排好序。N i-2i=2 j=0 1i=2 j=0N-1 i.6.1.4 简单排序算法的计算复杂性简单排序算法的计算复杂性n2、插入排序：、插入排序：最坏情况最坏情况,输入元素序列完全逆序，对任意输入元素序列完全逆序，对任意一个位置一个位置i元素需要做元素需要做i次的比较和交换，因次的比较和交换，因此，插入排序需要此，插入排序需要o(n2).最好情况，输入元素序列完全排好序最好情况，输入元素序列完全排好序,还是要还是要有有n(n-1)/2次的比较。次的比较。.6.1.4 简单排序算法的计算复杂性简单排序算法的计算复杂性n3、选择排序：、选择排序：整个算法需要的计算时间为：整个算法需要的计算时间为：O（n2）对任何输入序列，选择算法总要执行对任何输入序列，选择算法总要执行 n(n-1)/2次元素的比较，所以选择排序算法次元素的比较，所以选择排序算法至少需要至少需要（n2）。）。.n快速排序又称为分区交换排序。快速排序又称为分区交换排序。n其基本思想是：其基本思想是：n 首先将待排序记录序列中的所有记录作为当前首先将待排序记录序列中的所有记录作为当前待排序区域，从中任选取一个记录（比如，第一待排序区域，从中任选取一个记录（比如，第一个记录），并以该记录的关键字值为个记录），并以该记录的关键字值为基准基准，从位，从位于待排序记录序列左右两端开始，逐渐向中间靠于待排序记录序列左右两端开始，逐渐向中间靠拢，交替与基准记录的关键字进行拢，交替与基准记录的关键字进行比较、交换比较、交换，6.2 快速排序算法快速排序算法.n每次比较，若遇每次比较，若遇左侧左侧记录的关键字值记录的关键字值大于大于基准记基准记录的关键字，则将其录的关键字，则将其与基准记录交换与基准记录交换，使其移到，使其移到基准记录的右侧，若遇基准记录的右侧，若遇右侧右侧记录的关键字值记录的关键字值小于小于基准值，则将其与基准记录交换，使其移至基准基准值，则将其与基准记录交换，使其移至基准记录的左侧，最后让基准记录到达它的最终位置，记录的左侧，最后让基准记录到达它的最终位置，此时，基准记录将待排序记录分成了左右两个区此时，基准记录将待排序记录分成了左右两个区域，位于基准记录域，位于基准记录左侧左侧的记录都的记录都小于或等于小于或等于基准基准记录的记录的关键字关键字，位于基准记录，位于基准记录右侧右侧的所有记录的的所有记录的关键字都关键字都大于或等于大于或等于基准记录的基准记录的关键字关键字，这就是，这就是一趟快速排序；一趟快速排序；.n然后分别对左右两个然后分别对左右两个新新的待排序区域，重复上述的待排序区域，重复上述一趟快速排序的过程，其结果分别让左右两个区一趟快速排序的过程，其结果分别让左右两个区域中的基准记录都到达它们的最终位置，同时将域中的基准记录都到达它们的最终位置，同时将待排序记录序列分成更小的待排序区域，再次重待排序记录序列分成更小的待排序区域，再次重复对每个区域进行一趟快速排序，直到每个区域复对每个区域进行一趟快速排序，直到每个区域只有一个记录只有一个记录为止，此时所有的记录都到达了它为止，此时所有的记录都到达了它的最终位置，即整个待排序记录按关键值有序排的最终位置，即整个待排序记录按关键值有序排列，至此排序结束。列，至此排序结束。n快速排序是一个快速排序是一个递归递归的过程，只要能够实现一趟的过程，只要能够实现一趟快速排序的算法，就可以利用递归的方法对一趟快速排序的算法，就可以利用递归的方法对一趟快速排序后的左右分区域分别进行快速排序。快速排序后的左右分区域分别进行快速排序。.6.2 快速排序算法快速排序算法n在平均情况下，需要在平均情况下，需要O(nlogn)时间。时间。n1、基本思想：基于分治策略、基本思想：基于分治策略,对于输入的子数组对于输入的子数组al:r,按以下按以下3个步骤进行排序个步骤进行排序:n分解分解:以以 ar为基准元素将为基准元素将al:r划分成划分成3段段,al:i-1、ai和和ai+1:r,使使al:i-1 中任何元素都小中任何元素都小于等于于等于ai，ai+1:r中任何元素都大于等于中任何元素都大于等于ai。下标下标i在划分过程中确定。在划分过程中确定。n递归求解：通过递归调用快速排序算法分别对递归求解：通过递归调用快速排序算法分别对al:i-1和和ai+1:r进行排序。进行排序。n合并：合并：al:i-1和和ai+1:r都已排好序后，不需要都已排好序后，不需要执行任何计算，执行任何计算，a1:r就已排好序。就已排好序。.6.2.1 快速排序算法快速排序算法n int partition(SqList L,int low,int high)n n L.r0=L.rlow;/用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录n pivotkey=L.rlow.key;枢轴记录关键字枢轴记录关键字n while(lowhigh)n while(low=pivotkey）-high;n L.rrow=L.rhigh;/记录小的移到低端记录小的移到低端 n while(lowhigh&L.rlow.key=pivotkey)+low;n L.rhigh=L.rlow;/记录大的移到高端记录大的移到高端 n n L.rlow=L.r0;/枢轴记录到位；枢轴记录到位；n return low;n .6.2.1 快速排序算法快速排序算法n void quicksort(SqList L,int low,int high)n n if(lowhigh)n pivotloc=partition(L,low,high);n quicksort(L,low,pivotloc-1);/*对左半段排对左半段排序序*/n quicksort(L,pivotloc+1,high);/*对右半段对右半段排序排序*/n n .n快速排序实质上是对快速排序实质上是对冒泡冒泡排序的一种改进，排序的一种改进，它的效率与冒泡排序相比有很大地提高。它的效率与冒泡排序相比有很大地提高。n在冒泡排序过程中是对相邻两个记录进行在冒泡排序过程中是对相邻两个记录进行关键字比较和互换的，这样关键字比较和互换的，这样每次交换记录每次交换记录后，只能改变一对逆序记录后，只能改变一对逆序记录，而快速排序，而快速排序则则从待排序记录的两端开始进行比较和交从待排序记录的两端开始进行比较和交换换，并逐渐向中间靠拢，并逐渐向中间靠拢，每经过一次交换，每经过一次交换，有可能改变几对逆序记录有可能改变几对逆序记录，从而加快了排，从而加快了排序速度。序速度。.n到目前为止，快速排序是到目前为止，快速排序是平均速度最大平均速度最大的的一种排序方法，但当原始记录排列基本有一种排序方法，但当原始记录排列基本有序或基本逆序时，每一趟的基准记录有可序或基本逆序时，每一趟的基准记录有可能只将其余记录分成一部分，这样就降低能只将其余记录分成一部分，这样就降低了时间效率，所以快速排序适用于了时间效率，所以快速排序适用于原始记原始记录排列杂乱无章录排列杂乱无章的情况。的情况。n快速排序是一种快速排序是一种不稳定不稳定的排序，在递归调的排序，在递归调用时需要占据一定的存储空间用来保存每用时需要占据一定的存储空间用来保存每一层递归调用时的必要信息。一层递归调用时的必要信息。.6.2.2 算法的性能算法的性能n对于输入序列对于输入序列al：r，partition的计算时间显然为的计算时间显然为o(r-l-1)。n最坏情况：划分的区域分别包含最坏情况：划分的区域分别包含n-1个元素和个元素和1个个元素。元素。n o(1)n1;n 解此递归方程可得解此递归方程可得T（n）=o(n2).6.2.2 算法的性能算法的性能n最好情况：每次划分产生的最好情况：每次划分产生的2个区域都包含个区域都包含n/2个个元素。元素。n o(1)n1;n 解此递归方程可得解此递归方程可得T（n）=o(nlogn).n因此，快速排序算法在平均情况下的时间复杂性因此，快速排序算法在平均情况下的时间复杂性也是也是o(nlogn)，这是基于比较的排序算法中最快的。，这是基于比较的排序算法中最快的。.6.3 合并排序算法合并排序算法n合并排序也称为合并排序也称为归并归并排序，是一种另一类排序方排序，是一种另一类排序方法。法。n所谓归并是指将两个或两个以上的所谓归并是指将两个或两个以上的有序表有序表合并成合并成一个新的有序表。一个新的有序表。n基本思想基本思想:用用分治策略分治策略实现对实现对N N个元素进行排序的算法。个元素进行排序的算法。将将待排序集合一分为二，然后再对两个子集一分为待排序集合一分为二，然后再对两个子集一分为二二,不断下去不断下去,直至待排序集合只剩下个元素为直至待排序集合只剩下个元素为止，然后不断合并个排好序的数组段止，然后不断合并个排好序的数组段。.n一、一、分解分解：将：将N N个待排序元素分成大小大致相同的个待排序元素分成大小大致相同的2 2个子集个子集,再将每个子集分成再将每个子集分成2 2个大小大致相同的子个大小大致相同的子集，这样继续下去，直到集，这样继续下去，直到n=1n=1时（每个子集只有一时（每个子集只有一个元素时）终止分解。（个元素时）终止分解。（递归递归）n二、二、合并合并：是将：是将n n个长度为个长度为1 1的有序列，进行两两的有序列，进行两两归并，得到归并，得到n/2 n/2 个长度为个长度为2 2的有序序列，再进的有序序列，再进行两两归并，得到行两两归并，得到n/4 n/4 个长度为个长度为4 4的有序序列，的有序序列，如此重复，直至得到一个长度为如此重复，直至得到一个长度为n n的有序序列为止。的有序序列为止。.n合并算法可递归的描述如下：合并算法可递归的描述如下：n void mergesort(Item a ,int l,int r)n n int m=(r+l)/2;/*取中点取中点*/n if(r=l)return;n mergesort(a,l,m);/*对左半段排序对左半段排序*/n mergesort(a,m+l,r);/*对右半段排序对右半段排序*/n mergeab(a,b,l,m,r);/*合并到数组合并到数组 b*/n copy(b,a,l,r);/*复制回数组复制回数组 a*/n .n 算法算法mergeab合并合并2个排好序的数组段到一个新个排好序的数组段到一个新的数组的数组b中，然后由中，然后由copy将合并后的数组段再复将合并后的数组段再复制回数组中。制回数组中。n void mergeab(Item a,Item b,int l,int m,int r)n n int i=l,j=m+1,k=l;n while(i=m)&(jm)for(i=j;i=r;i+)b k+=a i;n else for(;i=m;i+)b k+=a i;n .nMergeab 和和 copy可以在可以在(n)时间内完成，时间内完成，因此合并排序算法对因此合并排序算法对n个元素进行排序，在个元素进行排序，在最坏的情况下所需的计算时间最坏的情况下所需的计算时间(n)满足满足n O(1)n1n 可知可知(n)=O(nlogn)n合并排序算法是一个合并排序算法是一个渐进最优渐进最优算法。算法。.6.3.3 自底向上的合并排序算法自底向上的合并排序算法n通常的合并算法指的就是通常的合并算法指的就是自底向上自底向上的合并的合并排序算法。排序算法。n基本思想（消除递归过程）基本思想（消除递归过程）n 首先将数组首先将数组a a中相邻元素两两配对，用中相邻元素两两配对，用合并算法将他们排序，构成合并算法将他们排序，构成n n组长度为组长度为的排好序的子数组段，然后再将他们排的排好序的子数组段，然后再将他们排序成长度为的排好序的子数组段。如此序成长度为的排好序的子数组段。如此下去，直至整个数组排好序。下去，直至整个数组排好序。.n消去递归后的自底向上合并排序算法可描述如下：消去递归后的自底向上合并排序算法可描述如下：n void mergesortBU(Item a ,int l,int r)n n int i,m;n for(m=1;mr-l;m=m+m)n for(i=l;ir-m;i+=m+m)n merge(a,i,i+m-l,mini(i+m+m-l,r);n .n2-2-路归并排序的递归算法从程序的书写形路归并排序的递归算法从程序的书写形式上看比较简单，但是在算法执行时，需式上看比较简单，但是在算法执行时，需要占用较多的辅助存储空间，即除了在递要占用较多的辅助存储空间，即除了在递归调用时需要保存一些必要的信息，在归归调用时需要保存一些必要的信息，在归并过程中还需要与存放原始记录序列同样并过程中还需要与存放原始记录序列同样数量的存储空间，以便存放归并结果，但数量的存储空间，以便存放归并结果，但与快速排序及堆排序相比，它是一种与快速排序及堆排序相比，它是一种稳定稳定的排序方法。的排序方法。.6.3.4自然合并排序自然合并排序n自然合并排序是自底向上合并排序算法的一个变自然合并排序是自底向上合并排序算法的一个变形。形。n对于初始给定的数组对于初始给定的数组a a，通常存在多个长度大于，通常存在多个长度大于1 1的已自然排好序的子数组段。的已自然排好序的子数组段。n用用1 1次对数组次对数组a a的线性扫描就足以找出所有已排好的线性扫描就足以找出所有已排好序的子数组段。序的子数组段。n然后合并相邻排好序的子数组段，直到整个数组然后合并相邻排好序的子数组段，直到整个数组已排好序。已排好序。n通常情况，按此方式进行合并排序所需的合并次通常情况，按此方式进行合并排序所需的合并次数少。数少。.排序算法的性能比较：排序算法的性能比较：排序方法排序方法 时间复杂度时间复杂度稳定性稳定性复杂性复杂性平均平均情况情况最坏最坏情况情况最好最好情况情况 冒泡冒泡O(n2)O(n2)O(n2)稳定稳定简单简单 选择选择O(n2)O(n2)O(n2)不稳定不稳定简单简单 插入插入O(n2)O(n2)O(n)稳定稳定简单简单 快速快速O(nlogn)O(n2)O(nlogn)不稳定不稳定复杂复杂 合并合并O(nlogn)O(nlogn)O(nlogn)稳定稳定复杂复杂.补充：补充：一、堆排序n1.堆排序的基本思想n 堆排序是另一种基于选择的排序方法。下面先介绍一下什么是堆？然后再介绍如何利用堆进行排序。n 堆定义：由n个元素组成的序列k1，k2，kn-1，kn，当且仅当满足如下关系时，称之为堆。.n若将堆看成是一棵以若将堆看成是一棵以k k1 1为根的为根的完全二叉树完全二叉树，则这棵完全二，则这棵完全二叉树中的每个非终端结点的值均不大于（或不小于）其左、叉树中的每个非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此可以看出，若一棵完全二叉树是堆，右孩子结点的值。由此可以看出，若一棵完全二叉树是堆，则根结点一定是这则根结点一定是这n n个结点中的最小者或最大者。下面给个结点中的最小者或最大者。下面给出两个堆的示例。出两个堆的示例。n例例如如序序列列（47，35，27，26，18，7，13，19）满足：满足：.n图 6-1.n下面我们讨论一下如何利用堆进行排序？下面我们讨论一下如何利用堆进行排序？n 从堆的定义可以看出，若将堆用一棵完全二叉树表示，从堆的定义可以看出，若将堆用一棵完全二叉树表示，则根结点是当前堆中所有结点的最小者（或最大者）。则根结点是当前堆中所有结点的最小者（或最大者）。n堆排序的基本思想是：堆排序的基本思想是：n首先将待排序的记录序列构造一个堆，此时，选出了堆中首先将待排序的记录序列构造一个堆，此时，选出了堆中所有记录的最小者或最大者，然后将它从堆中移走，并将所有记录的最小者或最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小（或次大）的剩余的记录再调整成堆，这样又找出了次小（或次大）的记录，以此类推，直到堆中只有一个记录为止，每个记录记录，以此类推，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列。出堆的顺序就是一个有序序列。.n堆排序的关键是堆排序的关键是构造堆构造堆，这里采用，这里采用筛选算法筛选算法建堆：建堆：先把待排序序列按完全二叉树的顺序存储方式排先把待排序序列按完全二叉树的顺序存储方式排列，假若完全二叉树的某一个结点列，假若完全二叉树的某一个结点i i的值和左右子的值和左右子树的值做比较，若结点的值比较小，则和左右子树的值做比较，若结点的值比较小，则和左右子树中的最大者交换，这有可能破坏下一级的堆。树中的最大者交换，这有可能破坏下一级的堆。于是继续采用上述方法构造下一级的堆。直到完于是继续采用上述方法构造下一级的堆。直到完全二叉树中结点全二叉树中结点i i构成堆为止。对于任意完全二叉构成堆为止。对于任意完全二叉树，反复利用上述思想建堆。大者树，反复利用上述思想建堆。大者“上浮上浮”，小，小者者“被筛选下去被筛选下去”。n例：已知序列例：已知序列503，87，512，61，908，170，897，275，653，462，采用堆排序进行降序排列，采用堆排序进行降序排列。.n在堆排序中，除建初堆以外，其余调整堆的过程最多需要在堆排序中，除建初堆以外，其余调整堆的过程最多需要比较树深次，因此，与简单选择排序相比时间效率提高了比较树深次，因此，与简单选择排序相比时间效率提高了很多；另外，不管原始记录如何排列，堆排序的比较次数很多；另外，不管原始记录如何排列，堆排序的比较次数变化不大，所以说，堆排序对原始记录的排列状态并不敏变化不大，所以说，堆排序对原始记录的排列状态并不敏感，约为感，约为log2n。n在堆排序算法中只需要一个暂存被筛选记录内容的单元和在堆排序算法中只需要一个暂存被筛选记录内容的单元和两个简单变量两个简单变量h h和和i i，所以堆排序是一种速度快且省空间的，所以堆排序是一种速度快且省空间的排序方法。堆排序是一种不稳定的。排序方法。堆排序是一种不稳定的。.