美文网首页
插入排序

插入排序

作者: 你大爷终归是你大爷 | 来源:发表于2021-05-07 16:08 被阅读0次

维护已经排好序的部分,插入需要重新维护(交换内部位置)
如果是有序(和有序部分的队尾比较),内部只比较一次O(n),适用于近乎有序的排序

/**
 * 插入排序 :维护已经排好序的部分,插入需要重新维护(交换内部位置)
 * O(n²)
 * 如果是有序(和有序部分的队尾比较),内部只比较一次O(n),适用于近乎有序的排序
 * 维护前半部分是有序的
 */
public class InsertionSort {

    private InsertionSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i< arr.length; i++)  {
            for (int j = i;j-1>=0;j--) {
                if (arr[j].compareTo(arr[j-1])<0){ // 和相邻的往前比
                    swap(arr,j,j-1);
                } else {
                    break;
                }
            }
        }
    }

    private static <E> void swap(E[] arr,int i,int j){
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

优化,不使用swap,减少赋值操作

    //优化,保存初始值,使用移动方式,减少赋值
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        for (int i = 0; i< arr.length; i++)  {
            E t = arr[i];
            int j = i;
            for (;j-1>=0;j--) {
                if (t.compareTo(arr[j-1])<0){
                    arr[j] = arr[j-1]; // 向后移动,和swap比减少了声明和一次赋值操作
                } else {
                    break;
                }
            }
            arr[j] = t;
        }
    }

相关文章

网友评论

      本文标题:插入排序

      本文链接:https://www.haomeiwen.com/subject/lntedltx.html