很多情況下瘫寝，只要跟算法相關(guān)的可能都有現(xiàn)成的開(kāi)源工具包拿來(lái)就用蜒蕾，比如排序算法。

現(xiàn)實(shí)業(yè)務(wù)開(kāi)發(fā)時(shí)焕阿，為了提升效率咪啡，確實(shí)建議使用現(xiàn)成的成熟的開(kāi)源工具。

但是暮屡，我們?nèi)绻恢朗褂瞄_(kāi)源工具包的話撤摸，如果有一天你去面試被問(wèn)到的話...

所以，我們應(yīng)用抽點(diǎn)時(shí)間褒纲，去學(xué)習(xí)我們常用的工具包或框架的實(shí)現(xiàn)思想和細(xì)節(jié)准夷。以備急需。

這也就是我們需要不停學(xué)習(xí)的原因之一吧莺掠。

插入排序算法

排序算法場(chǎng)景不用多說(shuō)了衫嵌，比如棋牌游戲中一鍵排序撲克牌，比如電商系統(tǒng)按銷量從高到低排序等等彻秆。

排序算法實(shí)現(xiàn)有多種渐扮，比如插入排序论悴，希爾排序，快速排序墓律，冒泡排序膀估，歸并排序等等。排序算法其實(shí)大有講究耻讽，每一種算法在不同的輸入規(guī)模需要的時(shí)間均不一樣察纯。用專業(yè)術(shù)語(yǔ)來(lái)說(shuō)就是他們的時(shí)間復(fù)雜度不同。下面我們主要來(lái)看一下插入排序和歸并排序的實(shí)現(xiàn)原理和不同輸入規(guī)模下需要的計(jì)算時(shí)間针肥。

圖解原理

下面我們通過(guò)畫圖+文字方式來(lái)講解插入排序原理饼记。先假定某此會(huì)議有四個(gè)人，會(huì)議要求他們坐成一排慰枕，且按編號(hào)從左邊開(kāi)始從小到大排列具则，假定他們到場(chǎng)初始化坐位編號(hào)排序?yàn)?/span>:

?

現(xiàn)在需要按照會(huì)議要求按編號(hào)從小到大進(jìn)行排序具帮，其中一人就提議按照插入排序法方式進(jìn)行位置的調(diào)整，從第二位開(kāi)始（插入排序法一般從第二項(xiàng)開(kāi)始）進(jìn)行匪凡，具體如下：

?

編號(hào)5開(kāi)始調(diào)整座位：

?

?

編號(hào)3調(diào)整座位：

?

編號(hào)6調(diào)整座位：

?

?

可以看到病游，現(xiàn)在順序變成：

?

?

代碼實(shí)現(xiàn)

排序算法：

?

