java 算法之归并排序详解及实现代码

时间:2021-05-19

java 算法之归并排序详解

一、思想

归并排序:将一个数组排序,可以先(递归地)将它分成两半部份分别排序,然后将结果归并起来;

二、概念

归并:将两个有序的数组归并成一个更大的有序数组;

三、特点

优点:能够保证将任意长度为N的数组排序所需要的时间和NlogN成正比;

缺点:需要额外的空间和N成正比;

四、实现方法

将两个不同的有序数组归并到第三个数组中;

先将前半部分排序,在将后半部分排序,然后在数组中移动元素而不需要使用额外的空间;

五、代码

/** * 归并排序 * * @author pengcx * */ public class Merge extends Sort { /** 归并所需的辅助数组 */ private static Comparable[] aux; public static void main(String[] args) { String[] a = { "d", "a", "w", "b", "q" }; Merge.sort(a); show(a); } public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a, 0, a.length - 1); } /** * 排序数组的a[lo]至a[hi]元素 * * @param a * 数组a * @param lo * 最小元素位置lo * @param hi * 最大元素位置hi */ private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) { return; } // 计算数组中间位置 int mid = lo + (hi - lo) / 2; // 排序数组a左边的元素 sort(a, lo, mid); // 排序数组a右边的元素 sort(a, mid + 1, hi); // 合并数组a左边和右边的元素 merge(a, lo, mid, hi); } /** * 将数组a的a[lo]至a[mid]的元素与a[mid]至a[hi]的元素合并 * * @param a * 合并的数组a * @param lo * 最小数组元素lo * @param mid * 中间元素位置mid * @param hi * 最大元素位置hi */ public static void merge(Comparable[] a, int lo, int mid, int hi) { int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } for (int k = lo; k <= hi; k++) { // 如果左边的元素用尽,取右边的元素 if (i > mid) { a[k] = aux[j++]; } // 如果右边的元素用尽,取左边的元素 else if (j > hi) { a[k] = aux[i++]; } // 如果右半边的当前元素小于左半边的当前元素,取右半边元素 else if (less(aux[j], aux[i])) { a[k] = aux[j++]; } // 如果右半边的当前元素大于等于左半边的当前元素,取左半边元素 else { a[k] = aux[i++]; } } } }

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章