引：2019年408中数据结构一道考察快速排序的选择题



答案：D

定位：这道题在考察快速排序中一趟的概念。注意，基本的冒泡，插入，选择排序的一趟概念很容易理解，

接下来我们要讨论的是递归排序算法中（本文以快排和归并排序）讨论“趟”是否有意义。（先说结论，有，但并不像基本排序算法里那么简单，或者说，像基本算法里那么有普适性，归并排序只有非递归实现才有讨论趟的必要性，而快速排序更为复杂一些）

思路：

回想教材（《数据结构》严）里对一趟的定义



算法描述：



可见第一张图的过程实际上是递归形式实现的快排第一次调用Partition函数产生的结果。

然而，我们知道，如果第一次选中的pivot处在了待排序元素最终结果中的中间位置。那么接下来的处理也是递归进行的，

如图(a)所示，在第一次调用Patition函数后，元素49被放到了最终位置，之后对49左侧位置元素调用Qsort进行处理，

之后，关键关键的一步来了。

对 49左侧位置元素（27 48 13）调用Qsort处理时，首先调用Partition函数选出Pivot 27（默认第一个元素作pivot），

接下来呢？是立刻返回并去处理49右边的元素再调用一次Partition吗？并不是，这显然不是递归函数执行过程，

正确的执行过程是在对（27 48 13）这个左子表调用Partition后变为（13 27 48）接下来会继续对27左侧子表调用Qsort进行处理。

什么意思？等递归函数处理到 49右侧位置元素 时，其左侧元素都已经排好序了！

我们再看题干描述 趟 的概念：对尚未确定最终位置的所有元素进行一遍处理称为一趟。

发现问题了吗？如果是递归实现的快排，按题干的的意思，把所有尚未确定最终位置元素进行一遍处理，只有第一次选中的元素处在最终位置的边缘，

才能保证有第二趟的概念，为什么？很简单，如果第一次选中的元素恰好在最终位置中间部分，比如教材里这个例子，那么严格意义上讲，这种情况下它的执行过程只有两趟（递归实现的快排）！

最新更改：上面我的结论有问题，如果第一次pivot选在了中间，也是有第二趟概念的。以2019年408选择题为例：

D选项中12和32排在了最终位置，那么假设这是两趟的结果吧，那得满足什么条件？

或者说D选项怎么改才算正确？

答：2，5，12，28，16，32，72，60（只是其中一种可能）

没错，把12左侧元素改为顺序即为可能出现的情况，也就是对应的快排代码中递归的顺序是先对pivot左侧递归调用Qsort，左侧都已经有序了，

再对右侧进行一次递归调用Qsort，首先会调用Partition，那么刚进行完这次Partition后，得到的结果即为“第二趟”。

 

注意这里的 趟 是题目定义的趟，对所有的未确定最终位置元素进行一遍处理。

（这里注意区分，我们平时讲的快速排序最坏情况下（初始情况完全有序），它的递归次数会达到最高（不是这里题目中的趟数））

 

 

简单反思下这个题纠结在哪了？快速排序我们平时记得多是Partition函数会使待排序数列产生一个位于最终位置的元素。

平时的教材中多是这样描述



就容易先入为主地认为1之后立刻执行2或者1，2同时进行（实际上的确有并行快速排序算法），

然而我们熟悉的多是递归形式实现的快速排序算法，PS：我又去查了下非递归实现的快排，多是用栈模拟..（把栈模拟出来，这难道就不算递归吗？）

这时另外一些稀奇古怪的问题冒出来了：所有的递归都可以改成非递归吗？手动压栈这种写法就不算递归了吗？（深坑，暂时不多做探讨，之所以会有这个问题是因为我看到了递归和非递归归并算法的实现）

即同样的，也有类似问题，问归并排序的“第二趟”处理结果类似问题

对序列25，57，48，37，12，82，75，29进行二路归并排序，第二趟归并后的结果为（）。

A．25，57，37，48，12，82，29，75
B．25，37，48，57，12，29，75，82

C．12，25，29，37，48，57，75，82

D．25，57，48，37，12，82，75，29

然而，我们平时写的也多是递归形式的，

//递归形式
void Msort(int a[], int l, int r)
{
    mid = (l + r) / 2
	Msort(a,l,mid);
	Msort(a,mid+1,r);
	merge(a,l,r,mid);	//合并两个子表
}

还是和快排相似的问题：递归形式的归并排序有“趟”的概念吗？（如果按照和上一道题定义的趟的概念，是没有的！没有！）