public static void insertSortAsc(Integer[] source) {    if (source == null || source.length < 1) {        return;    }    int len = source.length;    //i = 1表示從第二項(xiàng)開(kāi)始稠通，下標(biāo)從0開(kāi)始    for (int i = 1; i < len; i++) {        //當(dāng)前項(xiàng)        int currentVal = source[i];        //當(dāng)前項(xiàng)的前面項(xiàng)最大索引        int j = i - 1;        //j >= 0表示當(dāng)前存在哥們衬衬，需要繼續(xù)詢問(wèn)        //currentVal < source[j]表示詢問(wèn)你比我大么？        while (j >= 0 && currentVal < source[j]) {            //進(jìn)入這里表示前面項(xiàng)確實(shí)比我大            //source[j + 1] = source[j]表示那你往后挪一步            source[j + 1] = source[j];            //繼續(xù)向前詢問(wèn)            j--;        }        //前面哥們比自己小改橘，或者前面沒(méi)有哥們滋尉，回退一步回來(lái)坐下        source[j + 1] = currentVal;    }}

?

測(cè)試：

public static void main(String[] args) {
    Integer[] test = {7,5,3,6};
    System.out.println("排序前：" + JSON.toJSONString(test));    insertSortAsc(test);    System.out.println("排序后：" + JSON.toJSONString(test));}

?

輸出：

?

?

復(fù)雜度分析

插入排序算法的時(shí)間復(fù)雜度范圍為：?O(n) - O(n * n)，其中n為輸入項(xiàng)的數(shù)量唧龄，比如上面輸入項(xiàng)為4項(xiàng)，最好情況下時(shí)間復(fù)雜度為O(n)奸远。最好情況一般指輸入項(xiàng)本身已經(jīng)排好順序既棺。最差和平均情況時(shí)間復(fù)雜度為O(n * n)，最差情況一般指輸入項(xiàng)本身按目標(biāo)排序反向順序懒叛。時(shí)間一般指執(zhí)行所耗費(fèi)的時(shí)間

?

插入排序算法空間復(fù)雜度為O(1)丸冕，表示不管輸入項(xiàng)數(shù)量大小，運(yùn)行核心計(jì)算所需要的空間相較于其他排序算法來(lái)說(shuō)是固定的薛窥，空間一般指內(nèi)存使用胖烛。

歸并排序算法

歸并算法類似二分查找眼姐，它遵循分治法范疇，分治法的核心思想是將原問(wèn)題分解為幾個(gè)規(guī)模較小但類似于原問(wèn)題的子問(wèn)題佩番。然后通過(guò)遞歸的方式去求解這些子問(wèn)題众旗。最后一層一層的合并子問(wèn)題的解來(lái)得到原問(wèn)題的解。

分治法在每層遞歸一般有以下三個(gè)步驟：

分解：分解原問(wèn)題為若干子問(wèn)題

求解：遞歸求解子問(wèn)題

合并：合并子問(wèn)題的解得到原問(wèn)題的解

歸并排序算法實(shí)現(xiàn)分治法其原理如下：

分解：遞歸分解待排序的n個(gè)元素的序列/數(shù)組為n/2個(gè)子序列/數(shù)組

求解：遞歸排序一分為二的兩個(gè)子序列

合并：遞歸合并一分為二已經(jīng)排好序的序列

文字描述可能太抽象和枯燥趟畏，下面我們圖解算法方式講解算法的實(shí)現(xiàn)原理

圖解原理

我們復(fù)用上面的案例來(lái)講解通過(guò)歸并算法如何實(shí)現(xiàn)會(huì)議座位從左到右從小到大排序赋秀。

上面待排序項(xiàng)如下：

?

分解歸并排序如下：

?

上圖完全展示了歸并算法的核心思想绍弟，分解 -> 排序 -> 歸并樟遣。就拿5年碘，7屿衅，3，6排序來(lái)講解响迂，具體步驟如下：

分解：將5蔗彤，7然遏，3，6大致對(duì)半分解為兩組子問(wèn)題5秧倾，7和3那先，6胃榕，繼續(xù)將5苦掘，7大致按對(duì)半分解為兩組5和7鹤啡。同樣也將3递瑰，6按對(duì)半分解為3和6兩組子問(wèn)題，此時(shí)對(duì)n項(xiàng)輸入分解為6個(gè)子問(wèn)題來(lái)處理

求解：從低往上排序慎颗，例如7排序后得到7俯萎，5排序后得到5，然后進(jìn)行遞歸合并撇眯。

首次歸并將7熊榛，5歸并為一組来候，將3营搅，6歸并為一組。歸并過(guò)程進(jìn)行求解（排序）休蟹，將7赂弓，5排序得到5盈魁，7，將3珊膜，6排序得到3车柠，6。

繼續(xù)歸并將5溶褪，7和3猿妈，6歸并為5，7俯抖，3芬萍，6柬祠。歸并過(guò)程進(jìn)行求解（排序）所以最后得到3嗜愈，6蠕嫁，5，7迟赃。

合并：由于合并和求解在遞歸過(guò)程并行纤壁，所以合并操作在求解中已經(jīng)有所體現(xiàn)酌媒。

核心解釋：每次排序是將兩個(gè)子問(wèn)題進(jìn)行排序，每個(gè)子問(wèn)題實(shí)際是放到兩個(gè)序列/數(shù)組上的雨席，比如7和5這兩個(gè)分別放到不同的數(shù)組陡厘。然后在循環(huán)迭代體將這兩個(gè)進(jìn)行比較，把小的放前面谤饭，大的放后面保存到另一個(gè)數(shù)組中宜岛。

代碼實(shí)現(xiàn)

遞歸按n/2進(jìn)行分解，當(dāng)分解為最小子問(wèn)題時(shí)（遞歸到只有一個(gè)元素不可再分解時(shí)）辟汰，遞歸開(kāi)始回升帖汞，進(jìn)入歸并排序，回升一層催首，歸并排序一層：

/** * 通過(guò)分治算法實(shí)現(xiàn)歸并排序 * * @param source     需要排序的List * @param beginIndex 開(kāi)始下標(biāo) 從0開(kāi)始，包含開(kāi)始下標(biāo) * @param endIndex   結(jié)束下標(biāo)  從0開(kāi)始舶治， 包含結(jié)束下標(biāo) */public static void mergeSortAsc(List<Integer> source, int beginIndex, int endIndex) {    //當(dāng)前面一次遞歸只有一個(gè)元素時(shí)，開(kāi)始回升當(dāng)前遞歸    if (beginIndex < endIndex) {        int subIndex = (beginIndex + endIndex) / 2;        //排序左邊段惜浅，當(dāng)遞歸回升后左邊所有已經(jīng)排好序        mergeSortAsc(source, beginIndex, subIndex);        //排序右邊段，當(dāng)遞歸回升后右邊所有已經(jīng)排好序        mergeSortAsc(source, subIndex + 1, endIndex);        //合并并排序前面遞歸排好序的兩段        doMergeSortAsc(source, beginIndex, subIndex, endIndex);    }}

歸并排序：

private static void doMergeSortAsc(List<Integer> source, int beginIndex, int subBeginIndex, int endIndex) {
    if (SetsUtils.isEmpty(source)) {        return;    }    if (endIndex > source.size()) {        throw new RuntimeException("endIndex Not greater than source size");    }
    int num1 = subBeginIndex - beginIndex + 1;    int num2 = endIndex - subBeginIndex;
    List<Integer> left = SetsUtils.list(num1);    List<Integer> right = SetsUtils.list(num2);
    for (int i = 0; i < num1; i++) {        left.add(source.get(beginIndex + i));    }    left.add(num1, Integer.MAX_VALUE);
    for (int i = 0; i < num2; i++) {        right.add(source.get(subBeginIndex + i + 1));    }    right.add(num2, Integer.MAX_VALUE);

    int i = 0;    int j = 0;
    for (int k = beginIndex; k <= endIndex; k++) {        if (left.get(i) > right.get(j)) {            source.set(k, left.get(i));            i++;        } else {            source.set(k, right.get(j));            j++;        }    }}

測(cè)試：

?

public static void main(String[] args) {
    List<Integer> test = SetsUtils.list();    test.add(7);    test.add(5);    test.add(3);    test.add(6);
    System.out.println("排序前：" + JSON.toJSONString(test));    mergeSortAsc(test, 0, test.size() -1);    System.out.println("排序后：" + JSON.toJSONString(test));
}

?

輸出：

?

?

復(fù)雜度分析

歸并排序算法的時(shí)間復(fù)雜度為：?O(nlogn))画饥，其中n為輸入項(xiàng)的數(shù)量抖甘。時(shí)間一般指執(zhí)行所耗費(fèi)的時(shí)間

?

歸并排序算法空間復(fù)雜度為O(n)，輸入項(xiàng)數(shù)量越大艰额，運(yùn)行核心計(jì)算所需要的空間相較于其他排序算法來(lái)說(shuō)越大柄沮，空間一般指內(nèi)存使用祖搓。

對(duì)比

對(duì)比一般需要得出適用場(chǎng)景的結(jié)論棕硫，一般通過(guò)分析時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行定論哈扮，很多人喜歡討論時(shí)間換空間滑肉，空間換時(shí)間靶庙，這些都是一些術(shù)語(yǔ)而已六荒，進(jìn)一步是要詳細(xì)分析計(jì)算出算法的具體時(shí)間復(fù)雜度和空間復(fù)雜度掏击，然后得出結(jié)論灯变。

我們?nèi)绾卧诙喾N不同的排序算法中選擇一種算法添祸，其實(shí)者首先取決于我們的關(guān)注的刃泌，比如我們的計(jì)算機(jī)有足夠的空間去浪費(fèi)耙替，我們需要的是速度，例如電商網(wǎng)站的商品排序混坞。那么我們就應(yīng)該分析不同算法的時(shí)間復(fù)雜度然后進(jìn)行對(duì)比。相反爹凹，如果我們更多的關(guān)注內(nèi)存占用而不關(guān)心時(shí)間禾酱，例如大數(shù)據(jù)分析的任務(wù)調(diào)度颗管，那么我們就應(yīng)該分析不同算法的空間復(fù)雜度然后進(jìn)行對(duì)比垦江。由于時(shí)間問(wèn)題比吭，本篇不詳細(xì)計(jì)算插入排序和歸并排序的時(shí)間復(fù)雜度，后面再寫一篇文章進(jìn)行補(bǔ)充涛漂，筆者這里先給出答案：

