import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr1 = {4,2,6,3,5};
System.out.println(Arrays.toString(arr1));
mergeSort(arr1,0,arr1.length-1);
System.out.println(Arrays.toString(arr1));
}
public static void mergeSort(int[] arr,int l,int r) {
//0 4
if (l<r) {
int q = (l+r)/2;
mergeSort(arr,l,q);
mergeSort(arr,q+1,r);
merge(arr,l,q,r);
}
}
/**
*
* @param arr 排序數(shù)組
* @param l 數(shù)組最左邊下標(biāo)
* @param q 數(shù)組中間位置下標(biāo)
* @param r 數(shù)組最右位置下標(biāo)
*/
public static void merge(int[] arr, int l, int q, int r) {
/**因?yàn)槊看吻懈詈笞筮呄聵?biāo)都是（l,q），右邊數(shù)組的下標(biāo)是(q+1,r)
* 所以左邊數(shù)組的元素個(gè)數(shù)就是q - l + 1
* 右邊的數(shù)組元素個(gè)數(shù)就是r - q
* **/
final int n1 = q-l+1;//切割后左邊數(shù)組的數(shù)據(jù)長(zhǎng)度
final int n2 = r-q;//切割后右邊數(shù)組的數(shù)據(jù)長(zhǎng)度
/**創(chuàng)建兩個(gè)新數(shù)組將切割后的數(shù)組分別放進(jìn)去烤惊，長(zhǎng)度加1是為了放置無(wú)窮大的數(shù)據(jù)標(biāo)志位**/
final int[] left = new int[n1+1];//加一操作是增加無(wú)窮大標(biāo)志位
final int[] right = new int[n2+1];//加一操作是增加無(wú)窮大標(biāo)志位
//兩個(gè)循環(huán)將數(shù)據(jù)添加至新數(shù)組中
/**左邊的數(shù)組下標(biāo)是從l到q**/
/**遍歷左邊的數(shù)組*/
for (int i = 0; i < n1; i++) {
left[i] = arr[l+i];
}
for (int i = 0; i < n2; i++) {
right[i] = arr[q+1+i];
}
//將最大的正整數(shù)放在兩個(gè)新數(shù)組的最后一位
left[n1] = Integer.MAX_VALUE;
right[n2] = Integer.MAX_VALUE;
int i = 0,j = 0;
//誰(shuí)小誰(shuí)放在前面
for (int k = l; k <= r; k++) {
if (left[i]<=right[j]) {
arr[k] = left[i];
i = i+1;
} else {
arr[k] = right[j];
j = j+1;
}
}
}
}
用Java實(shí)現(xiàn)歸并排序算法
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門胳螟，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人筹吐，你說(shuō)我怎么就攤上這事糖耸。” “怎么了骏令？”我有些...
- 文/不壞的土叔 我叫張陵蔬捷，是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我榔袋，道長(zhǎng)周拐，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任凰兑，我火速辦了婚禮妥粟，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘吏够。我一直安慰自己勾给，他們只是感情好滩报，可當(dāng)我...
- 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著播急，像睡著了一般脓钾。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上桩警，一...
- 那天可训，我揣著相機(jī)與錄音，去河邊找鬼捶枢。 笑死握截，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的烂叔。 我是一名探鬼主播谨胞，決...
- 文/蒼蘭香墨 我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼蒜鸡！你這毒婦竟也來(lái)了胯努？” 一聲冷哼從身側(cè)響起，我...
- 序言：老撾萬(wàn)榮一對(duì)情侶失蹤术瓮，失蹤者是張志新（化名）和其女友劉穎康聂，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體胞四，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡恬汁，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了辜伟。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片氓侧。...
- 正文 年R本政府宣布独郎，位于F島的核電站，受9級(jí)特大地震影響枚赡，放射性物質(zhì)發(fā)生泄漏氓癌。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一贫橙、第九天 我趴在偏房一處隱蔽的房頂上張望贪婉。 院中可真熱鬧，春花似錦卢肃、人聲如沸疲迂。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)尤蒿。三九已至郑气，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間优质，已是汗流浹背竣贪。 一陣腳步聲響...
- 正文 我出身青樓匕争，卻偏偏與公主長(zhǎng)得像避乏，于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子甘桑，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 概念 歸并排序是建立在歸并操作上的一種有效的排序算法拍皮。該算法是采用分治法（Divide and Conquer）的...
- 快速排序 快速排序（Quicksort） 是一種排序算法，平均時(shí)間復(fù)雜度為：O(n log n)跑杭，最壞需要 O(n...
- 在極客時(shí)間學(xué)習(xí)時(shí)铆帽，又遇到了歸并排序，這里給出Java的實(shí)現(xiàn)德谅，附有注解爹橱，以備后面學(xué)習(xí)查看 寫一個(gè)測(cè)試用例測(cè)試下: 打...
- 我總是那么愛(ài)回顧生活，總結(jié)目標(biāo)窄做，計(jì)劃方向愧驱。回顧這一生椭盏，中學(xué)時(shí)代為了自己夢(mèng)想中的學(xué)校组砚，不怕留級(jí)，接受培訓(xùn)最終如愿以償...
