/**
* 分治算法.
*/
public class MergeSort {
private MergeSort() {
throw new RuntimeException();
}
public static void sort(int[] array) {
if (null == array||array.length<2) {
return;
}
sort(0, array.length, array);
}
private static void sort(int start, int length, int[] array) {
if (length > 2) {
int middle = (int) Math.floor(length / 2);
sort(start, middle, array);
sort(start + middle, length - middle, array);
merge(start, middle, start + middle, length - middle, array);
} else if (length == 2) {
if (array[start+1]<array[start]){
array[start+1] = array[start+1]^array[start];
array[start] = array[start]^array[start+1];
array[start+1] = array[start+1]^array[start];
}
}
}
private static void merge(int aStart, int aLength, int bStart, int bLength, int[] array) {
int aSize = aStart + aLength;
int bSize = bStart + bLength;
while (aStart < aSize && bStart < bSize) {
int a = array[aStart];
int b = array[bStart];
if (b<a){
System.arraycopy(array, aStart, array, aStart + 1, bStart - aStart);
array[aStart] = b;
aStart++;
bStart++;
aSize++;
}else {
aStart++;
}
}
}
}
JAVA分治合并排序(MERGE-SORT)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。合并排序法是将两个（或两个...
- 耗时 公式中 n 为参与排序的个数，T(n) 为排序时间。 分析 由上面可以看出当 n 足够大时 n^2 会远远大...
- 核心思想：“分”与“合”。 主体流程 先将一个序列分成很多个不能再分割的子序列，将各个子序列分别排序后再将子序列合...
