思想：将未排序的第一个元素和已排序（从最后一个）比较
排序前
Paste_Image.png
第一次插入
Paste_Image.png
第二次插入
Paste_Image.png
第三次插入
Paste_Image.png
Java展现其思想
package sortingAlgo;
import java.util.Arrays;
import java.util.Random;
/**
* @author 水皮蛋
* 特点：stable sort、In-place sort
* 最优复杂度：当输入数组就是排好序的时候，复杂度为O(n)，而快速排序在这种情况下会产生O(n^2)的复杂度。
* 最差复杂度：当输入数组为倒序时，复杂度为O(n^2)。
* 插入排序比较适合用于“少量元素的数组”。
*/
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 需要排序的数组
* @return 升序数组
*/
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是未排序的第一个角标
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类产生随机数组的对象
* @return 随机数组
*/
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;
}
}
