引：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，因此是无法通过不添加额外数据结构来实现快速排序的

概述
 
归并排序是典型的分而治之策略的应用。主要是把一个数组分成若干个子数组进行从小到大的归并直至有序。下面所说的归并排序默认为2路归并排序。
 
 
递归算法思想
 
1）将数组平分为2等份，对这两个子数组进行从小大到有序归并。 
 2）递归对左半部分进行2路归并 
 3）递归对右半部分进行2路归并
 
//一趟归并 
void Merge(int* data,int* tmp,int left,int right,int rightend)
{
    int leftend = right-1;
    int size = rightend-left+1;
    int cnt = left;
    while(left <= leftend && right <= rightend){
        if(data[left] < data[right]){
            tmp[cnt++] = data[left++];
        }else{
            tmp[cnt++] = data[right++];
        }
    }
    while(left <= leftend){
        tmp[cnt++] = data[left++];
    }
    while(right <= rightend){
        tmp[cnt++] = data[right++];
    }
    for(int i = 0 ; i < size ; i++,rightend--){
        data[rightend] = tmp[rightend]; 
    }
}

//归并排序  
void Msort(int* data,int* tmp,int left,int rightend)
{
    if(left < rightend){
        int mid = (left+rightend)/2;
        Msort(data,tmp,left,mid);
        Msort(data,tmp,mid+1,rightend);
        Merge(data,tmp,left,mid+1,rightend);
    }
}

//归并排序(递归版本)
void Merge_Sort(int* data,int size)
{
    int* tmp = new int[size];
    if(tmp != NULL){
        Msort(data,tmp,0,size-1);
    }
}
 
 
非递归算法思想
 
1）首先构造一个与原数组大小一样的临时数组 
 2）设置归并长度length = 1，从头开始堆两个length长度的数组进行归并到tmp直至倒数第二组。由于原数组长度与length布置时候能整除，如果能整除，那么把最后一组归并到数组了，若不能，那么就直接导入tmp数组。 
 3）更新length，使之翻倍，重复上述2）操作，只不过是把tmp的数组归并到原数组。 
 4）重复上述2）与3）操作，直至length大于数组长度。
 
//一趟归并 
void Merge(int* data,int* tmp,int left,int right,int rightend)
{
    int leftend = right-1;
    int size = rightend-left+1;
    int cnt = left;
    while(left <= leftend && right <= rightend){
        if(data[left] < data[right]){
            tmp[cnt++] = data[left++];
        }else{
            tmp[cnt++] = data[right++];
        }
    }
    while(left <= leftend){
        tmp[cnt++] = data[left++];
    }
    while(right <= rightend){
        tmp[cnt++] = data[right++];
    }
    for(int i = 0 ; i < size ; i++,rightend--){
        data[rightend] = tmp[rightend]; 
    }
}

//一趟归并排序
void Merge_Pass(int* data,int* tmp,int size,int length)
{
    int i;
    for(i = 0 ; i <= size-2*length ; i += 2*length){
        Merge(data,tmp,i,i+length,i+2*length-1);
    }
    if(i+length < size){//归并最后两个子序列 
        Merge(data,tmp,i,i+length,size-1);
    }else{//归并最后一个子序列 
        for(int j = i ; j < size ; j++){
            tmp[j] = data[j];
        }
    }
}
//归并排序(非递归排序)
void Merge_Sort1(int* data,int size)
{
    int* tmp = new int[size];
    int length = 1;
    if(tmp != NULL){
        while(length < size){
            Merge_Pass(data,tmp,size,length);
            length*=2;
            Merge_Pass(tmp,data,size,length);
            length*=2;
        }
        delete tmp;
    }
}
 
 
全部代码
 
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

//初始化数组 
void SetArray(int* data,int size)
{
    //srand(time(0));
    cout<<"随机初始化"<<size<<"个数"<<endl;
    for(int i = 0 ; i < size ; i++){
        data[i] =rand()%100+1;
    }
}

//打印函数 
void Print(int* data ,int size)
{
    for(int i = 0 ; i < size ; i++){
        cout<<data[i]<<" "; 
    }
    cout<<endl;
}       

//一趟归并 
void Merge(int* data,int* tmp,int left,int right,int rightend)
{
    int leftend = right-1;
    int size = rightend-left+1;
    int cnt = left;
    while(left <= leftend && right <= rightend){
        if(data[left] < data[right]){
            tmp[cnt++] = data[left++];
        }else{
            tmp[cnt++] = data[right++];
        }
    }
    while(left <= leftend){
        tmp[cnt++] = data[left++];
    }
    while(right <= rightend){
        tmp[cnt++] = data[right++];
    }
    for(int i = 0 ; i < size ; i++,rightend--){
        data[rightend] = tmp[rightend]; 
    }
}

//归并排序  
void Msort(int* data,int* tmp,int left,int rightend)
{
    if(left < rightend){
        int mid = (left+rightend)/2;
        Msort(data,tmp,left,mid);//递归归并排序左半部分 
        Msort(data,tmp,mid+1,rightend);//递归归并排序右半部分 
        Merge(data,tmp,left,mid+1,rightend);//对左右部分进行有序归并 
    }
}

