排序--插入排序

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都是有序，因为最后一位，需要都进行一次排序比较，所以又有了下面的  希尔排序