public class InsertionSorting {
public static void main(String[] args) {
int Arr[] ={5,4,3,2,1};
InsertionSorting in=new InsertionSorting();
in.sort(Arr);
for (int i=0;i<Arr.length;i++){
System.out.print(Arr[i]+"、");
}
}
void sort(int arr[]){
int n = arr.length;
for (int i=1; i<n; ++i)
{
int current = arr[i];
int pre = i-1;
while (pre>=0 && arr[pre] > current)
{
arr[pre+1] = arr[pre];
pre = pre-1;
}
arr[pre+1] = current;
}
}
}
/**
* 插入排序算法思想
* 先从数组第二个数(i=1)开始比较，使用for循环慢慢把i+1，直到i=数组.length,结束循环
* 先保存当前arr[i]的值: int current = arr[i];
* 得到i的前一位数的下标 pre=i-1,
* 进入while循环，判断j是否还在下标范围内(>=0),判断arr[pre]是否大于current，
* 如果两个条件都满足，则把的前一位数arr[pre]（大于arr[pre+1]的值)，赋值给arr[pre+1];
* 然后下标往前进一个，pre=pre-1，得到j前面继续想比较值的下标，
* 然后再次进入while循环，再进行判断判断j是否还在下标范围内(>=0),判断arr[pre]是否还大于current，
* 例子：{3,2,1}
* for第一次，下标i=1,从2开始，比较3，2的值会保存current,得到i的前一位下标pre = i-1=0，进入while，然后把arr[0]=3值赋值给arr[pre+1=1]处，此时为{3，3,1}，
* 然后pre-1=-1，结束while循环，把current赋值给pre+1=0处，此时为{2,3,1}
* for第二次，下标i=2,从1开始，比较arr[1]=3，1的值会保存current，进入while，然后把3的值赋值给1处，此时为{2,3,3}，然后pre-1=0,
* 继续while循环，2大于current,此时会把2的值赋值给pre+1=1处，此时 为{2,2,3}，然后pre-1=-1,结束while循环，把current赋值给pre+1=0处，此时为{1,2,3}
*
*
*/
