数据结构简明教程（第3版）课件 第9章排序(上)

第9章排序9.1排序的基本概念9.2插入排序9.3交换排序9.4选择排序9.5归并排序9.6基数排序9.7外排序第9章

排序1/86所谓排序，是要整理表中的元素，使之按关键字递增（递减）有序排列。其确切定义如下：

输入：n个元素，R0,R1,…,Rn-1,其相应的关键字分别为k0,k1,…,kn-1。

输出：Ri,0,Ri,1,…,Ri,n-1,使得ki,0≤ki,1≤…≤ki,n-1(或ki,0≥ki,1≥…≥ki,n-1)。本章仅考虑递增排序9.1排序的基本概念1.什么是排序9.1排序的基本概念2/86在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序。若排序过程中要进行数据的内、外存交换，则称之为外排序。2.内排序和外排序9.1排序的基本概念3/863.内排序的分类根据内排序算法是否基于关键字的比较，将内排序算法分为基于比较的排序算法和不基于比较的排序算法。像插入排序、交换排序、选择排序和归并排序都是基于比较的排序算法。而基数排序是不基于比较的排序算法。9.1排序的基本概念4/864.基于比较的排序算法的性能基于比较的排序算法中，主要进行以下两种基本操作：这类排序算法的性能由算法的时间和空间确定的，而时间是由比较和移动的次数之和确定的，两个元素的一次交换一般需要3次移动。比较：关键字之间的比较移动：元素从一个位置移动到另一个位置9.1排序的基本概念5/86若待排序元素的关键字顺序正好和要排序顺序相同，称此表中元素为正序。若待排序元素的关键字顺序正好和要排序顺序相反，称此表中元素为反序。基于比较的排序算法中有些算法是与初始序列的正序或反序相关，有些算法与初始序列的正序和反序无关。9.1排序的基本概念6/86当待排序元素的关键字均不相同时，排序的结果是唯一，否则排序的结果不一定唯一。

