寫在前邊
排序對于每個開發者來講,都多多少少知道幾個經典的排序算法,比如我們之前以動畫形式分享的冒泡排序,也包括今天要分享的插入排序。還有一些其他經典的排序,小鹿整理的共有十種是面試常問到的,冒泡排序、插入排序、希爾排序、選擇排序、歸并排序、快速排序、堆排序、桶排序、計數排序、基數排序。
雖然我們基本知道了這些排序算法,但是在實際項目開發以及面試中往往出乎我們所料。在面試中,經常會被問到各種排序之間的比較;在實際項目中,往往排序的數據不是我們所練習的整數。
那么今天我們來學習一下,插入排序比我們之前講的冒泡排序有什么區別呢?面試官問我們,我們如何回答完整呢?
思維導圖
1
如何分析一個排序算法?
之前寫的一篇很詳細的文章。
佩奇學編程 | 復雜度分析原來這么簡單
分析排序算法已經成為我們衡量一個算法優良的重要標準,從以下三個方面入手。
1.1 時間效率
這里所謂的實踐效率就是時間復雜度,相信大家對于時間復雜度并不陌生。
復雜度描述的是算法執行時間(或占用空間)與數據規模的增長關系。
對于時間復雜度的分析,要把最好時間復雜度、最壞時間復雜度、平均時間復雜度分析出來,分別對應了排序算法的最好排序情況、最壞排序情況以及平均排序效率。
1.2 空間消耗
所謂的空間消耗對應的是空間復雜度,在排序算法中需要開辟的額外內存空間是多少。如果空間復雜度為 O(1),此時該排序叫做原地排序。
注意:是額外的內存空間,存儲排序數據消耗的空間不計。
1.3 穩定性
算法的穩定性雖然我們之前接觸的很少,但是穩定性也是衡量一個排序算法的重要標準。什么是穩定排序呢?比如有一組有重復待排序的數據,排序前后,重復的數據順序不變,此時該排序為穩定排序。否則,叫做不穩定排序。它在實際應用中非常重要的,今天我們就不多說,以后會慢慢分享到。
2
什么是插入排序?
顧名思義,插入排序就是通過插入的方式來排序唄,最經典的就是打斗地主,可以將打亂的撲克牌作為未排序區間,手中已經排好序的作為排序區間。每次我們摸牌的過程,就是從未排序區間,通過插入的方式,插入到已排序區間。那么這個過程就稱為插入排序。
3
如何實現插入排序?
上述插入排序的概念我們已經理解了,那么給你一組數據,如何來進行插入排序呢?
首先我們要將數據劃分為兩個區間,已排序區間和未排序區間。
我們從未排序區間取出數據和已排序區間的數據進行比較,如果小于已排序區間的數據,那我們就交換數據。
如果交換到已排序區間數據不在大于插入的數據,然后將元素插入進去。
最后我們看一下總的插入排序動畫和代碼實現。
4
插入排序的性能
我們通過上邊的對插入排序的拆分講解和動畫以及代碼實現,想必面試官讓你手寫一個插入排序可以輕輕松松寫出。但是我們掌握的插入排序知識還往往不夠,我們在實際項目中,還要考慮插入排序的性能怎么樣?因為才能更好的選擇適當排序應用到項目中去。
4.1 插入排序的穩定性
再插入排序中,如果存在重復數據的話,前邊的元素再插入的過程永遠在第二個重復數據的前邊,所以插入排序后的重復數據前后順序不變,所以插入排序是穩定排序算法。
4.2 插入排序的空間消耗
我們可以發現,插入排序的移動方式,需要消耗常量級的額外內存空間存儲,也就是代碼中的 temp,所以時間復雜度為 O(1),我們上邊講到,空間復雜度為O(1)的是原地排序算法。
4.3 插入排序的時間效率
插入排序的最好情況就是不需要搬移任何數據,從頭到尾尋找插入數據,每次只比較一次即可,即一組有序數據,所以最好時間復雜度為O(n)。
如果一組數據正好是倒序輸出,那么每次都需要比較移動所有數據,每次移動時 n,n 個數據時間復雜度為O(n2)。
對于插入排序的平均時間復雜度,每次插入都要移動數據,插入 n 次,所以平均時間復雜度為 O(n2)。
5
小結
我們學完了今天的插入排序之后,我們回到最初的面試官問題上。插入排序和冒泡排序哪個更好呢?
我們現在元素移動次數上進行分析,如果一組無序的數據通過冒泡排序排好序之后,它的交換次數是這種數據的逆序度;對于插入排序來說也是一樣的,移動次數上都是原本數據的逆序度。
元素的移動次數是相同的,那我們接下來看看元素的交換次數。從代碼上分析可以明顯看出,冒泡排序的一次交換需要三行代碼,而插入排序的交換卻需要一行,所以總的交換次數冒泡排序大于插入排序。
有小伙伴會問,這兩行的差別有那么大嗎?移動一次,我們可以不計較,如果數據很多,想想下,兩者的效率差別很輕易的就比較出來了。
雖然冒泡排序的時間復雜度和插入排序的時間復雜度是相同的,但是我們實際使用中還是優先選擇插入排序。
對于插入排序還是可以優化的,對了,沒錯,就是希爾排序,我們在這不多分開寫,后期會繼續更新。
如果覺得寫的有幫助,歡迎轉發朋友圈圈哦!
-
算法
+關注
關注
23文章
4607瀏覽量
92840 -
排序
+關注
關注
0文章
31瀏覽量
9707
原文標題:動畫:面試官問我插入排序和冒泡排序哪個更牛逼?
文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數據結構】歡迎添加關注!文章轉載請注明出處。
發布評論請先 登錄
相關推薦
評論