一、什么是插入排序
插入排序的工作方式非常像人们排序一手扑克牌一样。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较，那插入排序是如何借助上面提到的思想来实现排序的呢？首先我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素，然后在未排序区间中依次取出元素并插入到已排序区间的合适位置，并保证已排序区间一直是有序。重复这个步骤直到未排序区间元素为空，算法结束。
二、代码实现
1、代码实现1
public void sort(int[] ints){
//遍历数组中的元素
for(int i=1 ; i<ints.length ; i++){//元素小于前面的元素
if(ints[i]<ints[i-1]){
//遍历i元素前面的所有元素，从索引0开始
for(int j=0;j<i; j++){
//如果索引为j的元素小于索引为i的元素
if(ints[i]<ints[j]){
int temp = ints[i];
//将索引为j到索引i之间的元素向后移动
for(int k=(i-1);k>=j;k--){
ints[k+1] = ints[k];
}
//将索引为j的元素赋值为temp
ints[j] = temp;
}
}
}
}
}
2、代码实现2
public void sort(int[] ints){
for(int i=1; i<ints.length ; i++){
int temp = ints[i];
int j = i-1;
//如果j大于temp 就一直向后移动
while(j>0&&ints[j]>temp){
ints[j+1] = ints[j];
j--;
}
//最后插入到合适的位置
ints[j+1] = temp;
}
}