那题就错了吗？不是，因为归并排序可以不借助栈，由循环结构实现。

非递归形式的归并排序思想是以2^k递增的间隔来划分待排序序列

void non_recur_msort(int arr[], int temp[], int left_end, int right_end)
{

 for(int i = left_end; i <= right_end; i = 2*i)
 {//i 是划分长度，以2^k速度递增,
  for(int j = left_end; j <= right_end-i; j += 2*i)
    //j用来迭代处理每个划分长度下，待排序序列划分得到的子表
    merge(arr, temp, j, j+i-1, Min(j + 2*i - 1 , right_end)); 
    //子表长度为i，合并的两个子表左子表起始位置为j，mid为 j+i-1，右子表终止位置为j+2*i-1，
 }
}

有些人会纠结奇数个元素怎么被处理的，看两张图，第一张是递归归并排序过程，第二张是非递归归并排序过程

 

第一张图——递归实现的归并排序是自顶向下划分（也就是划分时由大到小，再把小规模逐步求解），之后自底向上合并。



第二张图——非递归实现的归并排序的划分是由小到大（注意对比着上一张图看）



写到这，又回到了之前问题，快速排序的非递归形式会不会有类似（归并排序非递归方式）的实现？

似乎好多所谓的非递归只是手动实现了栈操作，然而我不确定这算不算是非递归。还有需要想到的应该是有没有并行快速排序的实现？

因为如果是并行实现的快排，那么同时调用Partition函数也就可以解释了



反思总结

像一些最基本的排序如插入排序，冒泡排序，选择排序的实现。在讨论一趟概念的时候并不需要考虑这么多。Why？

因为这些最基本的算法思想是迭代，什么是迭代？是逐步求得结果并更新，和一趟的概念较契合：每迭代处理一次所有未排序元素，就会求解出一个未排序元素最终位置。

而快排和归并接触到的写法多是递归形式的，利用了分治的思想，既然涉及分治，就无法避免划分和求解问题的顺序问题。

出现这个问题的根源是我们用递归方式去思考问题划分问题时是正向进行的，而实际运算处理是自底向上（递归划分到最底层再向上求解）的，这一点很容易混淆。

那说了半天遇到这种问题怎么搞？

如果是快速排序问第二趟，那么只有第一趟选中的元素位于边缘，才能有第二趟的存在，第k趟以此类推，或者换句话说，快速排序如果运行产生了第2，3，4，5趟，那一定是出现了初始状态导致了最坏情况的问题（也就是初始状态基本有序，导致递归趟数最大），这种情况下，递归趟数和排序趟数是一样的。

如果是归并排序第二趟，那么默认是在讨论非递归形式的归并排序（注意不是把栈写出来就算了..从本质上讲你把栈写出来并不能算是把递归算法转化成了非递归算法）

总而言之，趟是个非常鸡肋的概念，国外教材中暂时没有见过类似于趟描述，进一步说，这个概念纯粹是造出来出题玩的，无聊至极

 

后记：

去stackoverflow上找了下non-recursion quicksort without a stack，没想到用英文搜问题抓到了我疑惑的实质：

非尾递归的递归转化成iterative（迭代）算法是有代价的，那就是格外的数据结构（栈），原理涉及计算理论里图灵完备性（然而我仍然纠结non-recursive这个概念，不过这玩意用了这么久总不可能所有人都错了吧..基本现在一提非递归就都在说用栈模拟...

StackOverflow上有一个人回复类似问题的角度值得记下来：

因为快速排序的思想是divide and conquer，因此在你不需要用到其他partition时候，必然需要额外的数据结构保存那些partition，因此是无法通过不添加额外数据结构来实现快速排序的

归并排序法的执行流程如下： 

原始序列：49 38 65 97 76 13 27 

1.将原始序列看成是7个只含有一个元素的子序列，显然这些子序列是有序的。 

子序列1：49 

子序列2：38 

子序列3：65 

子序列4：97 

子序列5：76 

子序列6：13 

子序列7：27 

2.两两归并，形成若干有序二元组，第一趟二路归并排序结束后，结果如下： 

{38，49}，{65，97}，{13，76}，{27} 

然后再将这些序列看成是若干二元组子序列 

子序列1：38 49 

子序列2：65 97 

子序列3：13 76 

子序列4：27 

3.继续两两归并，形成若干有序四元组，第二趟二路归并结束后，结果如下： 

