文章目錄

• 三、插入排序
• • 1、插入排序原理
  • 2、圖解插入排序
  • 3、插入排序思路
  • 4、代碼實(shí)現(xiàn)插入排序
  • ５、時(shí)間復(fù)雜度分析
  • ６、小技巧：常用時(shí)間復(fù)雜度
  • • (1) Ｏ(1)
    • (2) Ｏ(n)
    • (3) Ｏ(n^2)
    • (4) Ｏ(n^3)
    • (5) Ｏ(lg n)
    • (6) Ｏ(n lg n)
    • (7) Ｏ(2^n)
  • ７、附：常用的排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度

三、插入排序

1、插入排序原理

每次處理就是將無序數(shù)列的第一個(gè)元素與有序數(shù)列的元素從后往前逐個(gè)進(jìn)行比較,找出插入位置,將該元素插入到有序數(shù)列的合適位置中。

插入排序，顧名思義其基本操作就是插入，不斷把一個(gè)個(gè)元素插入到一個(gè)序列中，最終得到排序序列。

插入排序就像打牌一樣，當(dāng)你摸到比較小的牌時(shí)，通常往后放，遇到比較大的牌時(shí)，通常往前方。當(dāng)然了，還要看自己個(gè)人習(xí)慣。

在打牌時(shí)，我們通常每次從桌子摸一張牌，然后把這張牌再放到一個(gè)正確的位置。

為了找到這張牌放置的正確位置，我們從左到右（或者從右到左）進(jìn)行比較。

2、圖解插入排序

第一輪：

i=2

第二個(gè)數(shù)與前面的數(shù)做比較，發(fā)現(xiàn)2比5小則把小的往前方，把大的往后放

第二輪：

i+1=3

第二輪時(shí)，從第三個(gè)數(shù)與前面的作比較，發(fā)現(xiàn)比5小，把2大，則把5往后移動(dòng)

第三輪：

i+1=4

第三輪時(shí)，因?yàn)槭莍+1，所以這次是第4個(gè)數(shù)與前面的數(shù)作比較，發(fā)現(xiàn)自己就是最大的，則不調(diào)整位置

第四輪：

i+1=5

第四輪從第5個(gè)數(shù)開始比較，發(fā)現(xiàn)比2小，則放在2的前面，2和后面的都向后移動(dòng)調(diào)整位置。

第五輪：

i+1=6

從第6個(gè)數(shù)依次向前比較，找到2號(hào)（按照數(shù)組的索引:0,1,2）位置，則插入此位置，并把后面的依次往后移動(dòng)。

完成：

3、插入排序思路

如上圖所示，此排序需要維護(hù)一個(gè)數(shù)組中的兩個(gè)列表，可以把插入排序的數(shù)組分成已排序和未排序的數(shù)組。

排序的過程中只需要維護(hù)已排序的部分即可。

每次拿未排序列表的首個(gè)數(shù)與已排序的列表的數(shù)據(jù)依次作比較。

找到合適的位置后，移動(dòng)這些的位置然后插入進(jìn)來即可完成插入的操作。

步驟：

從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序

取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描

如果被掃描的元素（已排序）大于新元素，將該元素后移一位

重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置

將新元素插入到該位置后

重復(fù)步驟2~5

4、代碼實(shí)現(xiàn)插入排序

從小到大：

