合并排序

编程的习惯过于随便，正在改正中

这个排序写了一会就搞定了，结果一直有bug，搞了好久，发现是之前的一个last和end搞反了，心态爆炸，索性直接用一个。哎，以后写程序最好在一个程序中相同的变量同名（形参和实参同名），一个函数中不要出现意思和拼写相近的变量名。

废话太多，开搞；
合并排序作为分治算法的最典型的例子之一，它最为重要的核心就是分治。分治就是把一个大问题分解为一个一个便于解决的小问题（用递归实现）。比如讲一个待排序的序列分解为两个，两个再细分，再细分，直到好解决问题为止（即每个序列里面只有一个元素），在将这些在之前分解时同属于一个序列的两个子序列排序同时合并，最终到只剩下一个大序列时排序就完成了.

(图片援引自
dreamcatcher-cx的博客。PS:大佬的图片非常高级
链接：大佬的博客

）

#include"stdio.h"
int Read()
{
int w = 1,s = 0;
char c = getchar();
while(c>'9'||c<'0'){if(c == '-')w=-1;c = getchar();}
while(c>='0'&&c<='9'){s = s*10+c-'0';c = getchar();}
return w*s;
}
int ReadIn(int a[])
{
int N,i;
N = Read();
for(i = 0;i < N;i++)
a[i] = Read(); 
return N;
}
void Sort(int a[],int start,int end)
{
int i = 0,mid = (start+end)/2,p,q,b[10001],t;
p = start;q = mid+1;
while(p<=mid&&q<=end)
{
 if(a[p]>a[q])b[i++] = a[q++];
 else b[i++] = a[p++];
}
if(p<=mid)t = p;
else t = q;
while(i < end - start + 1)b[i++] = a[t++];
for(i = 0;i <end - start + 1;i++)
a[start + i] = b[i]; 
}
 
 void UnSort(int a[],int start,int end)
 {
 int mid = (start+end)/2; 
 if(start<end)
 {
 UnSort(a,start,mid);
 UnSort(a,mid+1,end); 
 Sort(a,start,end);     
 }
 }                                                 
int main()
{
 int a[10001],i,N;
 N = ReadIn(a);
  UnSort(a,0,N-1);
   for(i = 0;i < N;i++)
   printf("%d ",a[i]);
 return 0;
}