听说你还不会归并排序?
明确递归方法的功能边界;
得到递归的递推关系;
给定递归的终止条件。
递归方法均可按照这三步进行,切忌不要陷入递归实现的细节中。下面以归并排序算法的书写为例,来谈一下递归方法的具体写法。
private static void mergeSort(int[] arr,int left,int right);
/**
*
* @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++];
else
helpArr[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 == null || right == left)//终止条件
return ;
int mid = left + (right - left) / 2;//确定分割的边界
mergeSort(arr,left,mid);//对左半部分调用递归方法,使其有序
mergeSort(arr,mid + 1,right);//对右半部分调用递归方法,使其有序
merge(arr,left,mid,right);//合并左右两部分,使整个数组有序
}
/**
* 归并排序算法
* @param arr
*/
public static void mergeSort(int[] arr){
mergeSort(arr,0,arr.length - 1);//调用写好的递归版归并排序方法
}
时间复杂度:一个算法执行所消耗的时间;
空间复杂度:运行完一个算法所需的内存大小;
原地排序:在排序过程中不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
非原地排序:需要利用额外的数组来辅助排序。
稳定排序:如果 a 原本在 b 的前面,且 a == b,排序之后 a 仍然在 b 的前面,则为稳定排序。
非稳定排序:如果 a 原本在 b 的前面,且 a == b,排序之后 a 可能不在 b 的前面,则为非稳定排序。
下面我们分析下归并排序算法的性能。
空间复杂度分析:在排序过程中使用了一个与原数组等长的辅助数组,估空间复杂度为O(n)。
稳定性分析:由排序过程可以知道,归并排序是一种稳定排序。
是否原地排序:排序过程中用到了辅助数组,所以是非原地排序。
【END】
更多精彩推荐
☞
☞
☞
☞