排序–插入排序
- 2019 年 10 月 22 日
- 笔记
1、什么是插入排序？
插入排序就是把n个元素看成一个有序表（一般是第一个元素）和无序表，将无序表中的元素逐个取出和有序表的元素从后向前进行比较，并放入合适的位置
2、插入排序的思路：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
3、代码逐步实现
目标：对数组内元素排序 int[] arr={101,34,119,1};
//第一轮 int insertVal=arr[1]; //默认arr[0]是有序元素，arr[1]是待插入元素 int insertIndex=1-1; //指向待插入元素的前一个元素 //insertIndex>=0是为了防止在找插入位置时发生错误， insertVal<arr[insertIndex是当待插入值比前面的有序元素小时，进入循环 while (insertIndex>=0 && insertVal<arr[insertIndex]){ arr[insertIndex+1]=arr[insertIndex]; //把当前元素和前一个元素置为相同，如101，101，119，1 insertIndex--; //向前移动 } arr[insertIndex+1]=insertVal; //跳出循环说明插入位置已经找到，为其赋值，为什么+1，因为循环内已经-1，现在才定位到arr[0] System.out.println(Arrays.toString(arr));
//第二轮 insertVal=arr[2]; //已经排好两个元素了，现在需要插入的时第三个元素 insertIndex=2-1; //定位到第三个元素的前一个元素 while (insertIndex>=0 && insertVal<arr[insertIndex]){ arr[insertIndex+1]=arr[insertIndex]; insertIndex--; } arr[insertIndex+1]=insertVal; System.out.println(Arrays.toString(arr));
//第三轮 insertVal=arr[3]; insertIndex=3-1; while (insertIndex>=0 && insertVal<arr[insertIndex]){ arr[insertIndex+1]=arr[insertIndex]; insertIndex--; } arr[insertIndex+1]=insertVal; System.out.println(Arrays.toString(arr));*/
可发现上面几轮有很多重复代码，可以设置一个for循环，整合一下
for (int i=1;i<arr.length;i++){ //i为每次需要插入的元素 int insertVal=arr[i]; int insertIndex=i-1; while (insertIndex>=0 && insertVal<arr[insertIndex]){ arr[insertIndex+1]=arr[insertIndex]; insertIndex--; } arr[insertIndex+1]=insertVal; System.out.println(Arrays.toString(arr)); }
3、时间复杂度
两层循环，所以时间复杂度为O(n^2)
4、发现问题
当元素前面时有序，最后几位为乱序时，很浪费时间，如
int[] arr={6,7,8,9,1};
7、8、9都是有序，因为最后一位，需要都进行一次排序比较，所以又有了下面的 希尔排序
