成为VIP
本文介绍了归并排序的基本思想，递归方法的一般写法，最后一步步手写归并排序，并对其性能进行了分析。
基本思想
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。即先使每个子序列有序，再将已有序的子序列合并，得到完全有序的序列。这里给出一种递归形式的归并排序实现。
递归方法的一般写法
递归方法的书写主要有三步：
递归方法均可按照这三步进行，切忌不要陷入递归实现的细节中。下面以归并排序算法的书写为例，来谈一下递归方法的具体写法。
手写归并排序
首先，明确递归方法的功能，这里我们定义方法的功能为，给定一个数组及左右边界，方法完成数组边界内元素的排序，如下：
private static void mergeSort(int[] arr,int left,int right)；先假设我们已经有了这么一个方法，不用管具体的实现。
接着，寻找递推关系，什么是递推关系呢？就是如何由子问题的求解，来得到原问题的求解，还是举例说明，有如下的数组：
原始数组
我们将其拆分为左右两部分，如下：
拆分数组
递推关系就是，假如左右两部分都已经有序了，如何使整个数组有序？这个问题其实就是给定了一个数组，数组的左半部分有序，右半部分也有序，如何使整个数组有序？
首先，定义两个指针，分别指向左侧部分起始位置和右侧部分起始位置，同时创建一个辅助数组和指向其初始位置的辅助指针：
定义指针及辅助数组
接着比较，左指针和右指针所对应的元素的大小，较小的元素填充至辅助数组，同时其对应的指针和辅助指针均加1，如下：
比较并填充辅助数组
依次进行，直至某左指针指向中间位置或者右指针指向数组的末尾，此时要将将剩余的元素填充至辅助数组。所有的元素填充完成后，再将辅助数组中的元素填充回原数组即可。具体的代码如下：
/**** @param arr 要合并的数组* @param left 左边界* @param mid 中间的分界* @param right 右边界*/private static void merge(int[] arr,int left,int mid,int right){int helpArr = new int[right - left + 1];//首先定义一个辅助数组int lPoint = left;//左指针int rPoint = mid + 1;//右指针int i = 0;//辅助指针while(lPoint <= mid && rPoint <= right){//比较并填充辅助数组if(arr[lPoint] <= arr[rPoint])helpArr[i++] = arr[lPoint++];elsehelpArr[i++] = arr[rPoint++];}while(lPoint <= mid){//将剩余元素填充至辅助数组helpArr[i++] = arr[lPoint++];}while(rPoint <= right){helpArr[i++] = arr[rPoint++];}for(int j = 0;j < helpArr.length;j ++){//将辅助数组中的元素回填至原数组arr[left + j] = helpArr[j];}}
最后，确定终止条件，一般是数组为空或者数组中只有一个元素，返回即可。
现在我们可以写出整个归并排序的代码了，如下：
private static void mergeSort(int[] arr,int left,int right){if(arr == || right == left)//终止条件return ;int mid = left + (right - left) / 2;//确定分割的边界mergeSort(arr,left,mid);//对左半部分调用递归方法，使其有序mergeSort(arr,mid + 1,right);//对右半部分调用递归方法，使其有序merge(arr,left,mid,right);//合并左右两部分，使整个数组有序}
为了保证形式的统一qsort函数，再对函数进行一下封装，如下，这就是我们的归并排序了。
/*** 归并排序算法* @param arr*/public static void mergeSort(int[] arr){mergeSort(arr,0,arr.length - 1);//调用写好的递归版归并排序方法}
至此，我们便完成了归并排序算法的代码实现。
性能分析
在分析归并排序算法性能之前，先介绍几个基础的概念。
下面我们分析下归并排序算法的性能。
首先是时间复杂度。归并排序算法在排序时首先将问题进行分解，然后解决子问题，再合并，所以总时间=分解时间+解决子问题时间+合并时间。分解时间就是把一个数组分解为左右两部分，时间为一常数qsort函数，即O(1)；解决子问题时间是两个递归方法，把一个规模为n的问题分成两个规模分别为n/2的子问题，时间为2T(n/2)；合并时间复杂度为O(n)。所以总时间T(n)=2T(n/2)+O(n)。这个递归问题的时间复杂度可以用下面的公式来计算
递归函数的时间复杂度计算公式
这个公式可针对形如：T(n) = aT(n/b) + f(n)的递归方程进行时间复杂度求解。带入可知，归并排序的时间复杂度为O(nlogn)。此外在最坏、最佳、平均情况下归并排序时间复杂度均为O(nlogn)。
本文源码已同步至github，地址：。
限时特惠：本站每日持续更新海量展厅资源，一年会员只需29.9元，全站资源免费下载
站长微信：zhanting688
