插入排序是一種簡單且有效的比較排序算法。在每次迭代過程中算法從輸入序列中移除一個元素，并將該元素插入待排序序列的正確位置。重復該過程，直到所有輸入元素都被選擇一次。

算法優點：

a.實現簡單

b.數據量較少時效率高

c.適應性：如果輸入序列已經預排序，則時間復雜度幾乎是線性的。

d.穩定性：鍵值相同時它能夠保持輸入數據的原有次序。

e.原地：不需要額外的空間。

算法思路：從第二個元素作為當前元素，依次往下標較小的位置遍歷，當前一個元素比該元素小，則將該元素放入當前位置，否則前一個元素后移，同理依次遍歷；然后以第三個元素作為當前元素，重復上述操作；依次往后直到到達最后一個元素完成排序。

代碼：

package insertionsort;public class InsertionSort {private static int count;public static int[] insertionSort(int[] A,int n){int i,j,v;for(i=1;i<n;i++){v=A[i];j=i;while(j>=1&&A[j-1]>v)//此處應該將j>=1的條件限制放在前面，然后用短路與&&,這樣使用才不會導致A[j-1]報錯;{A[j]=A[j-1];//滿足條件則需繼續遍歷，則將j-1位置的元素往后移；j--;count++;}A[j]=v;//當A[j-1]<v的時候，則將A[j]的位置放v。print(A);}return A;}private static void print(int[] A){int n=A.length;for(int i=0;i<n;i++)System.out.print(A[i]+" ");System.out.println();}public static void main(String[] args) {// TODO Auto-generated method stubint[] A= {8,9,1,4,5,3,7,2};int n=8;System.out.println("插入排序步驟中插入元素位置變化：");int[] ans=InsertionSort.insertionSort(A, n);System.out.println("完成排序后的序列：");for(int i=0;i<n-1;i++)System.out.print(ans[i]+" ");System.out.print(ans[n-1]);System.out.println();}} 測試結果：

插入排序步驟中插入元素位置變化： 8 9 1 4 5 3 7 2 1 8 9 4 5 3 7 2 1 4 8 9 5 3 7 2 1 4 5 8 9 3 7 2 1 3 4 5 8 9 7 2 1 3 4 5 7 8 9 2 1 2 3 4 5 7 8 9 完成排序后的序列： 1 2 3 4 5 7 8 9
插入排序最壞情況下的時間復雜度為O(n^2)，在數據幾乎都已經排序或者輸入數據規模較小時可以使用插入排序。

總結

以上是生活随笔為你收集整理的排序算法之插入排序--Java语言的全部內容，希望文章能夠幫你解決所遇到的問題。

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