面试之选择排序——数组下标越界了吗【面试踩坑优化】
排序算法3-插入排序
课代表总结
—
基本思路
-
插入排序就像是打扑克牌时，拿牌之后在手中的牌里找位置的思想一样。即将待排序数组看为两个部分，一部分是有序数组，另一部分是待插入的无序数组。 -
例如待排序数组为arr[5]={10，1，3，2，9}；在第一趟排序时，将数组分为两个部分，arr[0]为有序数组，而arr[1]、arr[2]、arr[3]、arr[4]为无序的待插入数组。 -
首先从无序数组中拿出arr[1]和arr[0]比较，arr[0]>arr[1]则将arr[0]的值后移，将arr[1]插入到arr[0]之前，依次类推。
「分析」
插入排序一共需要进行arr.length-1趟排序，时间复杂度为O(n^2);
「实现思路」
两个循环嵌套，第一层循环代表排序的趟数，一共arr.length-1趟，第二层循环为待插入数，分别和有序部分中的数组比较，如果待插入数组小于当前数值，则当前数值赋给当前的下一个。下面的动态图，相信你一看就懂的
「代码实现」
public class Insertsort1 {public static void main(String[] args) {int[] arr = new int[] { 4, 3, 2, 1 };insertsotr(arr);System.out.println(Arrays.toString(arr));}public static void insertsotr(int[] arr) {int temp, index = 0;for (int i = 0; i < arr.length - 1; i++) {temp = arr[i + 1];for (int j = i; j >= 0; j--) {if (temp < arr[j]) {arr[j + 1] = arr[j];index = j;} else {break;}}arr[index] = temp;System.out.println("第" + i + "趟排序的结果是" + Arrays.toString(arr));}}}
插入排序优化
在上面的程序中，每一趟排序都会执行arr[index] = temp语句，但是当待插入数值正好在现在的位置时，此语句不需要被执行，因此对上面的程序做一个优化，数值刚好出现在位置，不必执行语句，也就是代码中的if判断。
「代码」
public class Insertsort2 {public static void main(String[] args) {int[] arr = new int[] { 4, 3, 2, 1 };insertsotrt2(arr);System.out.println(Arrays.toString(arr));}public static void insertsotrt2(int[] arr) {int temp, index;for (int i = 1; i < arr.length; i++) {temp = arr[i];index = i-1;while (index >= 0 && temp < arr[index]) {arr[index + 1] = arr[index];index--;}if (index + 1 != i) {arr[index + 1] = temp; //加入判断避免不必要的赋值}System.out.println("第" + i + "趟排序的结果是" + Arrays.toString(arr));}}}
「常见错误」
while (index >= 0 && temp < arr[index]) 语句换为 while(temp < arr[index] && index >= 0) 时会出现数组下标越界，报错内容如下：
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1at insertsort.Insertsotr3.insertsotrt3(Insertsotr3.java:17)at insertsort.Insertsotr3.main(Insertsotr3.java:8)
「错误分析：」
-
主要原因是因为&&逻辑与，也叫做短路，只要当前项为假，它就不往后判断了，直接认为表达式为假。那么对于上面的两个条件，index为-1时temp也就数组越界了。 -
个人建议：对于while里面的条件判断，自己写完代码后一定拿一个值在边界上执行下循环即可发现是否会越界。
性能测试
随机产生80000个数据进行排序，运行时间结果图如下：
可以看出排序80000个随机数字，插入排序用了3秒，选择排序用了1秒，而冒泡排序用了12秒。
总结
-
插入排序比冒泡排序快，没有选择排序快。经常作为快排的补充。 -
当然这些都是次要的，排序算法都不难，最主要的是优化的思想！工作中也是这样，代码简单难的是优化。 -
无论简单的算法还是更为复杂的，主要是解决问题的思路，举一反三，多思考，很多地方都可以应用的到！