package altogramics.sort.merge;
import altogramics.sort.AbstractSort;
import java.util.Arrays;
public class MergeSort extends AbstractSort {
/**
* 始終O(nlogn)，代價是需要內(nèi)存額外空間
* <p>
* 作為一種典型的分而治之思想的算法應(yīng)用铆隘，歸并排序的實現(xiàn)由兩種方法：
* 1.自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）
* 2.自下而上的迭代
* <p>
* 穩(wěn)定排序
*/
@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) {
//開辟額外大集合弊仪，設(shè)置指針
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++];
}
}
//左側(cè)小集合還有剩余熙卡，依次放入大集合尾部
while (p1 <= mid) {
tempArray[p++] = array[p1++];
}
//右側(cè)小集合還有剩余杖刷，依次放入大集合尾部
while (p2 <= end) {
tempArray[p++] = array[p2++];
}
//把大集合的元素復(fù)制回原數(shù)組
for (int i = 0; i < tempArray.length; i++) {
array[i + start] = tempArray[i];
}
// return tempArray;
}
}
排序算法Java版（2）--歸并排序
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來昂验，“玉大人捂敌，你說我怎么就攤上這事〖惹伲” “怎么了占婉？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長甫恩。 經(jīng)常有香客問我逆济，道長，這世上最難降的妖魔是什么磺箕？ 我笑而不...
- 正文 為了忘掉前任奖慌，我火速辦了婚禮，結(jié)果婚禮上松靡，老公的妹妹穿的比我還像新娘升薯。我一直安慰自己，他們只是感情好击困，可當(dāng)我...
- 文/花漫 我一把揭開白布涎劈。 她就那樣靜靜地躺著，像睡著了一般阅茶。 火紅的嫁衣襯著肌膚如雪蛛枚。 梳的紋絲不亂的頭發(fā)上，一...
- 文/蒼蘭香墨 我猛地睜開眼溉贿，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了浦旱？” 一聲冷哼從身側(cè)響起宇色，我...
- 正文 年R本政府宣布，位于F島的核電站博投，受9級特大地震影響绸贡，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜毅哗，卻給世界環(huán)境...
- 文/蒙蒙 一听怕、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧虑绵，春花似錦尿瞭、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至捕发，卻和暖如春疏旨，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背扎酷。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 前言 本文總結(jié)了常用的全部排序算法，內(nèi)容包括： 排序算法的定義和思路 排序算法的代碼實現(xiàn)：Python和Java惫企，...
- 接下來準(zhǔn)備學(xué)習(xí)一下歸并排序去別的blog看了一段撕瞧，很多博客概括介紹歸并的時候是這樣子的： 基本理念:分治思想（di...
- 算法描述 使用歸并排序進行升序排列。 示例： 算法設(shè)計 基本思路：借助額外空間狞尔，合并兩個有序數(shù)組丛版，得到更長的有序數(shù)...
- 【歸并排序算法詳解】Java/Go/Python/JS/C不同語言實現(xiàn) 說明 歸并排序（Merge Sort）算法...