如果待排序的表中，存在有多个关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，称这种排序方法是稳定的；反之，若具有相同关键字的元素之间的相对次序发生变化，则称这种排序方法是不稳定的。5.算法的稳定性9.1排序的基本概念7/86在本章中，以顺序表作为排序数据的存储结构（除基数排序采用单链表和外排序之外）。为简单起见，假设关键字类型为int类型。待排序的顺序表中元素类型定义如下：typedefintKeyType;typedefstruct{KeyTypekey; //存放关键字,KeyType为关键字类型

ElemTypedata; //其他数据,ElemType为其他数据的类型}SqType;6.排序数据的组织9.1排序的基本概念8/869.2插入排序插入排序基本思路：每一趟将一个待排序的元素，按其关键字值的大小插入到已经排序的部分文件中适当位置上，直到全部插入完成。主要的插入排序算法：直接插入排序、折半插入排序和希尔排序。9.2插入排序9/869.2.1直接插入排序直接插入排序是一种最简单的排序方法，其过程是依次将每个元素插入到一个有序的序列中去。

有序区R[0]

……

R[i-1]无序区R[i]

……

R[n-1]有序区R[0]……

R[i-1]

R[i]无序区R[i+1]

……

R[n-1]一趟排序初始时，有序区只有一个元素R[0]i＝1~n-1，共经过n-1趟排序9.2插入排序10/86

【例9.1】已知有10个待排序的元素，它们的关键字序列为(75,87,68,92,88,61,77,96,80,72)，给出用直接插入排序法进行排序的过程。初始序列75876892886177968072i=175876892886177968072i=268758792886177968072i=368758792886177968072i=468758788926177968072i=561687587889277968072i=661687577878892968072i=761687577878892968072i=861687577808788929672i=961687275778087889296最终结果616872757780878892969.2插入排序i=1的行表示i=1这一趟的排序结果11/86以i=6即插入77为例说明一趟的过程：616875878892770123456有序区tmp…i=5的排序结果：i=6的排序结果12/86直接插入排序算法如下：voidInsertSort(SqTypeR[],intn) {inti,j;SqTypetmp;

for(i=1;i<n;i++)

//从第二个元素即R[1]开始的

{if(R[i-1].key>R[i].key)

{tmp=R[i];

//取出无序区的第一个元素R[i]

j=i-1; //在R[0..i-1]中找R[i]的插入位置

do

{R[j+1]=R[j]; //将关键字大于tmp.key的元素后移

j--; //继续向前比较

}while(j>=0&&R[j].key>tmp.key);

R[j+1]=tmp;

//在j+1处插入R[i]

}

}}9.2插入排序13/86直接插入排序算法分析：最好的情况（关键字在元素序列中顺序有序）：“比较”的次数：0“移动”的次数：最坏的情况（关键字在元素序列中逆序有序）：“比较”的次数：“移动”的次数：总的平均比较和移动次数约为9.2插入排序14/86归纳起来，直接插入排序算法的性能如表9.1所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况O(n)O(n2)O(n2)O(1)稳定9.2插入排序15/869.2.2折半插入排序利用有序区的有序性。可以采用折半查找方法先在R[0..i-1]中找到插入位置，再通过移动元素进行插入。这样的插入排序称为折半插入排序或二分插入排序。9.2插入排序16/86折半插入排序的算法如下：voidBinInsertSort(SqTypeR[],intn){inti,j,low,high,mid;SqTypetmp;

for(i=1;i<n;i++)

{if(R[i-1].key>R[i].key)

{tmp=R[i]; //将R[i]保存到tmp中

low=0;high=i-1;

while(low<=high)

//在R[low..high]中折半查找

{mid=(low+high)/2;//取中间位置

if(tmp.key<R[mid].key)

high=mid-1;

//插入点在左半区

else

low=mid+1;

//插入点在右半区

}

for(j=i-1;j>=high+1;j--) //元素后移

R[j+1]=R[j];

R[high+1]=tmp;

//插入原来的R[i]

}

}}9.2插入排序17/86折半插入排序的元素移动次数与直接插入排序相同，不同的仅是变分散移动为集中移动。在R[0..i-1]中查找插入R[i]的位置，折半查找的平均关键字比较次数为log2(i+1)，平均移动元素的次数为i/2+2，所以平均时间复杂度为：就平均性能而言，折半查找优于顺序查找，所以折半插入排序也优于直接插入排序。9.2插入排序18/86希尔排序基本思路：先取定一个小于n的整数d1作为第一个增量，把表的全部元素分成d1个组，所有距离为d1的倍数的元素放在同一个组中，在各组内进行直接插入排序。然后取第二个增量d2（＜d1），重复上述的分组和排序，直至所取的增量dt=1（dt<dt-1<…<d2<d1），即所有元素放在同一组中进行直接插入排序为止。9.2.3希尔排序9.2插入排序19/86将元素序列分成若干子序列，分别对每个子序列进行插入排序。

其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。例如：将n

个元素分成d

个子序列：

{R[0]，R[d]，R[2d]，…，

R[kd]}{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}

…{R[d-1]，R[2d-1]，R[3d-1]，…，R[(k+1)d-1]}9.2插入排序20/86例如：9876543210初始序列8765943210d=5直接插入排序4321098765d=d/2=243210987650123456789直接插入排序d=d/2=10123456789直接插入排序0123456789注意：对于d=1的一趟，排序前的数据已将近正序！9.2插入排序21/86取d1=n/2，di+1=

di/2

时的希尔排序的算法如下：voidShellSort(SqTypeR[],intn) {inti,j,d;

SqTypetmp;

d=n/2;

//增量置初值

while(d>0)

{for(i=d;i<n;i++)

{tmp=R[i]; //对所有相隔d位置的元素组采用直接插入排序

j=i-d;

while(j>=0&&tmp.key<R[j].key){R[j+d]=R[j];j=j-d;

}

R[j+d]=tmp;

}

d=d/2;

//减小增量

}}9.2插入排序22/86希尔排序的时间复杂度约为O(n1.3)。为什么希尔排序比直接插入排序好？例如：有10个元素要排序。希尔排序直接插入排序大约时间=102=100d=5：分为5组，时间约为5*22＝20d=2：分为2组，时间约为2*52＝50d=1：分为1组，几乎有序，时间约为10＋＋＝809.2插入排序23/86归纳起来，希尔排序算法的性能如表9.2所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况－O(n2)O(n1.5)O(1)不稳定9.2插入排序24/869.3交换排序交换排序基本思路：两两比较待排序元素的关键字，并交换不满足次序要求的那些偶对，直到全部满足为止。主要的交换排序算法：冒泡排序和快速排序。9.3交换排序25/86有序区R[0]┇R[i-1]无序区R[i]R[i+1]┇R[n-1]将无序区中最小元素放在R[i]有序区R[0]┇R[i-1]R[i]无序区R[i+1]┇R[n-1]一趟排序初始有序区为空。i＝0~n-2，共n-1趟使整个数据有序。R[i]有序区总是全局有序的9.3.1冒泡排序9.3交换排序26/86R[j]和R[j-1]反序

交换。若某一趟比较时不出现任何元素交换，说明所有元素已排好序了，就可以结束本算法。9.3交换排序27/86

【例9.3】已知有10个待排序的元素，它们的关键字序列为(75,87,68,92,88,61,77,96,80,72)，给出用冒泡排序法进行排序的过程。初始序列75876892886177968072i=0[61]758768928872779680i=161[68]7587729288778096i=26168[72]75877792888096i=3616872[75]778780928896i=461687275[77]8087889296i=56168727577[80]87889296最后结果616872757780878892969.3交换排序28/86冒泡排序算法如下：voidBubbleSort(SqTypeR[],intn){

inti,j,exchange;

SqTypetmp;

for(i=0;i<n-1;i++)

{exchange=0;

//本趟排序前置exchange为0

for(j=n-1;j>i;j--) //比较,找出最小关键字的元素

{

if(R[j].key<R[j-1].key)

{tmp=R[j];

//R[j]与R[j-1]进行交换,

R[j]=R[j-1]; //将最小关键字元素前移

R[j-1]=tmp;

exchange=1; //本趟排序发生交换置exchange为1

}

}if(exchange==0) //本趟未发生交换时结束算法

return;

}}29/86最好的情况（正序）：只需进行一趟冒泡“比较”的次数：0“移动”的次数：n-1最坏的情况（反序）：需进行n-1趟冒泡“比较”的次数：“移动”的次数：9.3交换排序30/86归纳起来，冒泡排序算法的性能如表9.3所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况O(n)O(n2)O(n2)O(1)稳定9.3交换排序31/86

首先对无序的元素序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无序序列无序子序列(1)无序子序列(2)基准一次划分分别进行快速排序9.3.2快速排序9.3交换排序32/86每趟使表的第一个元素（基准）放入适当位置，将表一分为二，对子表按递归方式继续这种划分。直至划分的子表长为0或者1。9.3交换排序33/86

【例9.4】设待排序的表有10个元素，其关键字分别为（6，8，7，9，0，1，3，2，4，5）。说明采用快速排序方法进行排序的过程。9.3交换排序34/866

87

9

0

1

3

2455

423019

7861

423

050，1，2，3，4，5，6，7，8，902

3

413

42348

7978快速排序递归树将递归树看成一棵3叉树，每个分支结点对应一次递归调用。这里递归次数：7左右子序列处理的顺序无关9.3交换排序35/8631542划分如何做？tmpiji=j：处理完毕划分完毕整个序列：R[s..t]左子序列：R[s..i-1]右子序列：R[i+1..t]36/86快速排序算法如下：voidQuickSort(SqTypeR[],ints,intt)//对R[s..t]的元素进行递增快速排序{inti=s,j=t;SqTypetmp;if(s<t) //区间内至少存在2个元素的情况

{tmp=R[s]; //用区间的第1个元素作为基准

while(i!=j) //从区间两端交替向中间扫描,直至i=j为止

{while(j>i&&R[j].key>=tmp.key)

j--; //从右向左扫描,找第1个小于tmp.key的R[j] if(i<j)

{R[i]=R[j]; //将R[j]前移到R[i]的位置

i++;}

while(i<j&&R[i].key<=tmp.key)

i++; //从左向右扫描,找第1个大于tmp.key的R[i]

if(i<j){R[j]=R[i]; //将R[i]后移到R[j]的位置

j--;}

}

R[i]=tmp;9.3交换排序37/86QuickSort(R,s,i-1);

//对左区间递归排序

QuickSort(R,i+1,t);

//对右区间递归排序

}}9.3交换排序R[s]………R[t]R[s]…R[i-1]R[i+1]…R[t]R[i]一次划分分别进行快速排序38/86算法分析最好的情况（随机分布）n个元素n/2个元素n/2-1个元素时间复杂度:O(nlog2n)最坏的情况（正序或者反序）n个元素n-1个元素空时间复杂度:O(n2)39/86则可得结果：结论:

