Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

简介

插入排序算法是生活中比较常用的一种算法。每次处理一个元素,把这个元素插入到前面已经处理好的数组中。

思路

一般使用两层循环,第一层遍历全部元素,第二层以第一层的指针所指向的位置为结束位置,以此位置倒叙遍历这个小数组,以最后一位依次与前面的所有元素对比,决定这个元素应该存放的位置。

实现

public class InsertSort{
    public static <E extends Comparable<E>> void doSort(E[] arr){
        E temp;
        for (int i = 0;i < arr.length;i++){
            for (int j = i;j - 1 > 0 && arr[j - 1].compareTo(arr[j]) > 0;j--){
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
        }
    }
}

优化

上述的实现中每次交换都需要三次操作temp =arr[i]arr[i] = arr[j]arr[j] = temp。优化后可以减少操作到一步。(时间复杂度仍是O(n^2))
我们可以使用平移覆盖的方式来优化这个操作。首先取出最后一个元素假设为最小值,并创建一个指针指向当前位置,每次循环指针指向的元素与前一个元素相比,如果前一个元素比取出的这个元素大,则前一个元素直接覆盖指针指向的位置,当前一个元素小于当前元素时最小值则使用取出的最小值覆盖指针指向的位置。

public class InsertSort{
    public static <E extends Comparable<E>> void doSort(E[] arr){
        for (int i = 0;i < arr.length;i++){
            int j;
            E temp = arr[i];
            for (j = i;j - 1 >= 0 && temp.compareTo(arr[j - 1] < 0)){
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }
}

性能测试

        long elder = System.nanoTime();
        // 调用排序方法
        long now = System.nanoTime();
        System.out.println(((now - older) / 1000000000.0));

使用上述方式计算两个方法:

交换元素的方法: 12.142622833s

覆盖元素的方法: 7.893185708s