插入排序思想
建议手上有一副扑克牌，会更加好理解。
- 场景0 ：现在有一个数组([2,5,3,1,4]),需要按照从小到大的顺序依次排列。
- 解决方法：明确--只有一个数的数组只有一种排序方式。所以此时可以假定，这个数组分为了两部分，其中一部分时排序为([2])的子数组，此子数组满足从小到大排序的的要求。另外一部分是排序为([5,3,1,4])子数组。此时选中5与2进行比较，5>2所以5的位置位置不变。此时子数组便可以分割为([2,5] [3,1,4])两个子数组了。左边的数组依旧有序，右边数组无序。下一步选中3，3<5但3 > 2，此时3应该在5之前而在2之后。可以看到，选中一个数，至少需要一次比较，至多需要(n - 1)次比较。而比较的次数也决定了需要移动地位置次数。
插入排序的思想就是始终保证一分为二，且其中一部分始终有序。依次选定每一个元素，然后插入合适的位置，将之前的元素依次向后移，直到遍历完所有元素。
现实例子，假设你现在在玩斗地主，目前的你手上没有一张牌。此时开始发牌，你需要对你的牌进行排序。拿到第一张牌，不论大小都会放置在1号位。在你拿起第二张牌时，需要与手上的第一张牌进行比较。如果小于第一张牌，则插入第一张牌前成为第一张牌，而原先的第一张牌则会位置往后挪移一步占据原先第二张牌的位置。当你的手上有(n)张牌的时候，最多便会进行(n-1)次比较。
Demo
package Sort;
/**
* 实现插入排序
*
* @author Ldity
* @date: 8/7 2020
*/
public class InsertSort {
// 测试数组
public static int[] arr = {123,34,132,21,23,1324,52,2123,23415,-1};
/**
* 实现《算法导论》中插入排序
*
* @param arr 未排序的数组
* @return 已排序的数组
*/
public static int[] insertSort0(int[] arr){
for(int i = 1; i < arr.length ; i++ ){
int tmp = arr[i];
int j = i - 1;
while(j >= 0 && arr[j] > tmp){
arr[j + 1] = arr[j];
j--;
}
arr[j+1] = tmp;
}
return arr;
}
/**
* 实现《算法》中的插入排序
*
* @param arr 未排序的数组
* @return 排序后的数组
*/
public static int[] insertSort1(int[] arr){
for(int i = 1; i < arr.length; i++){
int tmp = arr[i];
int j;
for(j = i - 1; j >= 0 && arr[j] > tmp; j--){
arr[j + 1] = arr[j];
}
arr[j + 1] = tmp;
}
return arr;
}
public static void main(String[] args){
arr = insertSort0(arr);
for (int s: arr) {
System.out.println(s);
}
}
}