思想：將未排序的第一個(gè)元素和已排序（從最后一個(gè)）比較
排序前
Paste_Image.png
第一次插入
Paste_Image.png
第二次插入
Paste_Image.png
第三次插入
Paste_Image.png
Java展現(xiàn)其思想
package sortingAlgo;
import java.util.Arrays;
import java.util.Random;
/**
* @author 水皮蛋
* 特點(diǎn)：stable sort到忽、In-place sort
* 最優(yōu)復(fù)雜度：當(dāng)輸入數(shù)組就是排好序的時(shí)候芽腾，復(fù)雜度為O(n)赠叼，而快速排序在這種情況下會(huì)產(chǎn)生O(n^2)的復(fù)雜度。
* 最差復(fù)雜度：當(dāng)輸入數(shù)組為倒序時(shí)勃教，復(fù)雜度為O(n^2)。
* 插入排序比較適合用于“少量元素的數(shù)組”嚼沿。
*/
public class InsertionSort {
public static void main(String[] args) {
int[] arr = createRandomArray();
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(insertionSort(arr)));
}
/**
* @param arr 需要排序的數(shù)組
* @return 升序數(shù)組
*/
public static int[] insertionSort(int[] arr) {
if (arr == null)
throw new NullPointerException();
int n = arr.length,j=0,key=0;
if (!(n > 1))
return null;
//i是未排序的第一個(gè)角標(biāo)
for(int i=1;i<n;i++){
j = i-1;
key = arr[i];
while(j >= 0 && arr[j] > key){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
return arr;
}
/**
* 使用Random類產(chǎn)生隨機(jī)數(shù)組的對(duì)象
* @return 隨機(jī)數(shù)組
*/
public static int[] createRandomArray() {
Random random = new Random();
int[] array = new int[10];
for (int i = 0; i < 10; i++) {
array[i] = random.nextInt(100);
}
return array;
}
}
