分治思想实现：归并排序、快速排序(C/C++)

归并排序：

思想图解（网上选取供参考）：

实现思想:

    数组排序任务可以如下完成:

    1) 把前一半排序；

    2) 把后一半排序；

    3) 把两半归并到一个新的有序数组，然后再拷贝回原数组，然后再拷贝回原数组,排序完成；

C/C++代码示例:

#include<iostream>
using namespace std;

int a[10] = {13,27,19,2,8,12,2,8,30,89};
int b[10];

void Merge(int a[],int s,int mid,int e,int tmp[])
{	//将数组a的局部a[s,m]和a[m+1,e]合并到tmp,并保证tmp有序,然后再拷贝回a[s,m]
	//归并操作时间复杂度: O(e-m+1),即O(n)
	int pb = 0;					//pb是tmp数组的指针(下标指针) 
	//p1是a数组(s到mid区间上)的指针,p2是a数组(mid到e区间上)的指针
	int p1 = s,p2 = mid+1; 
	while(p1 <= mid && p2 <= e)	//p1最大区间是mid,p2最大区间是e. 
	{
		if(a[p1] < a[p2])		//两段区间中的元素相比,谁小就把谁放入tmp中 
			tmp[pb++] = a[p1++];//指针对应元素放入后都要向后移一位 
		else
			tmp[pb++] = a[p2++];//指针对应元素放入后都要向后移一位
	}
	//然后,把剩下的指针没走到头的部分全拷贝过去就完事 
	while(p1 <= mid)				//判断p1是否走到头 
		tmp[pb++] = a[p1++];
	while(p2 <= e)					//判断p2是否走到头 
		tmp[pb++] = a[p2++];
	for(int i = 0;i < e-s+1;i ++)	//最后,将tmp中排好序的数组拷贝到a数组中就完事 
		a[s+i] = tmp[i];
}


void MergeSort(int a[],int s,int e,int tmp[])
{									//该函数就是将传入的数组不停的切开 
	if(s < e)						//只要还能切,就继续切,还剩一个,不能切就收工 
	{
		int mid = s + (e-s)/2;		//从中间切开 
		MergeSort(a,s,mid,tmp);		//从s到mid的中间切开 
		MergeSort(a,mid+1,e,tmp);	//从mid到e的中间切开
//此时已经切成一个一个的单个数组元素,就进行下一步逐个归并起来 
		Merge(a,s,mid,e,tmp);		//占用格外存储空间 
	}
} 

int main()
{
	int size = sizeof(a)/sizeof(int);
	MergeSort(a,0,size-1,b); 
	for(int i = 0;i < size;i ++)
		cout<<a[i]<<",";
	cout<<endl;
	return 0;
}

快速排序：

思想图解：推荐看《啊哈，算法》上面的哨兵图解。

基本实现思想：

也是分治，只不过跟归并排序不一样在，归并排序是切完后有序的合并起来，而快速排序是从一组数的两头出发往中间跑，分别跟指定的基准数对比，如果不符合从大到小或者从小到大的的话就交换，然后分成两份继续从两头往中间跑，接着跟新的基准数作对比，一直分下去，知道结束为止。

C/C++代码示例：

#include<stdio.h>

void swap(int a,int b)
{
	int temp = a;
	a = b;
	b = temp;
}

void quicksort(int a[],int left,int right)
{
	int i,j,temp;
	if(left>right)
		return ;
	temp = a[left];		//temp中存的就是基准数
	i = left;
	j = right;
	while(i != j)
	{
		//顺序很重要,要先从右往左
		while(a[j] >= temp && i < j)
			j --;
		//再从左往右找
		while(a[i] <= temp)
			i ++;
		//交换两个数在数组中的位置
		if(i < j)		//当i与j没有相遇的时候
		swap(a[i],a[j]);
	}
	//将基准数归位
	a[left] = a[i];
	a[i] = temp;
	quicksort(a,left,i-1);	//继续处理左边的，这里是一个递归的过程
 	quicksort(a,i+1,right);	//继续处理右边的，这里是一个递归的过程
}

int main()
{
	int i,n,arr[100];
	scanf("%d",&n);
	for(i = 0;i < n;i ++)
		scanf("%d",&arr[i]);
	
	quicksort(arr,0,n);
	
	for(i = 0;i < n;i ++)
		printf("%d",arr[i]);
}