圖解排序算法(四)之歸并排序

簡介

歸并排序(MERGE-SORT)是利用歸并的思想實現(xiàn)的排序方法,該算法采用經(jīng)典的分治(divide-and-conquer)策略(分治法將問題分(divide)成一些小的問題然后遞歸求解,而治(conquer)的階段則將分的階段得到的各答案"修補"在一起没宾,即分而治之)课舍。

分而治之

可以看到這種結(jié)構(gòu)很像一棵完全二叉樹膛壹,本文的歸并排序我們采用遞歸去實現(xiàn)(也可采用迭代的方式去實現(xiàn))。分階段可以理解為就是遞歸拆分子序列的過程良漱,遞歸深度為log2n愧口。

合并相鄰有序子序列

再來看看治階段,我們需要將兩個已經(jīng)有序的子序列合并成一個有序序列类茂,比如上圖中的最后一次合并耍属,要將[4,5,7,8]和[1,2,3,6]兩個已經(jīng)有序的子序列,合并為最終序列[1,2,3,4,5,6,7,8]巩检,來看下實現(xiàn)步驟厚骗。


代碼實現(xiàn)

package com.smart.algorithm.sort;

import java.util.Arrays;

/**
 * Created by fc.w on 2017/10/29.
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        sort(arr, 0, arr.length - 1);
        System.out.println("排序結(jié)果:" + Arrays.toString(arr));
    }

    public static void sort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(arr, left, mid);
            sort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[arr.length];
        int i = left; // 左序列
        int j = mid + 1; // 右序列
        int t = 0; // 臨時數(shù)組下標(biāo)
        while(i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }

        while (i <= mid) {
            temp[t++] = arr[i++];
        }
        while (j <= right) {
            temp[t++] = arr[j++];
        }

        t = 0;
        while (left <= right) {
            arr[left++] = temp[t++];
        }

    }

}

輸出

排序結(jié)果:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

總結(jié)

歸并排序是穩(wěn)定排序,它也是一種十分高效的排序兢哭,能利用完全二叉樹特性的排序一般性能都不會太差领舰。java中Arrays.sort()采用了一種名為TimSort的排序算法,就是歸并排序的優(yōu)化版本。從上文的圖中可看出冲秽,每次合并操作的平均時間復(fù)雜度為O(n)舍咖,而完全二叉樹的深度為|log2n|★鄙#總的平均時間復(fù)雜度為O(nlogn)排霉。而且,歸并排序的最好民轴,最壞攻柠,平均時間復(fù)雜度均為O(nlogn)。

參考資料

[1]From 圖解排序算法(四)之歸并排序

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末后裸,一起剝皮案震驚了整個濱河市瑰钮,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌微驶,老刑警劉巖浪谴,帶你破解...
    沈念sama閱讀 211,496評論 6 491
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異祈搜,居然都是意外死亡较店,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,187評論 3 385
  • 文/潘曉璐 我一進(jìn)店門容燕,熙熙樓的掌柜王于貴愁眉苦臉地迎上來梁呈,“玉大人,你說我怎么就攤上這事蘸秘」倏ǎ” “怎么了?”我有些...
    開封第一講書人閱讀 157,091評論 0 348
  • 文/不壞的土叔 我叫張陵醋虏,是天一觀的道長寻咒。 經(jīng)常有香客問我,道長颈嚼,這世上最難降的妖魔是什么毛秘? 我笑而不...
    開封第一講書人閱讀 56,458評論 1 283
  • 正文 為了忘掉前任,我火速辦了婚禮阻课,結(jié)果婚禮上叫挟,老公的妹妹穿的比我還像新娘。我一直安慰自己限煞,他們只是感情好抹恳,可當(dāng)我...
    茶點故事閱讀 65,542評論 6 385
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著署驻,像睡著了一般奋献。 火紅的嫁衣襯著肌膚如雪健霹。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,802評論 1 290
  • 那天瓶蚂,我揣著相機與錄音糖埋,去河邊找鬼。 笑死扬跋,一個胖子當(dāng)著我的面吹牛阶捆,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播钦听,決...
    沈念sama閱讀 38,945評論 3 407
  • 文/蒼蘭香墨 我猛地睜開眼洒试,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了朴上?” 一聲冷哼從身側(cè)響起垒棋,我...
    開封第一講書人閱讀 37,709評論 0 266
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎痪宰,沒想到半個月后叼架,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,158評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡衣撬,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,502評論 2 327
  • 正文 我和宋清朗相戀三年乖订,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片具练。...
    茶點故事閱讀 38,637評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡乍构,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出扛点,到底是詐尸還是另有隱情哥遮,我是刑警寧澤,帶...
    沈念sama閱讀 34,300評論 4 329
  • 正文 年R本政府宣布陵究,位于F島的核電站眠饮,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏铜邮。R本人自食惡果不足惜仪召,卻給世界環(huán)境...
    茶點故事閱讀 39,911評論 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望松蒜。 院中可真熱鬧扔茅,春花似錦、人聲如沸牍鞠。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,744評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽难述。三九已至萤晴,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間胁后,已是汗流浹背店读。 一陣腳步聲響...
    開封第一講書人閱讀 31,982評論 1 266
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留攀芯,地道東北人屯断。 一個月前我還...
    沈念sama閱讀 46,344評論 2 360
  • 正文 我出身青樓,卻偏偏與公主長得像侣诺,于是被迫代替她去往敵國和親殖演。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 43,500評論 2 348

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

  • 前言 本篇文章基本是從常用排序算法總結(jié)(一)快速排序引申而來年鸳,其中大部分代碼和描述都來自這兩篇文章趴久。 時間復(fù)雜度 ...
    王三的貓阿德閱讀 1,076評論 0 1
  • 常見的排序算法: 快速排序、堆排序搔确、歸并排序彼棍、選擇排序 插入排序、二分插入排序 冒泡排序膳算、雞尾酒排序 桶排序座硕、計數(shù)...
    晴空歌閱讀 761評論 0 12
  • 排序算法可以分為內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序涕蜂,而外部排序是因排序的數(shù)據(jù)很大华匾,一次不能容納...
    采姑娘的大白菜閱讀 389評論 0 0
  • 該系列文章主要是記錄下自己暑假這段時間的學(xué)習(xí)筆記,暑期也在實習(xí)宇葱,抽空學(xué)了很多瘦真,每個方面的知識我都會另起一篇博客去記...
    Yanci516閱讀 12,200評論 6 19
  • 簡單排序 冒泡排序:循環(huán)遍歷左右比較,較小者左移或較大者后移黍瞧; 選擇排序:在未排序序列中找到最小者元素一次放到已排...
    王然Gondole閱讀 1,423評論 0 2