快速排序的时间复杂度为O(nlog2n)平均情况：平均所需栈空间为O(log2n)。nk-1n-k1次划分的时间Tavg(n)=Cnlog2n。9.3交换排序40/86归纳起来，快速排序算法的性能如表9.4所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况O(nlog2n)O(n2)O(nlog2n)O(log2n)不稳定9.3交换排序41/869.4选择排序选择排序基本思路：每步从待排序的元素中选出关键字最小的元素，按顺序放在已排序的元素序列的最后，直到全部排完为止。主要的选择排序算法：简单选择排序和堆排序。9.4选择排序42/86有序序列R[0..i-1]无序序列R[i..n-1]

第i

趟简单选择排序从中选出关键字最小的元素有序序列R[0..i-1]无序序列R[i+1..n-1]9.4.1简单选择排序9.4选择排序43/86

【例9.5】已知有10个待排序的元素，它们的关键字序列为(75,87,68,92,88,61,77,96,80,72)，给出用直接选择排序法进行排序的过程。初始序列75876892886177968072i=061876892887577968072i=161688792887577968072i=261687292887577968087i=361687275889277968087i=461687275779288968087i=561687275778088969287i=661687275778087969288i=761687275778087889296i=861687275778087889296最后结果616872757780878892969.4选择排序44/86简单选择排序算法如下：voidSelectSort(SqTypeR[],intn) {inti,j,k;

SqTypetmp;

for(i=0;i<n-1;i++)

{k=i;

for(j=i+1;j<n;j++){

if(R[j].key<R[k].key)

k=j; //用k指出每趟在无序区段的最小元素

}if(k!=i)

{tmp=R[i]; //将R[k]与R[i]交换

R[i]=R[k];R[k]=tmp;

}

}}9.4选择排序45/86

