歸并排序詳解

一奶赔、概述

????歸并排序是建立在歸并操作上的一種有效的排序算法惋嚎,該算法是采用分治法(Divide and Conquer)的一個(gè)典型應(yīng)用。

????將已有序的子序列合并纺阔,得到完全有序的序列瘸彤;即先使每個(gè)子序列有序,再使子序列段之間有序笛钝。將兩個(gè)有序表合并成一個(gè)有序表质况,稱為二路歸并愕宋。

二、歸并排序的基本思想

????將待排序序列R[0...n-1]看成是n個(gè)長度為1的有序序列结榄,將相鄰的有序表成對歸并中贝,得到n/2個(gè)長度為2的有序表;將這些有序序列再次歸并臼朗,得到n/4個(gè)長度為4的有序序列邻寿;如此反復(fù),最后得到一個(gè)長度為n的有序序列视哑。

歸并排序需要做兩件事:

1)分解:將序列每次折半劃分

2)合并:將劃分后的序列段兩兩合并后排序

如何合并绣否?

????在每次合并過程中,都是對兩個(gè)有序的序列段進(jìn)行合并挡毅,然后再排序蒜撮。這兩個(gè)有序的序列段分別為R[low, mid]和R[mid+1, high],先將它們合并到一個(gè)局部的暫存數(shù)組R2中跪呈,待合并完成后再將R2復(fù)制回R中段磨。

????每次從兩個(gè)段中取出一個(gè)記錄進(jìn)行關(guān)鍵字的比較,將較小者放入R2中耗绿,最后將各段中余下的部分直接復(fù)制到R2中苹支。經(jīng)過這樣的過程,R2已經(jīng)是一個(gè)有序的序列误阻,再將其復(fù)制回R中债蜜,一次合并排序就完成了。

在某趟歸并中究反,設(shè)各子表的長度為gap策幼,則歸并前R[0...n-1]中共有n/gap個(gè)有序的子表:R[0...gap-1], R[gap...2*gap-1], ... , R[(n/gap)*gap ... n-1]。

在將相鄰的子表歸并時(shí)奴紧,需要對表的特殊情況進(jìn)行處理:

1)若子表個(gè)數(shù)為奇數(shù),最后一個(gè)子表無須和其他子表歸并(即本趟處理輪空)晶丘;

2)若子表個(gè)數(shù)為偶數(shù)黍氮,到最后一對子表中后一個(gè)子表區(qū)間的上限為n-1;

三浅浮、排序性能

時(shí)間復(fù)雜度:歸并排序的形式就是一棵二叉樹沫浆,需要遍歷的次數(shù)就是二叉樹的深度,時(shí)間復(fù)雜度是O(nlogn)滚秩。

空間復(fù)雜度:算法處理過程中专执,需要一個(gè)大小為n的臨時(shí)存儲空間用來保存合并序列。

算法穩(wěn)定性:在歸并排序中郁油,相等元素的順序不會改變本股,所以它是穩(wěn)定的算法攀痊。

總結(jié):

1)時(shí)間復(fù)雜度:O(nlogn)

2)空間復(fù)雜度:O(n)

3)穩(wěn)定性:穩(wěn)定

4)復(fù)雜性:較復(fù)雜

四、選擇對比

1)空間復(fù)雜度考慮:選擇優(yōu)先級為[堆排序>快速排序>歸并排序]拄显。

2)穩(wěn)定性考慮:應(yīng)選歸并排序苟径,堆排序和快速排序都是不穩(wěn)定的。

3)平均排序速度考慮:應(yīng)選快速排序躬审。

五棘街、代碼實(shí)現(xiàn)

import java.util.Arrays;

/**

* 歸并排序

* 效率O(nlogn),歸并的最佳承边、平均和最糟用例效率之間沒有差異遭殉,適用于排序大列表,基于分治法博助。

*/

