1、快速排序

快速排序：说白了就是给基准数据找其正确索引位置的过程。

1. 设置最开始的基准数据定义为数组中间的元素，用变量去存储基准数据，即mid=a[头+尾)/2];
2. 以mid为界，然后分别从数组的两端扫描数组，设两个指示标志:begin指向起始位置，end指向末尾。当begin与end相遇前，交换位置的值，直到两者相遇。
3. 重新调用函数qsort()，直到不满足条件if(h<end)；if(begin<r)。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int Max = 100; //定义数组长度 
int a[Max];
void qsort(int,int);

int main(){
	int n,i;
	cout<<"输入n个整数：";
	cin>>n;
	cout<<"每个整数按空格隔开："<<endl; 
	for(i=1;i<=n;i++) 	//输入数据 
		cin>>a[i];
	qsort(1,n);			//调用函数 
	
	cout<<"快速排序结果："<<endl; 
	for(i=1;i<=n;i++)	//输出数据 
		cout<<a[i]<<" ";
	cout<<endl;
}

void qsort(int h,int r){
	int begin,end,mid,p;
	begin=h;	//标记开头 
	end=r;		//标记尾巴 
	mid=a[(h+r)/2];	// 定义数组中间的元素基准数 
	do
	{
		while(a[begin]<mid) begin++; //左部分寻找比中间大的数位置 
		while(a[end]>mid) end--;	//右部分寻找比中间小的数位置
		if(begin<=end) //找到位置,交换值,直到两个标记相遇 
		{ //在左边数比mid大 or 右边数比mid小的情况-->交换值
			p=a[begin];
			a[begin]=a[end];
			a[end]=p;
			begin++;
			end--; 
		}
	}while(begin<=end);
// 一趟过后，begin>end; mid的左边数<mid; mid的右边数>mid;
	if(h<end) //mid左边满足条件 
		qsort(h,end); // 递归->对h,end的范围进行qsort()判断 
	if(begin<r) //mid右边满足条件 
		qsort(begin,r);	// 递归->
}

快速排序是不稳定的排序方法，时间复杂度是O(nlog2n)，速度快，平均时间来说，快速排序是最好的一种内部排序方法。但快速排序需要一个栈空间实现递归，每一趟排序都会将记录序列分割成两个子序列，栈最大深度为log(n+1)。

2、归并排序

归并的思路（分治）是把一个大问题a拆解成两个小问题b和c，解决了两个子问题再整合一下，就解决了原问题。用递归的方法，先分解再合并（分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突）。

• 稳定性：稳定；
• 空间复杂度O(n)；
• 复杂度：时间复杂度O(nlogn)；
• 优缺点：效率高且稳定，但是消耗的辅助空间与原数据空间成正比。

1. 若low>high,则将序列分从中间mid=(low+high)/2分开；
2. 对左半部分[low, mid]递归地进行归并排序；
3. 对右半部分[mid+1, high]递归地进行归并排序；
4. 将左右两个有序子序列Merge为一个。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int Max = 1000; //定义数组长度 
int a[Max]; //定义数组 
int r[Max]; //定义辅助函数 

void merge(int a[],int low,int mid,int high){ //2.3
	int i=low,j=mid+1,k=low;  //i,j标记mid分割后左右序列的首位置，k记录序列首位置 
	for(k;k<=high;k++) //把数组a复制到数组r上; 
		r[k]=a[k];
		
	for(k=i;i<=mid && j<=high; k++){ //在范围内
		if(r[i]<=r[j]) 	  //比较左、右序列的值,把小的值存在数组a;
			a[k]=r[i++]; //以此类推,保证数组a[]顺序存储从小到大; 
		else
			a[k]=r[j++];
	}	//剩下的不在在范围内 
	while(i<=mid) a[k++]=r[i++];   //保存到数组a[]后面 
	while(j<=high) a[k++]=r[j++];
}

void msort(int a[],int low,int high){ //2.1
	if(low<high){
		int mid=(low+high)/2;
		msort(a,low,mid);
		msort(a,mid+1,high);	//当函数msort()递归到只有一个元素组成的序列
		merge(a,low,mid,high);  //2.2 就调用这个方法 
	}
}
int main(){
	int n;
	cout<<"输入n个整数：";
	cin>>n;
	cout<<"每个整数按空格隔开："<<endl; 
	for(int i=1;i<=n;i++) 	//1、输入数据 
		cin>>a[i];
	msort(a,1,n);	//2、调用函数 
	cout<<"归并排序结果："<<endl; 
	for(int i=1;i<=n;i++)	//3、输出数据 
		cout<<a[i]<<" ";
	cout<<endl;
}