对n

个元素进行简单选择排序，所需进行的关键字间的比较次数总计为：移动元素的次数，最小值为0,最大值为3(n-1)。9.4选择排序46/86归纳起来，简单选择排序算法的性能如表9.5所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况O(n2)O(n2)O(n2)O(1)不稳定9.4选择排序47/86堆排序采用堆结构选择最大（最小）元素。设排序元素为R[1..n]。将R[1..n]看成是一棵完全二叉树的顺序存储结构。如果每个结点的关键字均大于等于其所有孩子结点的关键字，称为大根堆。如果每个结点的关键字均小于等于其所有孩子结点的关键字，称为小根堆。本章的堆排序采用的大根堆。9.4.2堆排序9.4选择排序48/86a1a2a3an…完全二叉树i2i2i+1左孩子右孩子大根堆：对应的完全二叉树中，任意一个结点的关键字都大于或等于它的孩子结点的关键字。最小关键字的元素一定是某个叶子结点！！！层序编号方式：a1

a2

…

an将序列a1

a2

…

an看成是一颗完全二叉树9.4选择排序49/86堆排序的关键是构造堆,这里采用筛选算法建堆。所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。堆堆筛选堆9.4选择排序50/86例如：（6,8,9,5,7,1）89571大根堆大根堆考虑根，不是大根堆比较tmp6比较整个调整成大根堆了！9.4选择排序51/86

