哈嘍，我是程式員大鵬，
前面我們介紹了冒泡排序和選擇排序，今天我們來看一下簡單排序中的插入排序，
打過撲克的都知道，在抓牌的時候，我們不會等抓完所有的牌再用冒泡或者選擇排序再理牌，一般是拿到一張牌就放到手里，抓到第二張牌的時候，再跟手里面已經有的牌進行比較，插到合適的位置，然后抓第三張牌，再與手里面的兩張牌進行比較，然后再把牌插到合適的位置，這種一邊抓牌，一邊理牌的方式，我們就稱之為直接插入排序，
插入排序思想
插入排序是一種從序列左端開始依次對資料進行排序的演算法，在排序程序中，索引左側的資料陸續歸位，而右側留下的就是還沒有被排序的資料，
插入排序的思路就是從右側的未排序區域內取出一個資料做為待排序資料，然后將它插入到已排序區域內合適的位置上，一直到未排序清空，
排序原理
- 將待排序的值臨時移除并保存在一個臨時變數中，
- 將空隙左側的每一個值一次與臨時變數比較，如果左邊的數大于臨時變數的值，則該值右移一格，如果左邊的數字更小，就不需要繼續比較，本輪操作到此結束，最終左側會有一個位置的空隙，
- 將臨時移走的資料插入到當前空隙，
- 重復前面三步，直到所有元素均排序完畢，
插入排序影片
插入排序代碼
public static void insertSort(int[] arr) {
// 默認第一個元素是有序的，所以索引不是從0開始，從1開始
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];//待排序元素賦值給臨時變數
int position = i;//記錄當前比較的索引
while (position > 0 && arr[position - 1] > temp) {
arr[position] = arr[position - 1];
position--;
}
arr[position] = temp;//插入到正確的位置
}
}
讓我們來一行一行地分析一下代碼：
for (int i = 1; i < arr.length; i++) {
在上面代碼是外層回圈，在i的左側是已排序資料，起始的i等于1，是默認第0個資料已經是排序資料，
int temp = arr[i];//待排序元素賦值給臨時變數
int position = i;//記錄當前比較的索引
每一輪開始的時候，position是待排序資料的索引，temp的值就是本輪待排序的資料，第一輪的待排序索引為1，第二輪是2,第三輪是3，依次類推，一直到最后一輪，
while (position > 0 && arr[position - 1] > temp) {
開始內層的回圈，如果滿足position大于0，并且當前位置的資料與temp比較，如果大于temp資料，則進入到回圈里面，
arr[position] = arr[position - 1];
position--;
資料平移一個位置，將position做為空隙，
arr[position] = temp;
將待排序的資料temp插入到空隙的位置，
排序步驟分析
下面我們應用插入排序對陣列[4,2,3,5,1]進行排序，來看每一步的操作，
第0輪
這一輪其實是沒有的，我們默認就是第一個位置的值是有序的，
第一輪
將索引值為1的值2暫時移除，保存在臨時變數temp中，此時temp為2，
第1步：比較索引0的值4與temp中的
第2步：因為4大于2，所以將4右移，
空隙移到了陣列最左端，沒有其他值可以比較了，
第3步：將temp插回到陣列中，結束第一輪，
第二輪
將索引為2的值3暫時移除，保存到臨時變數temp中，此時temp為3，
第4步：比較4與temp
第5步：因為4比3大，所以將4右移
第6步：比較2與temp
第7步：因為2比3小，所以無須2平移，平移結束
第8步：將temp插回到陣列的空隙中，結束第二輪，
第三輪
將索引為3的值5暫時移除，保存在臨時變數temp中，此時temp的值為5.
第9步：比較4與temp
第10步：因為4比5小，，所以無須4平移，平移結束
第四輪
將索引為4的值1暫時移除，保存在臨時變數temp中，此時temp的值為1.
第11步：比較5與temp
第12步：因為5比1大，所以將5右移
第13步：比較4與temp
第14步：因為4比1大，所以將4右移
第15步：比較3與temp
第16步：因為3比1大，所以將3右移
第17步：比較2與temp
第18步：因為2比1大，所以將2右移
空隙移到了陣列最左端，沒有其他值可以比較了，
第19步：將temp的值1插回到陣列的空隙中，
到現在為止，整個陣列已經排好序了，
選擇排序復雜度分析
在插入排序中，需要將取出的資料與其左邊的數字進行比較，就跟前面講的步驟一 樣，如果左邊的數字更小，就不需要繼續比較，本輪操作到此結束，自然也不需要交換 數字的位置，
然而，如果取出的數字比左邊已歸位的數字都要小，就必須不停地比較大小，交換數字，直到它到達整個序列的最左邊為止，具體來說，就是第 k 輪需要比較k-1 次，因 此，在最糟糕的情況下，第2 輪需要操作1 次，第 3 輪操作2 次……第n 輪操作n-1 次，所以時間復雜度和冒泡排序的一樣，都為 O(n^2)，
和前面講的排序演算法一樣，輸入資料按從大到小的順序排列時就是最糟糕的情況，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/63381.html
標籤：Java