快速排序 归并排序

 快速排序（重点）

//quick_sort

void quick_sort(int a,int l,int r)
{
    if(l>=r) return;
    
    int i=l-1,j=r+1;            //所谓的 “ 双 指 针 ”
    int x=a[(l+r)/2];

     while(i<j)
	{    
		do i++;while(a[i]<x);    //不能等于x
		do j--;while(a[j]>x);
		if(i<j)
		{
			swap(a[i],a[j]);    //不合法则交换； 
		} 
	}

	quick_sort(a,l,j);
	quick_sort(a,j+1,r);

}
//算例： 1 3 2 6 5 
//算例： 4 1 4 2 5 

/*划分一个中间数。双指针向中间移动，最后的结果是将数组划分成两个区间；
然后以j为分界线进行划分。
在图中会表现为i和j “ 擦 肩 而 过 ” 
*/

归并排序

//merge_sort

void merge_sort(int a,int l,int r)
{
    if(l>=r) return;
    
   int m=(l+r)/2;
   merge_sort(a,l,m);
   merge_sort(a,m+1,r);
   
   int t[10],k=0;//存储合并之后的结果 
   int i=l,j=m+1;
 
	while(i<=m&&j<=r)
	{
		if(a[i]<a[j]) t[k++]=a[i++];
		else t[k++]=a[j++];
	} 
	
	while(j<=r) t[k++]=a[j++];
	while(i<=m) t[k++]=a[i++];
	
	for(int i=l,j=0;i<=r;i++,j++)  //将原来的数组粘贴到对应的位置当中去
	 
	{
		a[i]=t[j];
	}
}

/*
非常有趣的一个排序：
以m为界限不断的细分（调用自己）
所以在每一次调用的时候都会出现一个新的l和r，
不能再分时：（只有一个元素）先写入数组t[]（“排序”），然后在写入上个数组t。
t是一个中间数组，通过写入的方式实现了“排序“。

*/