假设对R[low..high]进行堆调整，它是一棵满足筛选条件的完全二叉树，即以R[low]为根结点的左子树和右子树均为堆，其调整堆的算法sift()如下：voidSift(SqTypeR[],intlow,inthigh) //对R[low..high]进行堆筛选{inti=low,j=2*i; //R[j]是R[i]的左孩子

SqTypetmp=R[i];while(j<=high)

{if(j<high&&R[j].key<R[j+1].key)

j++;

//若右孩子较大,把j指向右孩子

if(tmp.key<R[j].key)

{R[i]=R[j]; //将R[j]调整到双亲结点位置上

i=j; //修改i和j值,以便继续向下筛选

j=2*i;

}

elsebreak; //已是大根堆,筛选结束

}

R[i]=tmp; //被筛选结点的值放入最终位置}9.4选择排序52/869.4选择排序是一个堆是一个堆295413从根开始筛选大根堆tmp筛选示例相当于：将2有序插入的（9,4）中（9,4,2）53/86堆排序过程：从最后一个分支结点（编号为n/2）开始到根结点（编号为1）通过多次调用筛选算法建立初始堆。排序过程：9.4选择排序将R[1]（无序区中最大元素）与无序区最后一个元素交换，归位无序区最后一个元素，无序区减少一个元素。再筛选，重复进行，直到无序区只有一个元素。54/86堆排序的算法如下：voidHeapSort(SqTypeR[],intn)//对R[1..n]进行递增堆排序{inti;

SqTypetmp;

for(i=n/2;i>=1;i--) //循环建立初始堆

Sift(R,i,n);

for(i=n;i>=2;i--) //进行n-1次循环,完成堆排序

{ tmp=R[1]; //将R[1]和R[i]交换

R[1]=R[i];R[i]=tmp;

Sift(R,1,i-1); //筛选

}}9.4选择排序55/86【例9.6】已知有10个待排序的元素，它们的关键字序列为（75，87，68，92，88，61，77，96，80，72），给出用堆排序法进行排序的过程。75876892886177968072（1）建立初始堆的过程758768928861779680729.4选择排序56/8675876892886177968072758768968861779280729.4选择排序57/8675876896886177928072758777968861689280729.4选择排序58/8675877796886168928072759677928861688780729.4选择排序59/867596779288616887807296927787886168758072初始堆：96,92,77,87,88,61,68,75,80,729.4选择排序60/86（2）排序过程96927787886168758072第1趟排序结果（i=10）初始堆：72,92,77,87,88,61,68,75,80,96交换72969.4选择排序61/86729277878861687580第2趟排序结果（i=9）初始堆：80,88,77,87,72,61,68,75,92,96交换928877877261687580筛选9280最终结果：61,68,72,75,77,80,87,88,92,90以此类推9.4选择排序62/86堆排序的时间复杂度分析：对高度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；调整“堆顶”n-1次，总共进行的关键字比较的次数不超过

2(

log2(n-1)

+

log2(n-2)

+…+log22)<2n(

log2n

)

因此，堆排序的时间复杂度为O(nlog2n)。对n个关键字，建成高度为h(=

log2n+1)的堆，所需进行的关键字比较的次数不超过4n9.4选择排序63/86归纳起来，堆排序算法的性能如表9.6所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定9.4选择排序64/86归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表─二路归并排序。9.5归并排序9.5

归并排序65/86在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的元素有序子序列。归并为一个元素的有序序列。有序序列R[low..high]有序子序列R[low..mid]有序子序列R[mid+1..high]9.5

归并排序66/86

【例9.7】已知有10个待排序的元素，它们的关键字序列为（75，87，68，92，88，61，77，96，80，72），给出用归并排序法进行排序的过程。75，87，68，92，88，61，77，96，80，7275，8768，9261，8877，9672，8068，75，87，9261，77，88，9672，8061，68，75，77，87，88，92，9672，8061，68，72，75，77，80，87，88，92，96

log2n

趟9.5

