插入排序

原理

将给定的数组从第一位开始,遍历,每取一位都和她前面的元素比较,前面的大,就把他放到当前元素后边,不断向前,知道前面的元素比后面小。

时间复杂度

O(nn)
最好情况On
最坏情况O(n
n)

空间复杂度

O(1)

代码

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int tmp = arr[i];
        int t;
        for (int j = i; j >= 0; j--) {
            if (j > 0 && arr[j - 1] > tmp) {
                t = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = t;
            } else {
                arr[j] = tmp;
                break;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

可以化简为如下代码,不用特意进行交换,因为他每次往前飞,如果前面的都会覆盖当前的,每移动一次,覆盖一次,直到找到前面的元素比tmp小,则把那个元素赋值给tmp,这里可以用打断点追踪一下,很清晰,很巧妙!!!,思路起源于这篇博客,点击访问

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int tmp = arr[i];
        int t;
        for (int j = i; j >= 0; j--) {
            if (j > 0 && arr[j - 1] > tmp) {
                arr[j] = arr[j-1];
            } else {
                arr[j] = tmp;
                break;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

或者,条件变一下, 原理大同小异,下面的其实把条件从if里面移动到while里了

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int tmp = arr[i];
        int insert = i;
            while (insert>0 && tmp<arr[insert-1]){
                arr[insert] = arr[insert-1];
                insert--;
            }
            arr[insert] = tmp;
    }
    System.out.println(Arrays.toString(arr));
}

希尔排序

原理

直接插入排序其实是希尔排序gap步长为1的特例

时间复杂度

O(nlog n)
最好情况O(n
log n)
最坏情况O(n*log^2 n)

空间复杂度

O(1)

代码

public static void shellSort(int[] arr){
    for (int gap = arr.length/2; gap >0 ; gap/=2) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            for (int j = i; j >= 0; j-=gap) {
                if (j-gap >= 0 && tmp < arr[j - gap]) {
                    arr[j] = arr[j - gap];
                } else {
                    arr[j] = tmp;
                    break;
                }
            }
        }
    }
}

或者

public static void shellSort(int[] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int insert = i;
            while (insert - gap >= 0 && tmp < arr[insert - gap]) {
                arr[insert] = arr[insert - gap];
                insert -= gap;
            }
            arr[insert] = tmp;
        }
    }
}

或者

public static void shellSort(int[] arr) {
    int n = arr.length;

    // 初始的间隔取 n/2,然后每次减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 使用插入排序对每个分组进行排序
        for (int i = gap; i < n; i++) {
            int tmp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = tmp;
        }
    }

    System.out.println(Arrays.toString(arr));
}

参考文档

插入排序
知乎文章 八大排序算法

分类: java

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

ICP备案号: 辽ICP备20003309号