/**
* 用递归的方法实现的插入排序算法
* 分解：n个元素的排序看成是把第n个元素插入到已排好序的n-1个元素中
* 解决：对n-1个元素以次递归
* 合并：用插入排序将第n个元素插入到排好序的n-1个元素序列中
*/
public class InsertSort {
/**
* 将数组arr中第p个位置的元素插入到排好序的0到p-1序列中
* @param arr
* @param p
*/
static void insert(int arr[],int p){
if(p>0){
if(arr.length>1){
int key = arr[p];
int i = p-1;
while(i>=0&&arr[i]>key){
arr[i+1]=arr[i];
i--;
}
arr[i+1]=key;
}
}
}
/**
* 插入排序的外层函数
* @param arr
* @param p
*/
static void insertSort(int arr[],int p){
if(p>1)
insertSort(arr,p-1);
insert(arr,p);
}
public static void main(String[] args) {
int arr[] = {3,4,5,14,19,11,16,1,9,7,8,10,2,6,12,15,18,13,17,20};
insertSort(arr,arr.length-1);
for(int i=0;i<arr.length;i++)
System.out.println(arr[i]);
}
}
