归并排序
归并：将两个或两个以上的有序表组合成一个新有序表
主要的思想:划分，求解子问题，综合解
利用递归的分治方法：
1、将原序列细分，直到成为单个元素
2、在将分割后的序列一层一层地按顺序合并,完成排序。
细分通过不断深入递归完成，合并通过递归一层层返回完成
伪代码：
算法分析：
时间效率：O(nlog2n)
空间效率：O(n)
稳 定 性：稳定
C语言实现归并排序
源代码：
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>
int N=0;
void printArr(int *a,int n); //打印数组
void merge(int arr[],int low,int m,int high);
void mergesort(int arr[],int left,int right);
int main()
{
srand((unsigned)time(NULL));
int *arr;
printf("请输入数组的长度：");
scanf("%d",&N);
arr=(int *)malloc(N*sizeof(int)); //生成长度为N的数组
for(int i=0;i<N;i++) //把1-100的随机数赋值给数组arr
{
arr[i]=rand()%100+1;
}
printf("排序前：\n");
printArr(arr,N);
printf("归并排序后：\n");
mergesort(arr,0,N-1);
printArr(arr,N);
return 0;
}
void printArr(int *a,int n) //打印数组
{
for(int i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
//arr[low]~arr[m] 和 arr[m+1]~arr[high]是两个有序序列
//将两个子序列合并为一个总的有序的序列
void merge(int arr[],int low,int m,int high)
{
int *arr1; //arr1为辅助数组
arr1=(int *)malloc(N*sizeof(int));
int i,j,k;
i=low;
j=m+1;
k=low;
while((i<=m)&&(j<=high)) //对两个有序序列中的记录排序
{
if(arr[i]<=arr[j])
arr1[k++]=arr[i++];
else
arr1[k++]=arr[j++];
}
while(i<=m) //如果第一个序列未检测完，将第一个序列后面所有元素加到合并的序列中
arr1[k++]=arr[i++];
while(j<=high) //如果第二个序列未检测完，将第二个序列后面所有元素加到合并的序列中
arr1[k++]=arr[j++];
for ( i = low; i <=high; i++) //将排列好的序列复制回原数组
arr[i]=arr1[i];
free(arr1); //释放辅助数组arr1的空间
}
void mergesort(int arr[],int left,int right)
{
if(left<right) //至少包含两个元素
{
int q=(left+right)/2; //均分为两份进行合并排序
mergesort(arr,left,q); //左边的进行合并排序，即left->q，包括i都是左边负责
mergesort(arr,q+1,right); //右边的进行合并排序，即q+1->right,包括right都是右边负责排序
merge(arr,left,q,right); //将已排序的两部分合并
}
}
运行结果：
Java实现归并排序
源代码：
import java.util.Random;
public class Gbsort {
public static void main(String args[]) {
int a[]=new int[10]; //声明创建长度为10的一维数组
Random ran=new Random();
int i;
//生成随机数组并输出
for(i=0;i<a.length;i++)
{
a[i]=ran.nextInt(1000)+1; // 把范围为1-1000的随机整数复制给a[i]
System.out.print(a[i]+" "); // 输出a[i]
}
System.out.println();
mergesort(a,0,a.length-1);
System.out.println("归并排序后：");
for(int j:a) //遍历排序后的数组
{
System.out.print(j+" ");
}
}
//arr[low]~arr[m] 和 arr[m+1]~arr[high]是两个有序序列
//将两个子序列合并为一个总的有序的序列
public static void merge(int arr[],int low,int m,int high)
{
int arr1[]=new int [arr.length]; //arr1为辅助数组
int i,j,k;
i=low;
j=m+1;
k=low;
while((i<=m)&&(j<=high)) //对两个有序序列中的记录排序
{
if(arr[i]<=arr[j])arr1[k++]=arr[i++];
else arr1[k++]=arr[j++];
}
while(i<=m)arr1[k++]=arr[i++]; //如果第一个序列未检测完，将第一个序列后面所有元素加到合并的序列中
while(j<=high)arr1[k++]=arr[j++]; //如果第二个序列未检测完，将第二个序列后面所有元素加到合并的序列中
for ( i = low; i <=high; i++) //将排列好的序列复制回原数组
arr[i]=arr1[i];
}
public static void mergesort(int arr[],int l,int r) {
if(l<r) //至少包含两个元素
{
int q=(l+r)/2;
mergesort(arr,l,q);
mergesort(arr,q+1,r);
merge(arr,l,q,r);
}
}
}
运行结果：