[排序算法]--直接插入排序的三种实现(Java)

谁借莪１个温暖的怀抱￠ 2022-07-12 01:09 160阅读 0赞

> 直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

设数组为a\[0….N-1\]:  
（1）初始时，a\[0\]自成1个有序区，无序区为a\[1..n-1\]。令i=1

（2）将a\[i\]并入当前的有序区a\[0…i-1\]中形成a\[0…i\]的有序区间。

（3）i++并重复第二步直到i==n-1，排序完成。

按照上面的思路，给出代码：

public static void insertSort1(int [] a, int n){
        int i, j;
    
        for(i =1; i<n; i++){
       //依次把a[1]到a[n-1]插入到前面有序序列中
            //从前往后找到a[i]的插入点
            for(j =0; j<i; j++){
                if(a[j] > a[i]){
                    break;//跳出内层循环
                }
            }
    
            /**将元素a[i]插入在a[j]位置*/
            int temp = a[i];//这里需要保存a[i], 不然下面的移动操作会覆盖掉a[i]的数据
            //将a[j]开始的元素到a[i-1]后移
            for(int k=i-1; k>=j; k--){
                a[k+1] = a[k];
            }
            //将a[i]插入
            a[j] = temp;
        }
    }

测试函数：

public static void main(String[] args) {
        int[] arr = {
       1,1,2,0,9,3,12, 7, 8, 3, 4, 65, 22};
    
        InsertionSort.insertSort2(arr, arr.length);
    
        for(int i:arr){
            System.out.print(i+",");
        }
    }

运行结果：

0,1,1,2,3,3,4,7,8,9,12,22,65,

上面的代码太长，可以把代码写得简洁一些，现在我们从有序序列的最大值往前比较，并且边比较边移动数据：即每次a\[i\]先和前面一个数据a\[i-1\]比较，如果a\[i\] > a\[i-1\]说明a\[0…i\]也是有序的，无须调整。否则就令j=i-1,temp=a\[i\]。然后一边将数据a\[j\]向后移动一边向前搜索，当有数据a\[j\]

/** * 优化第一步:边比较和移动合并,这时候需要从大到小比较 * @param a * @param n */
    public static void insertSort2(int [] a, int n){
        int i, j;
    
        for(i =1; i<n; i++){
       //依次把a[1]到a[n-1]插入到前面
            if(a[i] < a[i-1]){
       //当a[i]小于a[i-1]时才需要比较
                int temp = a[i];//这里需要保存a[i], 不然下面的移动操作会覆盖掉a[i]的数据
                //找到插入点
                for(j =i-1; j>=0 && a[j]>temp; j--){
                    a[j + 1] = a[j];
                }
                //将a[i]插入
                a[j+1] = temp;
            }
        }
    }

再次改写，现在将前面的数据移动方法进行改写，用数据交换代替移动。如果a\[j\]前一个数据a\[j-1\] > a\[j\]，就交换a\[j\]和a\[j-1\]，再j–直到a\[j-1\] <= a\[j\]。这样也可以实现将一个新数据新并入到有序区间。

public static void insertSort3(int [] a, int n){
        int i, j;
    
        for(i =1; i<n; i++) {
       //依次把a[1]到a[n-1]插入到前面
            for(j = i-1; j>=0 && a[j]>a[j+1]; j--){
                int temp;
                temp = a[j];
                a[j] = a[j+1];
                a[j+1]=temp;
            }
        }
    }

其实上面三种算法的时间复杂度都是O(n^2)，只不过，后面的优化更改善一点点性能。

本文所有代码的github地址：  
[https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Algorithm/InsertionSort.java][https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Algorithm_InsertionSort.java]

[https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Algorithm_InsertionSort.java]: https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Algorithm/InsertionSort.java