java中归并排序及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");
}
形如
T(N) = a * T(N/b) + O(N^d)(其中的a、b、d都是常数)
的递归函数,可以直接通过Master公式来确定时间复杂度
如果 log(b,a) < d,复杂度为O(N^d)
如果 log(b,a) > 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)
关于java中归并排序及Master公式是什么问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注亿速云行业资讯频道了解更多相关知识。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。