归并排序67/86将两个有序子表归并为一个有序子表的算法Merge()：voidMerge(SqTypeR[],intlow,intmid,inthigh)//将R[low..mid]和R[mid+1..high]两个相邻的有序表归并为有序表R[low..high]{SqType*R1;

inti=low,j=mid+1,k=0; //k是R1的下标R1=(SqType*)malloc((high-low+1)*sizeof(SqType));

//动态分配空间R1while(i<=mid&&j<=high) //均未扫描完时循环{if(R[i].key<=R[j].key) //将第1子表中的元素放入R1中

{R1[k]=R[i];

i++;k++;

}

else

//将第2子表中的元素放入R1中

{R1[k]=R[j];

j++;k++;

}}9.5

归并排序68/86

while(i<=mid) //将第1子表余下部分复制到R1

{ R1[k]=R[i]; i++;k++;

}

while(j<=high) //将第2子表余下部分复制到R1

{ R1[k]=R[j]; j++;k++;

}

for(k=0,i=low;i<=high;k++,i++)

R[i]=R1[k]; //将R1复制回R中

free(R1); //释放R1所占内存空间}9.5

归并排序69/86MergePass()算法解决一趟归并问题：voidMergePass(SqTypeR[],intlength,intn)//一趟二路归并排序{inti;

for(i=0;i+2*length-1<n;i=i+2*length)

Merge(R,i,i+length-1,i+2*length-1);

//归并length长的两相邻子表if(i+length-1<n)

//余下两个子表,后者长度小于lengthMerge(R,i,i+length-1,n-1);}9.5

归并排序70/86二路归并排序算法如下：voidMergeSort(SqTypeR[],intn) //二路归并算法{intlength;

for(length=1;length<n;length=2*length)

MergePass(R,length,n);}9.5

归并排序71/86每一趟归并的时间复杂度为O(n)，总共需进行

log2n

趟。所以对n个元素进行归并排序的时间复杂度为Ο(nlog2n)。9.5

归并排序72/86归纳起来，二路归并排序算法的性能如表9.7所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定9.5

归并排序73/86基数排序是通过“分配”和“收集”过程来实现排序。是一种借助于多关键字排序的思想对单关键字排序的方法。9.6基数排序9.6基数排序74/86一般地，元素R[i]的关键字R[i].key是由d位数字组成，即kd-1kd-2…k0，每一个数字表示关键字的一位，其中kd-1为最高位，k0是最低位，每一位的值都在0≤ki<r范围内，其中r称为基数。例如，对于二进制数r为2，对于十进制数r为10。

9.6基数排序75/86基数排序有两种：最低位优先（LSD）和最高位优先（MSD）。最低位优先的过程：先按最低位的值对元素进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是根据关键字的一位并在前一趟的基础上对所有元素进行排序，直至最高位，则完成了基数排序的整个过程。最高位优先类似。9.6基数排序76/86分配：开始时，把Q0,Q1,…,Qr-1各个队列置成空队列，然后依次考察线性表中的每一个结点aj（j=0,1,…,n-1），如果aj的关键字kji=k，就把aj放进Qk队列中。收集：把Q0,Q1,…,Qr-1各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的线性表。对i=0,1,…,d-1，依次做一次“分配”和“收集”（其实就是一次稳定的排序过程）。9.6基数排序77/86建立10个队列，f为队头，r为队尾

进行第1次分配：按个位进行第1次收集h→369→367→167→239→237→138→230→139f[0]←r[0]f[7]←r[7]f[8]←r[8]f[9]←r[9]→369→367→167→237→239→139→138→230h→230→367→167→237→138→369→239→139例如(369,367,167,239,237,138,230,139)

基数排序第1趟排序完毕分配时是按一个一个元素进行的收集时是按一个一个队列进行的9.6基数排序78/86

进行第2次分配：按拾位进行第2次收集f[3]←r[3]f[6]←r[6]→367→167→369→230h第2趟排序完毕→237→138→139→239h→230→367→167→237→138→369→239→139→230→237→138→139→239→367→167→3699.