寫在前邊

排序?qū)τ诿總€(gè)開發(fā)者來(lái)講，都多多少少知道幾個(gè)經(jīng)典的排序算法，比如我們之前以動(dòng)畫形式分享的冒泡排序，也包括今天要分享的插入排序。還有一些其他經(jīng)典的排序，小鹿整理的共有十種是面試常問到的，冒泡排序、插入排序、希爾排序、選擇排序、歸并排序、快速排序、堆排序、桶排序、計(jì)數(shù)排序、基數(shù)排序。

雖然我們基本知道了這些排序算法，但是在實(shí)際項(xiàng)目開發(fā)以及面試中往往出乎我們所料。在面試中，經(jīng)常會(huì)被問到各種排序之間的比較；在實(shí)際項(xiàng)目中，往往排序的數(shù)據(jù)不是我們所練習(xí)的整數(shù)。

那么今天我們來(lái)學(xué)習(xí)一下，插入排序比我們之前講的冒泡排序有什么區(qū)別呢？面試官問我們，我們?nèi)绾位卮鹜暾兀?/p>

思維導(dǎo)圖

1

如何分析一個(gè)排序算法？

之前寫的一篇很詳細(xì)的文章。

佩奇學(xué)編程 | 復(fù)雜度分析原來(lái)這么簡(jiǎn)單

分析排序算法已經(jīng)成為我們衡量一個(gè)算法優(yōu)良的重要標(biāo)準(zhǔn)，從以下三個(gè)方面入手。

1.1 時(shí)間效率

這里所謂的實(shí)踐效率就是時(shí)間復(fù)雜度，相信大家對(duì)于時(shí)間復(fù)雜度并不陌生。

復(fù)雜度描述的是算法執(zhí)行時(shí)間（或占用空間）與數(shù)據(jù)規(guī)模的增長(zhǎng)關(guān)系。

對(duì)于時(shí)間復(fù)雜度的分析，要把最好時(shí)間復(fù)雜度、最壞時(shí)間復(fù)雜度、平均時(shí)間復(fù)雜度分析出來(lái)，分別對(duì)應(yīng)了排序算法的最好排序情況、最壞排序情況以及平均排序效率。

1.2 空間消耗

所謂的空間消耗對(duì)應(yīng)的是空間復(fù)雜度，在排序算法中需要開辟的額外內(nèi)存空間是多少。如果空間復(fù)雜度為 O(1)，此時(shí)該排序叫做原地排序。

注意：是額外的內(nèi)存空間，存儲(chǔ)排序數(shù)據(jù)消耗的空間不計(jì)。

1.3 穩(wěn)定性

算法的穩(wěn)定性雖然我們之前接觸的很少，但是穩(wěn)定性也是衡量一個(gè)排序算法的重要標(biāo)準(zhǔn)。什么是穩(wěn)定排序呢？比如有一組有重復(fù)待排序的數(shù)據(jù)，排序前后，重復(fù)的數(shù)據(jù)順序不變，此時(shí)該排序?yàn)榉€(wěn)定排序。否則，叫做不穩(wěn)定排序。它在實(shí)際應(yīng)用中非常重要的，今天我們就不多說(shuō)，以后會(huì)慢慢分享到。

2

什么是插入排序？

顧名思義，插入排序就是通過(guò)插入的方式來(lái)排序唄，最經(jīng)典的就是打斗地主，可以將打亂的撲克牌作為未排序區(qū)間，手中已經(jīng)排好序的作為排序區(qū)間。每次我們摸牌的過(guò)程，就是從未排序區(qū)間，通過(guò)插入的方式，插入到已排序區(qū)間。那么這個(gè)過(guò)程就稱為插入排序。

3

如何實(shí)現(xiàn)插入排序？

上述插入排序的概念我們已經(jīng)理解了，那么給你一組數(shù)據(jù)，如何來(lái)進(jìn)行插入排序呢？

首先我們要將數(shù)據(jù)劃分為兩個(gè)區(qū)間，已排序區(qū)間和未排序區(qū)間。

