package altogramics.sort.merge;
import altogramics.sort.AbstractSort;
import java.util.Arrays;
public class MergeSort extends AbstractSort {
/**
* 始终O(nlogn),代价是需要内存额外空间
* <p>
* 作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
* 1.自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法)
* 2.自下而上的迭代
* <p>
* 稳定排序
*/
@Override
public int[] onSort(int[] originalArray) {
try {
int[] copyArray = Arrays.copyOf(originalArray, originalArray.length);
exeSort(copyArray, 0, copyArray.length - 1);
return copyArray;
} catch (Exception e) {
throw new RuntimeException(e);
}
}
public void exeSort(int[] arr, int start, int end) {
if (start >= end) {
return;
}
int middle = (start + end) >> 1;
exeSort(arr, start, middle);
exeSort(arr, middle + 1, end);
merge(arr, start, middle, end);
}
protected void merge(int[] array, int start, int mid, int end) {
//开辟额外大集合,设置指针
int[] tempArray = new int[end - start + 1];
int p1 = start, p2 = mid + 1, p = 0;
while (p1 <= mid && p2 <= end) {
if (array[p1] <= array[p2]) {
tempArray[p++] = array[p1++];
} else {
tempArray[p++] = array[p2++];
}
}
//左侧小集合还有剩余,依次放入大集合尾部
while (p1 <= mid) {
tempArray[p++] = array[p1++];
}
//右侧小集合还有剩余,依次放入大集合尾部
while (p2 <= end) {
tempArray[p++] = array[p2++];
}
//把大集合的元素复制回原数组
for (int i = 0; i < tempArray.length; i++) {
array[i + start] = tempArray[i];
}
// return tempArray;
}
}
排序算法Java版(2)--归并排序
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 前言 本文总结了常用的全部排序算法,内容包括: 排序算法的定义和思路 排序算法的代码实现:Python和Java,...
- 算法描述 使用归并排序进行升序排列。 示例: 算法设计 基本思路:借助额外空间,合并两个有序数组,得到更长的有序数...
- 【归并排序算法详解】Java/Go/Python/JS/C不同语言实现 说明 归并排序(Merge Sort)算法...