1.算法的簡單原理介紹
插入排序(Insertion-Sort)是一種最簡單直觀的排序算法。它的工作原理是通過構建有序序列,對於未排序數據,在已排序序列中從後向前掃描,找到相應位置並插入。也就是說,他是基於比較的排序。就是通過比較數組中的元素,看誰大誰小,根據結果來調整元素的位置。因此,對於這類排序,就有兩種基本的操作:
①比較操作;
②交換操作。
2.插入排序的實現步驟
- 將第0個元素開始,該元素可以認為已經排序完成;
- 從下一個元素開始,從排序完成的元素開始由後往前掃描;
- 如果已經排序完成的元素大於新元素,則新元素前移;
- 重複3的步驟,直到已排序元素小於等於新元素;
- 將新元素插入到該元素後面;
- 重複以上步驟(2-5);
以上文字讀起來可能比較難以理解,通過下面的動態圖可以更好的理解。
簡言之,就是從前往後,將小數據元素往前移。
3.插入排序的程序實現
舉例分析如下:
以5,3,2,3排序過程如下:
---------------------------------------------------------------------------------------------------------------
第一趟:3 5 2 3
第0個元素5認為是排序完成的,從第1個元素開始,第1個元素和第0個元素比較,第1個元素小,所以前移;
---------------------------------------------------------------------------------------------------------------
第二趟:2 3 5 3
第2個元素2跟第1個元素5比較,小,所以第二個元素前移,再與第0個元素比較,還小,所以再前移;
---------------------------------------------------------------------------------------------------------------
第三趟:2 3 3 5
第3個元素,與第2個元素比較,小,所以第三個元素前移,再與前一個元素比較,不小於,所以不動,完成排序。
---------------------------------------------------------------------------------------------------------------
4.最後總結:
插入排序,就是玩兒牌的過程,在抓牌的時候,放牌的過程中就完成了一次排序,會打牌的朋友可以回想一下這個過程。
更多精彩內容,請關注頭條號:玩轉嵌入式。謝謝。
閱讀更多 玩轉嵌入式 的文章