java中归并排序和Master公式详解

java中归并排序和Master公式详解

目录基本思想实现对数器验证递归时间复杂度计算 Master 公式总结

基本思想

归并排序采取分治的思想进行排序，借用一张图片说明一下

将n个元素从中间切开,分成两部分。(左边可能比右边多1个数) 将步骤1分成的两部分,再分别进行递归分解。直到所有部分的元素个数都为1。 从最底层开始逐步合并两个排好序的数列。优点在于，分治之后，合并排序的过程时间复杂度是O（N）（只需要扫描一遍就可以将两个有序的数组合并成一个有序数组）

实现

public static void MergeSort(int[] arr,int l , int r) {

if (l == r || r < 0){

return;

}

int middle = l+(r-l)/2; //取中值，可以防止达到Integer.MaxValue 溢出

MergeSort(arr,l,middle);

MergeSort(arr,middle+1,r);

sort(arr,l,middle,r);

}

/**

*

* @param arr 等待排序的数组

* @param l 左数组第一个指针

* @param middle 分割左右数组

* @param r 右数组最后一个指针

*/

private static void sort(int[] arr, int l, int middle, int r) {

int[] temp = new int[arr.length];

System.arraycopy(arr, 0, temp, 0, arr.length);

int right_first = middle+1;

int tempIndex = l;

while (l <= middle && right_first <= r){

if (temp[tempIndex] < temp[right_first]){

arr[l++] = temp[tempIndex++];

}else {

arr[l++] = temp[right_first++];

}

}

while (tempIndex <= middle){

arr[l++] = temp[tempIndex++];

}

while (right_first <= r ){

arr[l++] = temp[right_first++];

}

}

对数器验证

我们可以写个对数器，使用暴力排序的方式验证我们的排序方法是否准确

//生成1-100内随机数组

public static int[] getParamArrays(){

int[] result = new int[(int) (Math.random() * 100)];

//随机生成数

for (int i = 0; i < result.length; i++) {

result[i] = (int) (Math.random() * 100);

}

return result;

}

public static void main(String[] args){

for (int i = 0; i < 1000000; i++) {

int[] nums = getParamArrays();

int[] temp = nums;

MergeSort(nums,0,nums.length-1);

Arrays.sort(temp);

//通过自定义比较次数，对随机数组进行排序验证正确性

if (!nums.equals(temp)){

System.out.println("wrong");

}

}

System.out.println("end");

}

递归时间复杂度计算 Master 公式

形如T(N) = a * T(N/b) + O(N^d)(其中的a、b、d都是常数)的递归函数，可以直接通过Master公式来确定时间复杂度如果 log(b,a) < d，复杂度为O(N^d)如果 log(b,BXMQwa) > d，复杂度为O(N^log(b,a))如果 log(b,a) == d，复杂度为O(N^d * logN)此公式适用于子递归规模相等的情况下

a表示递归的次数也就是生成的子问题数，b表示每次递归是原来的1/b之一个规模，O(N^d) 表示分解和合并所要花费的时间之和（除开递归的复杂度）此处就是 T(N)= 2*T(N/2)+O(N^1) 适用于第三种情况 复杂度为 O（nlogn）

总结

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。