我們從未排序區(qū)間取出數(shù)據(jù)和已排序區(qū)間的數(shù)據(jù)進(jìn)行比較，如果小于已排序區(qū)間的數(shù)據(jù)，那我們就交換數(shù)據(jù)。

如果交換到已排序區(qū)間數(shù)據(jù)不在大于插入的數(shù)據(jù)，然后將元素插入進(jìn)去。

最后我們看一下總的插入排序動(dòng)畫和代碼實(shí)現(xiàn)。

4

插入排序的性能

我們通過(guò)上邊的對(duì)插入排序的拆分講解和動(dòng)畫以及代碼實(shí)現(xiàn)，想必面試官讓你手寫一個(gè)插入排序可以輕輕松松寫出。但是我們掌握的插入排序知識(shí)還往往不夠，我們?cè)趯?shí)際項(xiàng)目中，還要考慮插入排序的性能怎么樣？因?yàn)椴拍芨玫倪x擇適當(dāng)排序應(yīng)用到項(xiàng)目中去。

4.1 插入排序的穩(wěn)定性

再插入排序中，如果存在重復(fù)數(shù)據(jù)的話，前邊的元素再插入的過(guò)程永遠(yuǎn)在第二個(gè)重復(fù)數(shù)據(jù)的前邊，所以插入排序后的重復(fù)數(shù)據(jù)前后順序不變，所以插入排序是穩(wěn)定排序算法。

4.2 插入排序的空間消耗

我們可以發(fā)現(xiàn)，插入排序的移動(dòng)方式，需要消耗常量級(jí)的額外內(nèi)存空間存儲(chǔ)，也就是代碼中的 temp，所以時(shí)間復(fù)雜度為 O(1),我們上邊講到，空間復(fù)雜度為O(1)的是原地排序算法。

4.3 插入排序的時(shí)間效率

插入排序的最好情況就是不需要搬移任何數(shù)據(jù)，從頭到尾尋找插入數(shù)據(jù)，每次只比較一次即可，即一組有序數(shù)據(jù)，所以最好時(shí)間復(fù)雜度為O(n)。

如果一組數(shù)據(jù)正好是倒序輸出，那么每次都需要比較移動(dòng)所有數(shù)據(jù)，每次移動(dòng)時(shí) n，n 個(gè)數(shù)據(jù)時(shí)間復(fù)雜度為O(n2)。

對(duì)于插入排序的平均時(shí)間復(fù)雜度，每次插入都要移動(dòng)數(shù)據(jù)，插入 n 次，所以平均時(shí)間復(fù)雜度為 O(n2)。

5

小結(jié)

我們學(xué)完了今天的插入排序之后，我們回到最初的面試官問題上。插入排序和冒泡排序哪個(gè)更好呢？

我們現(xiàn)在元素移動(dòng)次數(shù)上進(jìn)行分析，如果一組無(wú)序的數(shù)據(jù)通過(guò)冒泡排序排好序之后，它的交換次數(shù)是這種數(shù)據(jù)的逆序度；對(duì)于插入排序來(lái)說(shuō)也是一樣的，移動(dòng)次數(shù)上都是原本數(shù)據(jù)的逆序度。

元素的移動(dòng)次數(shù)是相同的，那我們接下來(lái)看看元素的交換次數(shù)。從代碼上分析可以明顯看出，冒泡排序的一次交換需要三行代碼，而插入排序的交換卻需要一行，所以總的交換次數(shù)冒泡排序大于插入排序。

有小伙伴會(huì)問，這兩行的差別有那么大嗎？移動(dòng)一次，我們可以不計(jì)較，如果數(shù)據(jù)很多，想想下，兩者的效率差別很輕易的就比較出來(lái)了。

雖然冒泡排序的時(shí)間復(fù)雜度和插入排序的時(shí)間復(fù)雜度是相同的，但是我們實(shí)際使用中還是優(yōu)先選擇插入排序。

對(duì)于插入排序還是可以優(yōu)化的，對(duì)了，沒錯(cuò)，就是希爾排序，我們?cè)谶@不多分開寫，后期會(huì)繼續(xù)更新。

如果覺得寫的有幫助，歡迎轉(zhuǎn)發(fā)朋友圈圈哦！