插入排序的思想及代码

╰+哭是因爲堅強的太久メ 2022-09-01 13:59 131阅读 0赞

插入排序：  
插入排序最好时间复杂度是 O(n)，即当数组刚好是完全顺序时，每次只用比较一次就能找到正确的位置。这个过程重复 n 次，就可以清空未排序区间。

插入排序最坏时间复杂度则需要 O(n*n)。即当数组刚好是完全逆序时，每次都要比较 n 次才能找到正确位置。这个过程重复 n 次，就可以清空未排序区间，所以最坏时间复杂度为 O(n*n)。

插入排序的平均时间复杂度是 O(n*n)。这是因为往数组中插入一个元素的平均时间复杂度为 O(n)，而插入排序可以理解为重复 n 次的数组插入操作，所以平均时间复杂度为 O(n*n)。

插入排序不需要开辟额外的空间，所以空间复杂度是 O(1)。

根据上面的例子可以发现，插入排序是稳定的排序算法。代码如下：

public class InsertSort {
        
        public static void main(String[] args){
        
            int[] arr=new int[1000];
            for (int i = 0; i <1000 ; i++) {
        
                arr[i]=(int)(Math.random()*1000);
            }
            }
        public static void InsertSortMethod(int[] arr){
        
            for (int i = 0; i <arr.length ; i++) {
        
                int j=i;
                while (j>0){
        
                    if(arr[j]>arr[j-1]){
        
                        int temp=arr[j];
                        arr[j-1]=arr[j];
                        arr[j]=temp;
                        j--;
                    }else{
        
                        break;
                    }
                }
            }
        }
    }
    /*
     思路：1.默认从第二个数开始往前比较，若比第一个数字大（或者小）则交换
          2.然后用第三个数去和第二个数进行比较，符合则交换，但是还应该继续往前比较
          比如有 5个数8，15，20，45, 17,17比45小，需要交换，但是17也比20小，也要交换，当不需 要和15交换以后
          ，说明也不需要和15前面的数据比较了，肯定不需要交换，因为前 面的数据都是有序的
          3.重复步骤二，一直到数据全都排完。
     * */