package 排序算法.插入排序;import java.util.Arrays;/*** @Auther: truedei* @Date: 2020 /20-6-6 22:59* @Description:*/ public class InsertionSort {public static int[] INSERTION_SORT(int[] ints){//所有參與排序的數(shù)組的索引范圍，為什么從1開始呢，因?yàn)榭梢园?號(hào)位置的數(shù)據(jù)當(dāng)成已經(jīng)排序好的for (int i = 1; i < ints.length; i++) {//一直到排到的第i個(gè)位置結(jié)束，進(jìn)行倒著比較for (int j = i; j >0 ; j--) {//比較，如果符合要求則交換位置if(ints[j] < ints[j-1]){int temp = ints[j];ints[j]=ints[j-1];ints[j-1]=temp;}else {//遇到不符合要求的數(shù)據(jù)則停止，代表前面都是最小或者最大的了break;}}}return ints;}public static void main(String[] args) {System.out.println(Arrays.toString(INSERTION_SORT(new int[]{2,5,4,7,6,1,3})));}}

結(jié)果：

[1, 2, 3, 5, 4, 6, 7]

從大到小：

package 排序算法.插入排序;import java.util.Arrays;/*** @Auther: truedei* @Date: 2020 /20-6-6 22:59* @Description:*/ public class InsertionSort {public static int[] INSERTION_SORT(int[] ints){//所有參與排序的數(shù)組的索引范圍，為什么從1開始呢，因?yàn)榭梢园?號(hào)位置的數(shù)據(jù)當(dāng)成已經(jīng)排序好的for (int i = 1; i < ints.length; i++) {//一直到排到的第i個(gè)位置結(jié)束，進(jìn)行倒著比較for (int j = i; j >0 ; j--) {//比較，如果符合要求則交換位置if(ints[j] > ints[j-1]){int temp = ints[j];ints[j]=ints[j-1];ints[j-1]=temp;}else {//遇到不符合要求的數(shù)據(jù)則停止，代表前面都是最小或者最大的了break;}}}return ints;}public static void main(String[] args) {System.out.println(Arrays.toString(INSERTION_SORT(new int[]{2,5,4,7,6,1,3})));}}

結(jié)果：

[7, 6, 5, 4, 3, 2, 1]

[7, 6, 5, 4, 3, 2, 1]

５、時(shí)間復(fù)雜度分析

插入排序使用了雙層for循環(huán)，其中內(nèi)層循環(huán)體是真正完成排序的代碼，所以我們分析插入排序的時(shí)間復(fù)雜度時(shí)忽略其他的，主要分析一下內(nèi)層循環(huán)體的時(shí)間復(fù)雜度即可；

可以注意到該算法就兩個(gè)操作是有用的：

• 一個(gè)是比較數(shù)據(jù)
• 一個(gè)是交換數(shù)據(jù)

最壞的情況：

比較數(shù)據(jù)次數(shù)：

最壞的情況就是從頭到尾進(jìn)行比較

$$(N?1)+(N?2)+(N?3)+...+2+1=((N?1)+1)\times \frac{Ｎ?1}{2}=\frac{{Ｎ}^2}{2}?\frac{Ｎ}{2}$$

交換數(shù)據(jù)次數(shù)：

最壞的情況就是從頭到尾進(jìn)行交換

$$(N?1)+(N?2)+(N?3)+...+2+1=((N?1)+1)\times \frac{Ｎ?1}{2}=\frac{{Ｎ}^2}{2}?\frac{Ｎ}{2}$$

時(shí)間復(fù)雜度就是：
$$(\frac{{Ｎ}^2}{2}?\frac{Ｎ}{2})+(\frac{{Ｎ}^2}{2}?\frac{Ｎ}{2})=N^2?N$$

根據(jù)大Ｏ推導(dǎo)法則，保留最高階項(xiàng)：　　去掉常數(shù)項(xiàng)還剩下：
$${Ｎ}^2$$
所以最終得出時(shí)間復(fù)雜度為：
$$O({Ｎ}^2)$$

６、小技巧：常用時(shí)間復(fù)雜度

(1) Ｏ(1)

（１）O(1)　這個(gè)針對(duì)的是常數(shù)；對(duì)于一個(gè)N，不管這個(gè)N是如何增長(zhǎng)，這個(gè)時(shí)間是不變的。

例如下面這些代碼的時(shí)間復(fù)雜度都是O(1)：

/*** @Auther: truedei* @Date: 2020 /20-6-2 22:01* @Description:*/ public class Test {public static void main(String[] args) {System.out.println("你好，我叫鄭暉");System.out.println("你好，我叫鄭暉");System.out.println("你好，我叫鄭暉");System.out.println("你好，我叫鄭暉");}}

還有這種：

我有一個(gè)數(shù)組，我知道了我需要的這個(gè)數(shù)據(jù)所在的索引，然后去拿這個(gè)值，咋這種也是O(1)

/*** @Auther: truedei* @Date: 2020 /20-6-2 22:01* @Description:*/ public class Test {public static void main(String[] args) {String[] names = {"小明","小紅","鄭暉"};System.out.println("你好，我叫"+names[2]);}}

(2) Ｏ(n)

Ｏ(n)是一個(gè)線性增長(zhǎng)的。

經(jīng)常用在for()循環(huán)當(dāng)中

例如下面這種代碼:

/*** @Auther: truedei* @Date: 2020 /20-6-2 22:01* @Description:*/ public class Test {public static void main(String[] args) {String[] names = {"小明","小紅","鄭暉"};for (int i = 0; i < names.length; i++) {System.out.println("你好，我叫"+names[i]);}}}

(3) Ｏ(n^2)

是一個(gè)平方級(jí)的的增長(zhǎng)。經(jīng)常出現(xiàn)在兩層for循環(huán)。

例如本文所寫的：

public static int[] sort(int A[]){for (int i = 0; i < A.length; i++) {for (int j = 0; j < A.length -i - 1 ; j++) {.....}}return A; }

(4) Ｏ(n^3)

是一個(gè)立方級(jí)的增長(zhǎng)。經(jīng)常出現(xiàn)在遍歷一個(gè)三層的for循環(huán)中

for (...) {for (...) {for (...) {.....}}}

(5) Ｏ(lg n)

是一個(gè)對(duì)數(shù)級(jí)。

在二分查找法里就是Ｏ(lg n)。

每次執(zhí)行Ｎ是以一個(gè)倍數(shù)的形式是遞減的：

比如第１次：１/２

比如第２次：１/４

比如第３次：１/８

比如第４次：１/１６

…

快速的讓N的規(guī)模變小。

(6) Ｏ(n lg n)

在排序中經(jīng)常見到的

(7) Ｏ(2^n)

指數(shù)級(jí)的

７、附：常用的排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度

排序法最差時(shí)間分析平均時(shí)間復(fù)雜度穩(wěn)定度空間復(fù)雜度

冒泡排序	O(n^2)	O(n^2)	穩(wěn)定	O(1)
快速排序	O(n^2)	O(n*log2n)	不穩(wěn)定	O(log2n)~O(n)
選擇排序	O(n^2)	O(n^2)	不穩(wěn)定	O(1)
二叉樹排序	O(n^2)	O(n*log2n)	不一頂	O(n)
插入排序	O(n^2)	O(n^2)	穩(wěn)定	O(1)
堆排序	O(n*log2n)	O(n*log2n)	不穩(wěn)定	O(1)
希爾排序	O	O	不穩(wěn)定	O(1)

如果對(duì)你有幫助，可以分享給你身邊的朋友?；蛘呓o俺點(diǎn)個(gè)大大的贊和大大的評(píng)論，點(diǎn)贊和評(píng)論就是給我最大的支持，感謝。
水平有限，難免會(huì)有疏漏或者書寫不合理的地方，歡迎交流討論。
作者：TrueDei
作者唯一博客ＣＳＤＮ：https://truedei.blog.csdn.net/
轉(zhuǎn)載說明：如需轉(zhuǎn)載請(qǐng)注明原地址和作者名。

如果喜歡我的文章，還沒看夠可以關(guān)注我，我會(huì)用心寫好每一篇文章。

歡迎大佬們加入在下的小社區(qū)：

總結(jié)

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

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