{38 49 65 79}，{13 27 76} 

4.最后将这些子序列在进行一次归并，就完成了整个二路归并 

13 27 38 49 65 76 79

时间复杂度为O(nlog(2)n) 

空间复杂度O(n)

归并排序的复杂度是O(nlogn) 性能优良，基本思想是这样的：乱序的数列，这里假设，3,1,0,0,4,8,6  。

第一趟排序，两个数字一组排序后结果为{1,3}{0,0}{4,8}{6}，
第二趟排序，{0,0,1,3}{4,6,8}
第三趟排序，{0,0,1,3,4,6,8}
显然归并排序的主要操作在于合并操作(merge).
ok，不多说了，关于排序的讲解网上很多，这里直接上代码。
void merge(int *a,int p,int q,int r){
     int n1 = q-p+1;
     int n2 = r-q;
     int *a1 = new int[n1];
     int *a2 = new int[n2];
     int p1 = p;
     int q1 = q+1;
     int i = 0;int j = 0;
     while(i<n1) a1[i++] = a[p1++];//p--q有序数组存入a1 
     while(j<n2) a2[j++] = a[q1++];//q+1--r有序数组存入a2 
     i = 0; j = 0;
     while(i<n1&&j<n2) 
         if(a1[i]<=a2[j]) a[p++] = a1[i++]; 
         else a[p++] = a2[j++]; 
     while(i<n1) a[p++] = a1[i++];
     while(j<n2) a[p++] = a2[j++];
}
void mergeSort(int *a,int p,int r){
     if(p<r){
         int q = (p+r)/2;
         mergeSort(a,p,q);
         mergeSort(a,q+1,r); 
         merge(a,p,q,r);       
     }          
}

归并排序原理

该算法的基本操作是合并两个已排序的表.因为两个表是已排序的,所以若将输出放到第三个表中,结果也是排好序的,合并算法可以通过对输入数据一趟排序来完成.递归调用分离的两个子表可求得结果.

归并算法策略

基本的合并算法是取两个输入数组A和B,一个输出数组C,以及3个计数器Actr,Bctr,Cctr,它们的初始位置对应数组的开始端.A[Actr]和B[Bctr]中较小者被拷贝到C中的下一个位置,相关的计数器向前推进一步.当两个各输入表有一个用完时,则将另一个表中剩余的部分拷贝到C中.合并例程工作图如下:

 



如果数组A含有1,13,24,26,数组B含有2,15,27,38,那么该算法的过程如下:首先,比较在1和2之间进行,1被添加到C中,然后13和2进行比较.



2被添加到C中,然后13和15比较



13被添加到C中,接下来比较24和15,这样一直进行到26和27比较







将26添加到数组C中,数组A已经用完.



然后将数组B的其余部分拷贝到C中.



合并两个已排序的表的时间显然是线性的,因为最多进行N-1次比较,其中N是元素的总数.

归并排序代码实现

	public static void mergeSort(int[] a){
		int[] tmpArray = new int[a.length];
		mergeSort(a,tmpArray,0,a.length-1);
	}
	
	public static void mergeSort(int[] a,int[] tmpArray, int left, int right){
		if(left < right){
			int center = (left + right )/2;
			mergeSort(a,tmpArray,left,center);
			mergeSort(a,tmpArray,center+1,right);
			merge(a,tmpArray,left,center+1,right);
		}
	}
	public static void merge(int[] a, int[] tmpArray, int leftPos, int rightPos, int rightEnd){
		int leftEnd = rightPos -1;
		int tmpPos = leftPos;
		int numElements = rightEnd - leftPos + 1;
		while(leftPos<=leftEnd&&rightPos<=rightEnd){
			if(a[leftPos]<a[rightPos])
				tmpArray[tmpPos++] = a[leftPos++];
			else
				tmpArray[tmpPos++] = a[rightPos++];
		}
		while(leftPos<=leftEnd)
			tmpArray[tmpPos++] = a[leftPos++];
		while(rightPos<=rightEnd)
			tmpArray[tmpPos++] = a[rightPos++];
		for(int i = 0; i < numElements;i++,rightEnd--){
			a[rightEnd] = tmpArray[rightEnd];
		}
	}

在Java中,快速排序也用作基本类型的标准库排序.这里,比较和数据移动的开销是类似的,因此使用少得多的数据移动足以补偿那些附加的比较而且还有盈余.

时间复杂度

归并排序以最坏情形时间运行,而所使用的比较次数几乎是最优的.