1底哗、插入排序法和歸并排序法的時(shí)間復(fù)雜度對(duì)比取決于輸入規(guī)模

2跋选、當(dāng)輸入規(guī)模大于1W時(shí)歸并排序法優(yōu)于插入排序法

3坠韩、相反炼列，當(dāng)輸入規(guī)模小于1W時(shí)俭尖，插入排序法優(yōu)于歸并排序法

4稽犁、當(dāng)輸入規(guī)模達(dá)到10W以上時(shí)熊赖，不推薦使用插入排序法

5震鹉、當(dāng)輸入規(guī)模達(dá)到20W以上時(shí)，不推薦使用歸并排序法

對(duì)比代碼

public static void main(String[] args) {    List<Integer> test = SetsUtils.list();    int i = 10;    Random r = new Random();    while (i++ < 50000) {        test.add(r.nextInt(10000));    }    List<Integer> test1 = new ArrayList<>(test);    List<Integer> test2 = new ArrayList<>(test);
    long t = System.currentTimeMillis();
    System.out.println(JSON.toJSONString(test1));    mergeSortAsc(test1, 0, test1.size() - 1);    System.out.println(JSON.toJSONString(test1));
    long t2 = System.currentTimeMillis();
    System.out.println("歸并排序算法耗時(shí)：" + (t2 - t) + "ms");
    long t3 = System.currentTimeMillis();
    System.out.println(JSON.toJSONString(test2));    insertSortAsc(test2);    System.out.println(JSON.toJSONString(test2));
    long t4 = System.currentTimeMillis();
    System.out.println("插入排序算法耗時(shí)：" + (t4 - t3) + "ms");}

?

對(duì)比結(jié)果

?