public class MergeSort {

????public static void main(String[] args) {

????????int[] array = {9, 1, 5, 3, 4, 2, 6, 8, 7};

????????MergeSort merge = new MergeSort();

????????System.out.println("排序前:"+Arrays.toString(array));

????????merge.sort(array);

????????System.out.println("排序后:"+Arrays.toString(array));

????}

????private static int[] sort(int[] list){

????????for(int gap = 1;gap <list.length; gap = 2*gap){

????????????MergePass(list,gap,list.length);

????????????System.out.println("gap="+gap+":"+Arrays.toString(list));

????????}

????????return list;

????}

????private static void MergePass(int[] arr,int gap,int length){

????????int i=0;

????????// 歸并gap長度的兩個(gè)相鄰子表

????????for(i=0;i+2*gap-1 < length;i = i+2*gap){

????????????Merge(arr, i, i + gap - 1, i + 2 * gap - 1);

????????}

????????// 余下兩個(gè)子表险污,后者長度小于gap

????????if (i + gap - 1 < length) {

????????????Merge(arr, i, i + gap - 1, length - 1);

????????}

????}

????private static void Merge(int[] arr,int low,int mid,int high){

????????int i=low;// i是第一段序列的下標(biāo)

????????int j = mid +1;// j是第二段序列的下標(biāo)

????????int k = 0;// k是臨時(shí)存放合并序列的下標(biāo)

????????int[] array2 = new int[high - low + 1]; // array2是臨時(shí)合并序列

????????// 掃描第一段和第二段序列,直到有一個(gè)掃描結(jié)束

????????while (i <= mid && j <= high) {

????????????// 判斷第一段和第二段取出的數(shù)哪個(gè)更小翔始,將其存入合并序列罗心,并繼續(xù)向下掃描

????????????if (arr[i] <= arr[j]) {

????????????????array2[k] = arr[i];

????????????????i++;

????????????????k++;

????????????} else {

????????????????array2[k] = arr[j];

????????????????j++;

????????????????k++;

????????????}

????????}

????????// 若第一段序列還沒掃描完,將其全部復(fù)制到合并序列

????????while(i <= mid){

????????????array2[k] = arr[i];

????????????i++;

????????????k++;

????????}

????????// 若第二段序列還沒掃描完城瞎,將其全部復(fù)制到合并序列

????????while(j <= high){

????????????array2[k] = arr[j];

????????????j++;

????????????k++;

????????}

????????// 將合并序列復(fù)制到原始序列中

????????for (k = 0, i = low; i <= high; i++, k++) {

????????????arr[i] = array2[k];

????????}

????}

}

運(yùn)行結(jié)果:

排序前: ? ? 9???1???5???3???4???2???6???8???7??

gap?=?1:???1???9???3???5???2???4???6???8???7??

gap?=?2:???1???3???5???9???2???4???6???8???7??

gap?=?4:???1???2???3???4???5???6???8???9???7??

gap?=?8:???1???2???3???4???5???6???7???8???9??

排序后: ? ? 1???2???3???4???5???6???7???8???9 ?

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末渤闷,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子脖镀,更是在濱河造成了極大的恐慌飒箭,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,406評論 6 503
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件蜒灰,死亡現(xiàn)場離奇詭異弦蹂,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)强窖,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,732評論 3 393
  • 文/潘曉璐 我一進(jìn)店門凸椿,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人翅溺,你說我怎么就攤上這事脑漫。” “怎么了咙崎?”我有些...
    開封第一講書人閱讀 163,711評論 0 353
  • 文/不壞的土叔 我叫張陵优幸,是天一觀的道長。 經(jīng)常有香客問我褪猛,道長网杆,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,380評論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮碳却,結(jié)果婚禮上队秩,老公的妹妹穿的比我還像新娘。我一直安慰自己追城,他們只是感情好刹碾,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,432評論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著座柱,像睡著了一般迷帜。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上色洞,一...
    開封第一講書人閱讀 51,301評論 1 301
  • 那天戏锹,我揣著相機(jī)與錄音,去河邊找鬼火诸。 笑死锦针,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的置蜀。 我是一名探鬼主播奈搜,決...
    沈念sama閱讀 40,145評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼盯荤!你這毒婦竟也來了馋吗?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,008評論 0 276
  • 序言:老撾萬榮一對情侶失蹤秋秤,失蹤者是張志新(化名)和其女友劉穎宏粤,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體灼卢,經(jīng)...
    沈念sama閱讀 45,443評論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡绍哎,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,649評論 3 334
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了鞋真。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片崇堰。...
    茶點(diǎn)故事閱讀 39,795評論 1 347
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖涩咖,靈堂內(nèi)的尸體忽然破棺而出赶袄,到底是詐尸還是另有隱情,我是刑警寧澤抠藕,帶...
    沈念sama閱讀 35,501評論 5 345
  • 正文 年R本政府宣布,位于F島的核電站蒋困,受9級特大地震影響盾似,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,119評論 3 328
  • 文/蒙蒙 一零院、第九天 我趴在偏房一處隱蔽的房頂上張望溉跃。 院中可真熱鬧,春花似錦告抄、人聲如沸撰茎。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,731評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽龄糊。三九已至,卻和暖如春募疮,著一層夾襖步出監(jiān)牢的瞬間炫惩,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,865評論 1 269
  • 我被黑心中介騙來泰國打工阿浓, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留他嚷,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,899評論 2 370
  • 正文 我出身青樓芭毙,卻偏偏與公主長得像筋蓖,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子退敦,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,724評論 2 354

推薦閱讀更多精彩內(nèi)容