排序算法讲义

1、 排序算法讲义 -柳州高中丁强第一节 排序及其基本概念一、基本概念1什么是排序排序是数据处理中经常使用的一种重要运算。设由n个记录a1，a2，an组成的数据，对这n个记录按关键字大小递增或递减重新排列。简单的说就是将杂乱无章的数据元素，通过一定的方法按关键字顺序重新排列的过程。 2稳定性当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。3排序的方式如果文件中关键字相同的记录经过某种排序方法进行排序之后，仍能保持它们在排序之前的相对次序，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的不稳定的 由于文件大小不同使排序过程中涉及的存储器不同，可将排序分成内部排序和外部排

2、序两类。整个排序过程都在内存进行的排序，称为内部排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。 内排序适用于记录个数不是很多的小文件，而外排序则适用于记录个数太多，不能一次性放人内存的大文件。内排序是排序的基础，目前内存空间都足够应付分区排序数据量。这里主要介绍内部排序算法。 排序算法讲义 -柳州高中丁强第一节 排序及其基本概念补充：排序稳定性分析若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。 假定在待排序的记录序列中，存在多个具有相同键值的记录，若

3、经过排序，这些记录的相对次序保持不变，即在原序列中，ki=kj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。 对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。 例如，对于如下起泡排序算法，如果交换记录条件是rjrj+1则算法是稳定的。如果将记录交换的条件改成rj=rj+1，则两个相等的记录就会交换位置，从而变成不稳定的算法

4、。常见排序算法的稳定性 ：快速排序、希尔排序、堆排序、选择排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法 排序算法讲义 -柳州高中丁强第一节 排序及其基本概念二、排序算法分析1排序算法的基本操作几乎所有的排序都有两个基本的操作：（1）关键字大小的比较。（2）改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录，一般移动记录本身，而链式存储的记录则通过改变指向记录的指针实现重定位。2排序算法性能评价排序的算法很多，不同的算法有不同的优缺点，没有哪种算法在任何情况下都是最好的。评价一种排序算法好坏的标准主要有两条：（1）执行时间和所需的辅助空间，即时间

5、复杂度和空间复杂度；（2）算法本身的复杂程度，比如算法是否易读、是否易于实现。 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：一、冒泡排序1冒泡排序的思想最多进行n-1趟排序，每趟排序时，从底部向上扫描，一旦发现两个相邻的元素不符合规则，则交换。我们发现，第一趟排序后，最小值在A1，第二趟排序后，较小值在A2，.第n-1趟排序完成后，所有元素完全按顺序排列。2排序过程示例待排序数据：53 33 19 53 3 63 82 20 19 39第一趟排序：3 53 33 19 53 19 63 82 20 39第二趟排序：3 19 53 33 19 53 20 63 82 39第三趟排序：3

6、 19 19 53 33 20 53 39 63 82第四趟排序：3 19 19 20 53 33 39 53 63 82第五趟排序：没有反序数据，排序结束。 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：一、冒泡排序3程序代码procedure Bubble(n:integer); var temp,i,j:integer; change:boolean; begin for i:=1 to n-1 do 每趟循环找到一个最小值，进行n-1趟 begin change:=false;循环结束标记，优化 for j:=n-1 downto i do从后向前相邻比较 if ajaj+1

7、then begin change:=true;标记有存在交换情况 temp:=aj; 引用中间变量，交换aj,aj+1值 aj:=aj+1; aj+1:=temp; end; if not(change) then exit;一趟循环无交换，则全体数据有序，即排序结束 end; end; 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：一、冒泡排序4算法分析（1）稳定性：稳定（2）时间复杂度： 原始数据正序，需一趟排序，比较次数n-1=O(n) 原始数据反序，需n-1趟排序，比较次数 一般情况下，虽然不一定需要n-1趟排序，但由于每次数据位置的改变需要3次赋值操作，因此，可以在这里进行