//归并排序(递归版本)
void Merge_Sort(int* data,int size)
{
    int* tmp = new int[size];
    if(tmp != NULL){
        Msort(data,tmp,0,size-1);
    }
}

//一趟归并排序
void Merge_Pass(int* data,int* tmp,int size,int length)
{
    int i;
    for(i = 0 ; i <= size-2*length ; i += 2*length){
        Merge(data,tmp,i,i+length,i+2*length-1);
    }
    if(i+length < size){//归并最后两个子序列 
        Merge(data,tmp,i,i+length,size-1);
    }else{//归并最后一个子序列 
        for(int j = i ; j < size ; j++){
            tmp[j] = data[j];
        }
    }
}
//归并排序(非递归排序)
void Merge_Sort1(int* data,int size)
{
    int* tmp = new int[size];
    int length = 1;
    if(tmp != NULL){
        while(length < size){
            Merge_Pass(data,tmp,size,length);
            length*=2;
            Merge_Pass(tmp,data,size,length);
            length*=2;
        }
        delete tmp;
    }
}

int main()
{
    cout<<"请输入数组长度:"<<endl;
    int size,*data;
    cin>>size;
    data = new int[size];

    SetArray(data,size);
    cout<<"归并排序（递归版本）前："<<endl;
    Print(data,size);
    cout<<"归并排序（递归版本）后："<<endl;
    Merge_Sort(data,size);
    Print(data,size); 

    SetArray(data,size);
    cout<<"归并排序（非递归版本）前："<<endl;
    Print(data,size);
    cout<<"归并排序（非递归版本）后："<<endl;
    Merge_Sort1(data,size);
    Print(data,size);

    return 0;
 }  
 
截图： 
 

 
 
 不要自卑，去提升实力
 互联网行业谁技术牛谁是爹
 如果文章可以带给你能量，那是最好的事！请相信自己
 加油o~ 
 
 
 
 
 
已知数据序列为（12,5，9,20,6，31,24），对该数据序列进行排序，写出插入排序、冒泡排序、快速排序、简单选择排序、堆排序以及二路归并排序每趟的结果。
 
 
代码已经写好，自己运行一下就好啦
 
代码：
 
/**
 *作者：魏宝航
 *2080年14月45日,上午8:41
 */
