常見(jiàn)排序之——插入排序

何為插入排序：插入排序就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。簡(jiǎn)單來(lái)說(shuō)，就是指已經(jīng)插入數(shù)組中的元素都是有序的。

舉個(gè)粟子：

一個(gè)數(shù)組如下所示：3，4，2，7，5，1，9，0

當(dāng)插入3的時(shí)候，3保持不變；

插入4的時(shí)候，4>3,故順序保存不變；

插入2的時(shí)候，4>2,故交換，交換完之后發(fā)現(xiàn)3>2,再交換，故數(shù)組就變成：2，3，4（保持從小到大的順序了）；

插入7時(shí)，順序保持不變；

插入5時(shí)，由于5<7，故交換順序，此時(shí)變?yōu)?#xff1a;2，3，4，5，7；……這樣不斷進(jìn)行下去就可以將數(shù)組排好序，

不難看出：該排序方法的時(shí)間復(fù)雜度還是O（N^2）,不過(guò)該算法的一個(gè)好處就是穩(wěn)定性變好了。（題外話(huà)：何為穩(wěn)定性好呢？

穩(wěn)定性好是指：一個(gè)數(shù)組中兩個(gè)相同的元素，經(jīng)過(guò)排序之后他們?cè)跀?shù)組中的相對(duì)位置保持不變。。）

下面附上程序源碼：

總結(jié)

以上是生活随笔為你收集整理的常见排序之——插入排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。