8、一些优化减少交换次数。（3）空间复杂度：仅需一个中间变量，以及一个数组（4）程序实现：简单。)(2) 1()(211nOnninni5改进可以在每趟排序时，记住最后一次发生交换发生的位置，则该位置之前的记录均已有序。下一趟排序扫描到该位置结束。利用这种方式，可以减少一部分比较次数。 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：二、选择排序1选择排序的思想： 每一趟从待排序的数据中选出最小元素，顺序放在已排好序的数据最后，直到全部数据排序完毕。 选择排序过程模拟：待排序数据92286284621656873366第一趟排序16286284629256873366第二趟排序1628628

9、4629256873366第三趟排序16283384629256876266第四趟排序16283356629284876266第五趟排序16283356629284876266第六趟排序16283356626284879266第七趟排序16283356626266879284第八趟排序16283356626266849287第九趟排序16283356626266848792 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：二、选择排序2程序代码procedure select(n:integer); var temp,k,i,j:integer;begin for i:=1 to n-1

10、 do以i为基准进行n-1轮排序 begin k:=i;k:排序交换的位置 for j:=i+1 to n do与j位置以后的数据做比较 if ajak then k:=j;记录当前需要交换的可能位置 if ki then最后的最小数据做交换 begin a0:=ai; ai:=ak; ak:=a0; end; end;end; 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：二、选择排序3算法分析（1）稳定性：不稳定（2）时间复杂度：O(n2)（3）空间复杂度：仅需一个中间单元A0 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：三、插入排序插入排序的思想： 每次将一个待排序的记

11、录，按其关键字大小插入到前面已经排好序的记录集中，使记录依然有序，直到所有待排序记录全部插入完成。 1、直接插入排序基本思想：假设待排序数据存放在数组A1.n中，则A1可看作是一个有序序列，让i从2开始，依次将Ai插入到有序序列A1.i-1中，An插入完毕则整个过程结束，A1.n成为有序序列。排序过程示例 （用【 】表示有序序列）待排序数据：【25】 54 8 54 21 1 97 2 73 15 （n=10）i=2：【25 54】 8 54 21 1 97 2 73 15i=3：【8 25 54】 54 21 1 97 2 73 15i=4：【8 25 54 54】 21 1 97 2 73

12、 15i=5：【8 21 25 54 54】 1 97 2 73 15i=6：【1 8 21 25 54 54】 97 2 73 15i=7：【1 8 21 25 54 54 97】 2 73 15i=8：【1 2 8 21 25 54 54 97】 73 15i=9：【1 2 8 21 25 54 54 73 97】 15i=10：【1 2 8 15 21 25 54 54 73 97】 排序结束 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：三、插入排序直接插入排序算法实现：可在数组中增加元素A0作为关键值存储器和循环控制开关。第i趟排序，即Ai的插入过程为： 保存AiA0 j:=

13、i-1; 如果Aj=A0（即待排序的Ai），则A0Aj+1，完成插入； 否则，将Aj后移一个位置：AjAj+1； ；继续执行 对于上面的数据实例，i从2依次变化到10的过程中， j值分别为1，0，3，1，0，6，1，7，3 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：三、插入排序直接插入排序程序实现：排序结果从大到小procedure insertsort(n:integer); var i,j:integer; begin for i:=2 to n do begin a0:=ai; 数据i的结果预先放入a0中 j:=i-1; while aja0 do 决定运算次数和移动次数 b

14、egin aj+1:=aj; 数据向后退 j:=j-1; 数组下标向前继续找 end; aj+1:=a0; 找到数据i所在的位置，把结果放入 end; end; 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：三、插入排序直接插入排序算法分析：（1）稳定性：稳定（2）时间复杂度： 原始数据正序，总比较次数：n-1 原始数据逆序，总比较次数： 原始数据无序，第i趟平均比较次数= ， 总次数为： 可见，原始数据越趋向正序，比较次数和移动次数越少。（3）空间复杂度：仅需一个辅助单元AO)(22222nOnnini21/1iijij)(4322nOnn 排序算法讲义 -柳州高中丁强第二节 各类排

15、序算法分析：三、插入排序2.希尔排序：基本思想: 任取一个小于n的整数S1作为增量，把所有元素分成S1个组。 所有间距为S1的元素放在同一个组中。 第一组：A1，AS1+1，A2*S1+1， 第二组：A2，AS1+2，A2*S1+2， 第三组：A3，AS1+3，A2*S1+3， 第s1组：AS1，A2*S1，A3*S1，先在各组内进行直接插人排序；然后，取第二个增量S2（S1）重复上述的分组和排序，直至所取的增量St=1（StSt-1St-2S2S1），即所有记录放在同一组中进行直接插入排序为止。 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：三、插入排序 希尔排序过程示例： 从小到大

16、排序待排序数据：1289573296375457957序号12345678910原始数据1289573296375457957S1=5组别排序结果1254532573789577996S2=3组别排序结果1254532573789577996S3=2组别排序结果5321237575479578996S4=1组别排序结果5123237545757798996 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：三、插入排序 希尔排序算法实现： 由于在分组内部使用的是直接插入排序， 因此排序过程只要在直接插入排序的算法上 对j的步长进行修改就可以了 排序算法讲义 -柳州高中丁强第二节 各类排序算

17、法分析：三、插入排序希尔排序算法程序实现：procedure shell(n:integer); var s,k,i,j:integer; begin s:=n; repeat s:=round(s/2); 设置增量设置增量S递减递减 for k:=1 to s do 对对S组数据分别排序组数据分别排序 begin i:=k+s; 第二个待排序数据第二个待排序数据 while in时，本组数据排序结束时，本组数据排序结束 begin a0:=ai; j:=i-s; 约定步长为约定步长为S while (aja0) and (j=k) do begin aj+s:=aj; j:=j-s; end

18、; aj+s:=a0; i:=i+s; end; end; until s=1; end; 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：四、快速排序：目前公认的最快的排序方法目前公认的最快的排序方法1快速排序的思想快速排序的思想快速排序的思想 在在A1.n中任取一个数据元素作为比较的中任取一个数据元素作为比较的“基准基准”（不妨（不妨记为记为X），将数据区划分为左右两个部分：），将数据区划分为左右两个部分：A1.i-1和和Ai+1.n， 且且A1.i-1XAi+1.n(1in)，当，当A1.i-1和和Ai+1.n非非空时，空时， 分别对它们进行上述的划分过程，直至所有数据元素均已分别

19、对它们进行上述的划分过程，直至所有数据元素均已排序为止。排序为止。 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：四、快速排序：目前公认的最快的排序方法目前公认的最快的排序方法2快速排序的算法实现 ：算法实现算法实现 可以使用递归函数实现这一算法。假定待排序序列的下标范围为可以使用递归函数实现这一算法。假定待排序序列的下标范围为lowhigh。 借用两个整型变量借用两个整型变量i、j作为指针，约定初值分别为作为指针，约定初值分别为low、high。排序过程：排序过程： 选定基准选定基准X（不妨用（不妨用Alow） j向前扫描，直到向前扫描，直到AjX，交换，交换Ai与与Aj，j-1。保

20、证了。保证了XAj.high 继续执行继续执行、，直到，直到i=j。这时，。这时，X恰好在恰好在Ai位置上。位置上。 对序列对序列Alow.i-1及及Ai+1.high按照上述规律继续划分，直到序列为空。按照上述规律继续划分，直到序列为空。仔细分析算法，我们发现，在排序中，我们总是用基准仔细分析算法，我们发现，在排序中，我们总是用基准X与另一数据交换，与另一数据交换，因此，一趟排序结束后，因此，一趟排序结束后，X就能确切定位其最终位置。就能确切定位其最终位置。 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：四、快速排序：目前公认的最快的排序方法目前公认的最快的排序方法3快速排序的实例演

21、示 ：排序过程示例排序过程示例待排序数据：待排序数据： 67 67 14 52 29 9 90 54 87 71X=67 i j扫描扫描j i j 交换交换 54 67 14 52 29 9 90 67 87 71扫描扫描i i j 交换交换 54 67 14 52 29 9 67 90 87 71j=i，结束，结束 ij 第一趟排序后：第一趟排序后：54 67 14 52 29 9 67 90 87 71第二趟排序后：第二趟排序后： 9 29 14 52 54 67 67 71 87 90第三趟排序后：第三趟排序后：9 29 14 52 54 67 67 71 87 90第四趟排序后：第四趟

22、排序后：9 14 29 52 54 67 67 71 87 90第五趟排序后：第五趟排序后：9 14 29 52 54 67 67 71 87 90 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：四、快速排序：目前公认的最快的排序方法目前公认的最快的排序方法4快速排序的程序实现 ：procedure quicksort(low,high:integer); 调用时调用时 quicksort(1,n) n:数组最大下标数组最大下标 var temp,x,i,j:integer; begin if lowhigh then begin x:=alow; i:=low; j:=high;x:

23、当前比较的基准当前比较的基准 while ii) and (aj=x) do j:=j-1; j左移左移 temp:=ai; ai:=aj; aj:=temp; while (ji) and (aimid do dec(r); while al=l then需要交换当前不和条件的数需要交换当前不和条件的数ar,al begin temp:=ar; ar:=al; al:=temp; inc(l);dec(r); end; until rl;当前快排结束判断条件当前快排结束判断条件 if ir then qsort(i,r);继续对继续对i.r范围数据进行快排范围数据进行快排 if lj the

24、n qsort(l,j);继续对继续对l.j范围数据进行快排范围数据进行快排 end; 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析：四、快速排序：目前公认的最快的排序方法目前公认的最快的排序方法4快速排序的算法分析 ：算法分析算法分析（1）稳定性：不稳定）稳定性：不稳定（2）时间复杂度：）时间复杂度： 每趟排序所需的比较次数为待排序区间的长度每趟排序所需的比较次数为待排序区间的长度-1，排序趟数越多，占用时间越多。，排序趟数越多，占用时间越多。最坏情况：最坏情况： 每次划分选取的基准恰好都是当前序列中的最小每次划分选取的基准恰好都是当前序列中的最小(或最大或最大)值，值， 划分的结果

25、划分的结果 Alow.i-1为空区间或为空区间或Ai+1.high是空区间，是空区间， 且非空区间长度达到最大值。这种情况下，且非空区间长度达到最大值。这种情况下，必须进行必须进行n-1趟快速排序，第趟快速排序，第i次趟去见长度为次趟去见长度为n-i+1， 总的比较次数达到最大值：总的比较次数达到最大值：n(n-1)/2=O(n2)最好情况：最好情况：每次划分所取的基准都是当前序列中的每次划分所取的基准都是当前序列中的“中值中值”， 划分后的两个新区间长度大致相等。划分后的两个新区间长度大致相等。共需共需lgn趟快速排序，趟快速排序， 总的关键字比较次数：总的关键字比较次数：O(nlgn)基准

26、的选择决定了算法性能。经常采用选取基准的选择决定了算法性能。经常采用选取low和和high之间一个随机位置作为基准的之间一个随机位置作为基准的方式改善性能。方式改善性能。（3）空间复杂度：快速排序在系统内部需要一个栈来实现递归，）空间复杂度：快速排序在系统内部需要一个栈来实现递归， 最坏情况下为最坏情况下为O(n2)，最佳情况下为，最佳情况下为O(n*lgn)。 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序1堆排序思想： 堆排序是一种树形选择排序，在排序过程中，将堆排序是一种树形选择排序，在排序过程中，将A1.n构造成完全二叉树的顺序存储结构，构造成完全二叉树的顺序存储结

27、构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。2堆的定义： l堆是一棵近似满二叉树，它可分为大根堆和小根堆。堆的定义是递归的。堆的定义： n个元素的序列k1,k2,k3,kn当且仅当满足下列关系时候，称之为堆小根堆 ki=k2i ki=k2i ki=k2i+1 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序3堆的样例： 1647895313458769存储结构：小根堆 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序3堆的样例： 9683273811101209存储结

28、构：大根堆 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序4堆的基本操作： 4.1 堆的插入插入操作：在小根堆中插入一个值2。插入后继续保持小根堆的性质164789532 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序4堆的基本操作： 4.1 堆的插入插入操作：在小根堆中插入一个值2。插入后继续保持小根堆的性质164789532 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序4堆的基本操作： 4.1 堆的插入插入操作：在小根堆中插入一个值2。插入后继续保持小根堆的性质164789532 排序算法讲义 -柳州高中丁强第二节 各类排序算法

29、分析： 五：堆排序4堆的基本操作： 4.2 删除堆顶元素的操作：在小根堆中删除堆顶元素后，继续维持小根堆性质。164789532 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序4堆的基本操作： 4.2 删除堆顶元素的操作：在小根堆中删除堆顶元素后，继续维持小根堆性质。64789532 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序4堆的基本操作： 4.2 删除堆顶元素的操作：在小根堆中删除堆顶元素后，继续维持小根堆性质。64789532 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序4堆的基本操作： 4.2 删除堆顶元素的操作：在小根

30、堆中删除堆顶元素后，继续维持小根堆性质。64789532 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序4堆的基本操作： 4.2 删除堆顶元素的操作：在小根堆中删除堆顶元素后，继续维持小根堆性质。64789532 由于堆有一些特殊的性质，所以我们可以用数组来实现堆。 tot保存堆中元素的个数 heapi (1=i1时，heapi的父亲存放在heapi div 2当中 所以任何时刻当堆不为空的时候，堆的最小/大元素始终存放在heap1的位置。 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序5堆的数组实现： 排序算法讲义 -柳州高中丁强第二节 各类排序算法分

31、析： 五：堆排序6堆的插入操作程序： procedure Insert(x:longint);var s:integer;begin inc(tot); heaptot:=x; s:=tot; while (s1)and(heapsheaps div 2) do begin swap(heaps,heaps div 2); s:=s div 2; end;end; 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序8堆的各种操作的时间复杂度分析堆的各种操作的时间复杂度分析： 8.1 由于用数组实现的堆时刻是一棵近似满二叉树，因此插入和删除的操作时间复杂度仅跟这棵二叉树的高度有关

32、系。每次操作的复杂度为o(logN) 8.2 取最小值操作的时间复杂度为o(1). 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序9利用堆得性质排序利用堆得性质排序： 9.1：堆排序主程序 procedure heapsort(n:integer); 大根堆排序 var k,i,j:integer;begin for i:=1 to n do读入n个无序的数 read(ai); for i:=n div 2 downto 1 do 从第 n div 2 个位置元素开始筛选建立堆 sift(i,n); 建立堆 for i:=n downto 2 do把第1 个位置的元素与第

33、i 位置的交换，得出一个满足排序位置的解 begin temp:=a1; a1:=ai; ai:=temp; sift(1,i-1);从新建立堆，让a1 为堆中最小的值 end; for i:=n downto 1 do writeln(ai:0:0, );end; 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： 五：堆排序9利用堆得性质排序利用堆得性质排序： 9.2：维护堆过程 procedure sift(k,m:integer);筛选让ak.am 满足堆的定义： 大根堆 var i,j:integer; t,x:real; finished:boolean; begin i:=k

34、; j:=2*i; x:=ak; finished:=false;标记是否构成了堆 t:=ak;t:暂时记录当前堆顶的数量值 while (j=m) and not finished do begin if (jm) and (aj=aj then finished:=true x=aj 不需要向下再筛选，找到合适的位置来放t else begin ai:=aj;继续在堆中寻找合适的位置 ，把大的值向上移动 i :=j; 继续沿着j 分支寻找合适的插入位置 j:=2*i; end; end; ai:=t;把t插入到满足堆定义的合适的位置ai end; 排序算法讲义 -柳州高中丁强第二节 各类排

35、序算法分析： 五：堆排序10堆排序堆排序算法分析算法分析： （1）稳定性：不稳定。 假定数据序列为1，1，已是大堆，经过排序后，结果为1，1。（2）时间复杂度： 堆排序的时间，主要由建立初始堆和反复调整堆这两部分的时间开销构成，它们均是通过调用sift（）过程实现的。 堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。（3）空间复杂度：O(1)（4）堆排序经典例题 （noip2004提高组试题 合并果子合并果子） 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： l六：归并排序1归并排序算法基本思

36、路归并排序算法基本思路： 设有两个有序（升序）序列存储在同一数组中相邻的位置上，设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为不妨设为Al.m，Am+1.h，将它们归并为一个有序数列，并存，将它们归并为一个有序数列，并存储在储在Al.h。为了减少数据移动次数，不妨采用一个临时工作数组。为了减少数据移动次数，不妨采用一个临时工作数组C，将中间排序结果暂时保存在，将中间排序结果暂时保存在C数组中，等归并结束后，再将数组中，等归并结束后，再将C数组值复制给数组值复制给A。归并过程中，设置。归并过程中，设置p1，p2和和p3三个指针，其初三个指针，其初值分别指向三个有序区的起始位置。归

37、并时依次比较值分别指向三个有序区的起始位置。归并时依次比较Ap1和和Ap2的关键字，取关键字较小的记录复制到的关键字，取关键字较小的记录复制到Cp3中，然后将被复制记中，然后将被复制记录的指针录的指针p1或或p2加加1，以及指向复制位置的指针，以及指向复制位置的指针p3加加1。重复这一。重复这一过程直至有一个已复制完毕，此时将另一序列中剩余数据依次复制过程直至有一个已复制完毕，此时将另一序列中剩余数据依次复制到到C中即可。中即可。 排序算法讲义 -柳州高中丁强第二节 各类排序算法分析： l六：归并排序2归并排序实现方法归并排序实现方法： 分治法的三个步骤：设归并排序的当前区间是Al.h，分治法的三个步骤是：2.1 分解：将当前区间一分为二，即求分裂点m=(l+h)/22.2 求解：递归地对两个子区间Al.