vlambda博客
学习文章列表

归并排序的思想

可以分为两步，【分】和【合】

1，【分】：把待排序的数组划分成左右两个区间，左右两个区间继续划分，直到数组不能够再划分为止。这个过程我们可以用递归。

那么问题来了，怎么判断数组无法再进行划分了？

数组中只有一个元素的时候就无法进行划分了。这也是递归的终止条件。（此处敲黑板！！！）

2，【合】：当数组区间不能再划分的时候开始进行有序合并。

我们来看例子进行详解：

Step1：

定义 low=0（数组的初始位置下标）

high=array.length-1（数组最后一位数据的下标，array.length为数组长度）

mid=(low+high)/2

划分规则如下：

将low~mid划分为左区间，mid+1~high划分为右区间，第一次划分完结果如下：

Step2:

Step3:

再把两个长度为2的数组合并成一个数组。

分别用两个指针指向两个数组初始位置，比较两个指针指向数据的大小，较小的数据排到前面放入新数组后，排完后相应数组的指针向后移动，继续比较，直到两个数组分别到各自数组最后一位。

用以上连两个数组合并成一个数组举例，

好了，我们整体代码如下：

 public void mergeSort(int[] array){ int[] newArray=new int[array.length]; dealMerge(array,0,array.length-1,newArray); }    //处理整个递归和排序过程 public void dealMerge(int[] array,int low,int high,int[] newArray){ if(low>=high){ return; } int mid=(low+high)/2; //分 dealMerge(array,low,mid,newArray); dealMerge(array,mid+1,high,newArray); sort(array,low,mid,high,newArray); //合       //排序后，将辅助数组中对应区间的数据拷贝到原数组相应区间 for (int i = low; i <=high ; i++) { array[i]=newArray[i]; } } public void sort(int[] array,int low,int mid,int high,int[] newArray){ int i=low; int j=mid+1; int k=low; while(i<=mid && j<=high){ if(array[i]<=array[j]){ newArray[k++]=array[i++]; }else{ newArray[k++]=array[j++]; } } while(i<=mid){ newArray[k++]=array[i++]; } while(j<=high){ newArray[k++]=array[j++]; } }

这里需要讲解一下，合并数组的时候两个指针的边界需要注意下，分别为划分数组时两个数组的区间的范围。

i=low  ， i<=mid

j=mid+1 ，j<=high

首先要明确，归并排序计算时间复杂度的核心在于，排序的时候元素的比较次数；

还是上面的例子，整个归并过程可以用树状图来描述，我们来看下整个函数大致调用过程：

这里注意，每次执行完两个mergeSort后才开始合并两个数组进行排序，所以分层讨论更容易计算时间复杂度。

对于长度为4的数组来说，每次除以2进行划分，总共划分log(4)即2层，每一层数组的个数为2^k（k为层数, 自顶向下从0开始排序），每一层排序需要比较的次数为：每一层数组的个数*数组的长度 =2^k*2^(2-k)=2^2

这个过程中我们申请了n个空间来辅助排序，所以空间复杂度为O(n)。

本文写的算法是稳定的，排序后相同的关键字不会改变其相对次序。