package 八大排序;
import java.util.Arrays;
import java.util.Scanner;
public class 八大排序 {
	public static void main(String[] args) {
		int[] a=new int[] {12,5,9,20,6,31,24};
		System.out.println("冒泡排序:");
		bubbleSort(new int[] {12,5,9,20,6,31,24});
		System.out.println("选择排序:");
		chooseSort(new int[] {12,5,9,20,6,31,24});
		System.out.println("插入排序:");
		insertSrot(new int[] {12,5,9,20,6,31,24});
		System.out.println("希尔排序:");
		hillSort(new int[] {12,5,9,20,6,31,24});
		System.out.println("基数排序:");
		baseSort(new int[] {12,5,9,20,6,31,24});
		System.out.println("归并排序:");
		mergeSort(a, 0, a.length-1, new int[7]);
		System.out.println("快速排序:");
		quickSort(new int[] {12,5,9,20,6,31,24});
		System.out.println("堆排序:");
		heapSort(new int[] {12,5,9,20,6,31,24});		
	}
	//冒泡排序
	public static void bubbleSort(int [] a) {
		int i,j;
		for(i=0;i<a.length-1;i++) {
			for(j=0;j<a.length-i-1;j++)
				if(a[j]>a[j+1]) {
					int temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
				}
			System.out.println(Arrays.toString(a));
			
		}
	}
	//选择排序
	public static void chooseSort(int [] a) {
		int i,j;
		for(i=0;i<a.length;i++) {
			int min=a[i];
			int minindex=i;
			for(j=i+1;j<a.length;j++)
				if(a[j]<min) {
					min=a[j];
					minindex=j;
				}
			
			a[minindex]=a[i];
			a[i]=min;
			System.out.println(Arrays.toString(a));
		}
	}
	//插入排序
	public static void insertSrot(int [] a) {
		int i,j;
		for(i=1;i<a.length;i++) {
			j=i;
			int temp=a[j];
			if(a[j]<a[j-1]) {
				while(j-1>=0&&temp<a[j-1]) {
					a[j]=a[j-1];
					j--;
				}
				a[j]=temp;
			}
			System.out.println(Arrays.toString(a));
			
		}
	}
	//希尔排序
	public static void hillSort(int [] a) {
		int i,j;
		for(int gap=a.length/2;gap>0;gap/=2) {
			for(i=gap;i<a.length;i++) {
				j=i;
				int temp=a[j];
				if(a[j]<a[j-gap]) {
					while(j-gap>=0&&temp<a[j-gap]) {
						a[j]=a[j-gap];
						j-=gap;
					}
					a[j]=temp;
				}
			}
			System.out.println(Arrays.toString(a));
		}
	}
	//基数排序
	public static void baseSort(int [] a) {
		int i,j,k,n;
		int max=a[0];
		for(i=1;i<a.length;i++)
			if(a[i]>max)
				max=a[i];
		int maxlength=(max+"").length();
		int [][] bucket=new int [10][a.length];
		int [] bucketcount=new int [10];
		for(k=0,n=1;k<maxlength;k++,n*=10) {
			for(i=0;i<a.length;i++) {
				int dight=a[i]/n%10;
				bucket[dight][bucketcount[dight]]=a[i];
				bucketcount[dight]++;
			}
			int index=0;
			for(i=0;i<10;i++) {
				if(bucketcount[i]!=0) {
					for(j=0;j<bucketcount[i];j++) {
						a[index]=bucket[i][j];
						index++;
					}
				}
				bucketcount[i]=0;
			}
			System.out.println(Arrays.toString(a));
		}
	}
	//归并排序
	public static void merge(int [] a,int left,int mid,int right,int [] temp) {
		int i=left;
		int j=mid+1;
		int t=0;
		while(i<=mid&&j<=right) {
			if(a[i]<a[j]) {
				temp[t]=a[i];
				t++;
				i++;
			}
			else {
				temp[t]=a[j];
				t++;
				j++;
			}
		}
		while(i<=mid) {
			temp[t]=a[i];
			t++;
			i++;
		}
		while(j<=right) {
			temp[t]=a[j];
			t++;
			j++;
		}
		int templeft=left;
		t=0;
		while(templeft<=right) {
			a[templeft]=temp[t];
			templeft++;
			t++;
			
		}
	}
	public static void mergeSort(int [] a,int left,int right,int [] temp) {
		if(left<right) {
			int mid=(left+right)/2;
			mergeSort(a,left,mid,temp);
			mergeSort(a,mid+1,right,temp);
			merge(a,left,mid,right,temp);
			System.out.println(Arrays.toString(a));
		}
	}
	//快速排序
	public static void quickSort(int [] a) {
		if(a==null||a.length<=1)
			return;
		quickSort(a,0,a.length-1);
	}
	public static void quickSort(int [] a,int left,int right) {
		if(left>=right)
			return;
		int pivotindex=left+(int)(Math.random()*(right-left+1));
		swap(a,pivotindex,right);
		int i=left;
		int j=right-1;
		while(i<=j) {
			if(a[i]<=a[right])
				i++;
			else {
				swap(a,i,j);
				j--;
			}
		}
		swap(a,i,right);
		System.out.println(Arrays.toString(a));
		quickSort(a,left,i-1);
		quickSort(a,i+1,right);
		
	}
	public static void swap(int [] a,int x,int y) {
		int temp=a[x];
		a[x]=a[y];
		a[y]=temp;
	}
	//堆排序
	public static void heapSort(int[] a) {
		for(int i=a.length/2-1;i>=0;i--) {
			adjustHeap(a,i,a.length);
		}
		int temp;
		for(int j=a.length-1;j>0;j--) {
			temp=a[j];
			a[j]=a[0];
			a[0]=temp;
			adjustHeap(a,0,j);
			System.out.println(Arrays.toString(a));
		}
	}
	public static void adjustHeap(int[] a,int i,int length) {
		int temp=a[i];
		for(int k=i*2+1;k<length;k=k*2+1) {
			if(k+1<length&&a[k]<a[k+1]) {
				k++;
			}
			if(a[k]>temp) {
				a[i]=a[k];
				i=k;
				a[i]=temp;
			}else {
				break;
			}
		}
	}
}

 
 
归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。
 
 
思想:
 
归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
 
分解：将n个元素分成个含n/2个元素的子序列。
解决：用合并排序法对两个子序列递归的排序。
合并：合并两个已排序的子序列已得到排序结果。
 
 
 /**
     * @param arr   原数组
     * @param left  左端索引
     * @param right 右端索引
     * @param temp  拷贝数组
     */
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            //分
            int point = (left + right) / 2;
            mergeSort(arr, left, point, temp);
            mergeSort(arr, point + 1, right, temp);
            //合并
            merge(arr, left, point, right, temp);
        }
    }

    /**
     * 合并
     *
     * @param arr   原数组
     * @param left  左端索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  拷贝数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        //从左往右依次合并
        int l = left;
        int r = mid + 1;
        int t = 0;//temp数组的索引
        while (l <= mid && r <= right) {//只有两端数据都没有合并，才逐个进行合并
            if (arr[l] <= arr[r]) temp[t++] = arr[l++];
            else temp[t++] = arr[r++];
        }
        //如果左端没有遍历完成
        while (l <= mid) {
            temp[t++] = arr[l++];
        }
        //如果右边没有遍历完成
        while (r <= right) {
            temp[t++] = arr[r++];
        }
        //拷贝回原数组,不是拷贝所有位置，只有复制的这一段需要拷贝
        int tempLeft = left;//当前合并的元素最左边的位置
        t = 0;
        while (tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
        }
    }