算法簡介
- 將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中崭放，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)弛房，算法適用于少量數(shù)據(jù)的排序
- 穩(wěn)定排序
- 時(shí)間復(fù)雜度 O(n^2)
基本思想
將n個(gè)元素的數(shù)列分為已有序和無序兩個(gè)部分道盏，如下所示：
{{a1}，{a2文捶，a3荷逞，a4，…粹排，an}}
{{a1⑴种远，a2⑴}，{a3⑴顽耳，a4⑴ …坠敷，an⑴}}
…
{{a1(n-1），a2(n-1) 射富，…},{an(n-1)}}
每次處理就是將無序數(shù)列的第一個(gè)元素與有序數(shù)列的元素從后往前逐個(gè)進(jìn)行比較膝迎，找出插入位置，將該元素插入到有序數(shù)列的合適位置中胰耗。
java代碼實(shí)現(xiàn)(整形數(shù)組)
- 實(shí)現(xiàn)類 Sort.java
public class Sort{
public static void insertionSort(int[] a){
int i,j,key,n=a.length;
for(j = 1;j < n;j++){
key = a[j];
i = j - 1;
while(i >= 0 && a[i] > key){
a[i + 1] = a[i];
i--;
}
a[i + 1] = key;
}
}
}
- 測試類 Test.java
public class Test{
public static void main(String args[]){
int a[] ={4,5,36,8,1,22};
Sort.insertionSort(a);
for(int i = 0; i < a.length; i++){
System.out.println(a[i] + " ");
}
}
}
- 輸出效果圖
insertionsort.PNG
