本篇内容介绍了“如何使用归并排序”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
归并排序是用分治思想,分治模式在每一层递归上有三个步骤:
分解(Divide):将n个元素分成个含n/2个元素的子序列。
解决(Conquer):用合并排序法对两个子序列递归的排序。
合并(Combine):合并两个已排序的子序列已得到排序结果。
如下图所示:
代码如下:
public static int[] sort(int[] arr) {
if (arr.length < 2) {
return arr;
}
int middle = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
//递归调用
return merge(sort(left), sort((right)));
}
private static int[] merge(int[] left, int[] right) {
int leftLength = left.length;
int rightLength = right.length;
int[] result = new int[leftLength + rightLength];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] > right[0]) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
} else {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
return result;
}
“如何使用归并排序”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/4074923/blog/5022735