最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
java 算法之归并排序详解及实现代码
时间:2022-06-29 01:35:02 编辑:袖梨 来源:一聚教程网
java 算法之归并排序详解
一、思想
归并排序:将一个数组排序,可以先(递归地)将它分成两半部份分别排序,然后将结果归并起来;
二、概念
归并:将两个有序的数组归并成一个更大的有序数组;
三、特点
优点:能够保证将任意长度为N的数组排序所需要的时间和NlogN成正比;
缺点:需要额外的空间和N成正比;
四、实现方法
将两个不同的有序数组归并到第三个数组中;
先将前半部分排序,在将后半部分排序,然后在数组中移动元素而不需要使用额外的空间;
五、代码
代码如下 | 复制代码 |
/** * 归并排序 * * @author pengcx * */ publicclassMergeextendsSort { /** 归并所需的辅助数组 */ privatestaticComparable[] aux;
publicstaticvoidmain(String[] args) { String[] a = {"d","a","w","b","q"}; Merge.sort(a); show(a); }
publicstaticvoidsort(Comparable[] a) { aux =newComparable[a.length]; sort(a,0, a.length -1); }
/** * 排序数组的a[lo]至a[hi]元素 * * @param a * 数组a * @param lo * 最小元素位置lo * @param hi * 最大元素位置hi */ privatestaticvoidsort(Comparable[] a,intlo,inthi) { if(hi <= lo) { return; }
// 计算数组中间位置 intmid = 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 */ publicstaticvoidmerge(Comparable[] a,intlo,intmid,inthi) { inti = lo, j = mid +1;
for(intk = lo; k <= hi; k++) { aux[k] = a[k]; }
for(intk = lo; k <= hi; k++) { // 如果左边的元素用尽,取右边的元素 if(i > mid) { a[k] = aux[j++]; } // 如果右边的元素用尽,取左边的元素 elseif(j > hi) { a[k] = aux[i++]; } // 如果右半边的当前元素小于左半边的当前元素,取右半边元素 elseif(less(aux[j], aux[i])) { a[k] = aux[j++]; } // 如果右半边的当前元素大于等于左半边的当前元素,取左半边元素 else{ a[k] = aux[i++]; } } } } |
相关文章
- 火影忍者怎么获得大招 05-03
- 星际战甲新手什么刀好 05-03
- 文明6秦始皇金字塔怎么加速 05-03
- 全民奇迹2龙骸巨剑怎么获得 05-03
- 星露谷物语鲟鱼怎么获得 05-03
- 长安幻想怎么转职 05-03