插入排序的思想是把前面的排好依次往下進行遍歷，發現比最后一個數小的把它插入排好序的最后一個數的前面，此時排好的數組可能已經不再有序，就對它進行維護,以此重復上述操作

具體步驟：定義一個指針i,再定義一個指針j,i最開始指向數組的第二個數，j指向i的前一個數，然后讓j和他后面的數進行比較，如果后面的數比j小就讓他倆交換（如果不交換說明前面已經排好序），然后再讓指針j指到j的前一個數，在讓j和j后面的數進行比較如果比j指針指向的數大就再進行交換，以此循環直到j后面的數比j大或j指向數組的第一個數，就讓指針i指向下一個數，以此循環直到i指向數組最后一個數。排序完成。

數組按插入排序全過程如下圖：

?

?

?

?

?

插入排序代碼如下：

public class Insertsort {public static void main(String[] args) {//定義無序數組int[] arr= {23,43,1,22,67,123,88,99,90,15};sort(arr);}private static void sort(int[] arr) {//第一次for循環，即對每個數都進行遍歷，i就是上面所說的i指針for(int i=1;i<arr.length;i++) {//第二次for循環，每次j開始都是i的前一個數，然后向前走以維護前面已排好序的數組即j--for(int j=i-1;j>=0;j--) {//判斷如果j比后面數大就進行交換，然后j--進行維護if(arr[j]>arr[j+1]) {arr[j]^=arr[j+1];arr[j+1]^=arr[j];arr[j]^=arr[j+1];}else{//j比后面數小此層for循環結束，因為沒必要繼續遍歷以減小時間頻率，break;}} }System.out.println(Arrays.toString(arr)); }}

結果如下：

?時間復雜度：外層for循環時間復雜度是O（n）最壞情況里層需要每次遍歷到數組的第一個數即里層時間復雜度是O（n）,所以最壞情況下插入排序的時間復雜度是o(n^2)

這也是插入排序的弊端所以產生一個希爾排序來降低它的時間復雜度。

總結

以上是生活随笔為你收集整理的java数组的插入排序以及时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。