插入排序

概念

将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录递增1的有序表。

原理

首先以数组的第二个元素为当前元素，然后与前一个元素作比较，若前一个元素比当前的元素大，将前一个元素覆盖当前元素的位置。 重复以上比较步骤，直到前一个元素比当前元素小后，将当前元素的值插入进去。至此就完成一次外层循环， 接下来就是以第三个元素为当前元素与其前一个元素作比较，和之前的步骤一样，以此类推，完成排序

代码示例

public static int[] sort(int[] arr){ /* * 首先以数组的第二个元素为当前元素，然后与前一个元素作比较，若前一个元素比当前的元素大，将前一个元素覆盖当前元素的位置。 * 重复以上比较步骤，直到前一个元素比当前元素小后，将存储在临时变量tmp中的值插入进去。至此就完成一次外层循环， * 接下来就是以第三个元素为当前元素与其前一个元素作比较，和之前的步骤一样，以此类推，完成排序 */ for (int i = 1; i < arr.length; i++) { // 临时变量tmp存储当前位置的元素值 int tmp = arr[i]; // 创建临时变量j int j = i; // j>0是为了防止数组下标越界异常 while (j > 0 && arr[j-1] > tmp){ arr[j] = arr[j-1]; // j--的目的在于将当前元素一直与前一个元素比较，直到合适的位置 j--; } // 说明当前的元素找到位置了，将临时变量的值插入进去 if (j != i){ arr[j] = tmp; } } return arr; } public static void main(String[] args) { int[] arr = {9,3,2,0,-10,5,1}; int[] sort = sort(arr); for (int result:sort){ System.out.print(result+" "); } }

运行结果：