这些年我们忘记的排序算法--插入排序

vlambda
2020-04-13

这些年我们忘记的排序算法--插入排序

什么是插入排序？

插入排序属于内部排序法，是对于将要排序的元素以插入的方式寻找该元素的适当位置，以达到排序的目的。

我们应该如何操作呢？

首先呢，我们把n个待排序的元素看成一个有序数组和无序数组，一开始时，有序数组只包含一个元素，无序数组包含n-1个元素，在排序过程中我们每次从无序数组中取出第一个元素，然后分别与有序数组中的元素进行比较，最终插入到适当的位置，使之成为有序数组。下面我们通过模型来更好的理解：

模型中我们可以发现黑方框把数组分成两个数组，在每次排序中，我们分别从无序数组中取出数字与有序数组中的数字比较，然后放在适当的位置。随着有序数组元素的增多，无序数组元素的减少，最终我们整个数组变成为一个有序数组。

原理我们理解了差不多了，该如何用代码实现呢？

上代码

import java.util.Arrays;
public class Charu {
 public static void main(String[] args) { int[] arr = { 7,5,9,2,3,6 }; array(arr);  }
 public static void array(int[] arr) { // 因为我们把数组的第一个元素（下标为0的元素）看成为有序数组 // 所以i从1开始 for (int i = 1; i < arr.length; i++) { int insertvalue = arr[i]; // 将要插入的元素 int index = i - 1; // 要插入的元素前一个元素下标 // Index>=0保证给insertValu找插入位置时不越界 // insertvalue<array[Index]待插入的数还没有找到插入位置 while (index >= 0 && insertvalue < arr[index]) { // 后移，此时array[Index+1]和array[Index]值相同 arr[index + 1] = arr[index]; // 继续找前一个元素 index--;  } // 退出while循环时表明找到了插入的位置 // 也就是说，咋们要插入的元素比他前面的元素大了(insertvalue>arr[index]) // 或者是找到头了index=-1了 // 咱们把要插入的那个值放在比他小的那个元素的后面(index+1的位置) // 此时insertvalu覆盖了两个相同值下标小的那个值 arr[index + 1] = insertvalue; System.out.println(Arrays.toString(arr)); } }}