【巩固基础系列】一文搞定算法基础

参考资料：

算法 第四版 (塞奇威克(Sedgewick, R.))

文中引用的所有网络内容均以 [x] 的形式标出，点击即可跳转到出处。

如有错误，欢迎大家在评论区指正！

一文搞定算法基础

1. 排序

在继续阅读之前，首先我们要清楚排序的本质是什么？假设我们要从小到大排序，一个数组中取两个元素如果前面比后面大，则为一个逆序，容易看出排序的本质就是消除逆序数。[1]

如下为代码示例中会用到的两个公共类。

//所有排序算法的基类
package com.book1.chapter2.sort;

public abstract class Sort {
    public abstract void sort(int[] arr);

    /**
     * 交换
     */
    public void exchange(int[] a, int i, int j) {
        SortUtils.exchange(a, i, j);
    }

    /**
     * a是否小于b
     *
     * @param a
     * @param b
     * @return
     */
    public boolean less(int a, int b) {
        return SortUtils.less(a,b);
    }

}


//排序算法的工具类
package com.book1.chapter2.sort;

import java.time.Duration;
import java.time.LocalDateTime;
import java.util.Arrays;

public class SortUtils {
    /**
     * 是否为有序数组
     *
     * @param arr
     * @return
     */
    public static boolean isOrderArr(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }


    /**
     * 打印数组
     *
     * @param arr
     */
    public static void printArr(int[] arr) {
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 交换两个元素
     *
     * @param a
     * @param i
     * @param j
     */
    public static void exchange(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }


    /**
     * a是否小于b
     *
     * @param a
     * @param b
     * @return
     */
    public static boolean less(int a, int b) {
        return a < b;
    }

    /**
     * 分析时间
     *
     * @param arr
     * @param sort
     */
    public static void analyseTime(int[] arr, Sort sort) {
        LocalDateTime s = LocalDateTime.now();
        sort.sort(arr);
        LocalDateTime e = LocalDateTime.now();
        System.out.printf("是否有序：%s，用时:%s\n", isOrderArr(arr), Duration.between(s, e).toMillis());
    }
}

1.1 选择排序

思想

1. 找到数组中最小的那个元素；
2. 将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）；
3. 在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置；
4. 循环1~3 。

这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

代码

package com.book1.chapter2.sort;

public class SelectSort extends Sort {

    /**
     * 选择排序:
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     *
     * @return
     */
    @Override
    public void sort(int[] arr) {
        int min;
        //0.遍历数组的每一个索引i
        for (int i = 0; i < arr.length; i++) {
            min = i;
            //1. 找到数组中最小的那个元素；
            for (int j = i + 1; j < arr.length; j++) {
                if (less(arr[j], arr[min])) {
                    min = j;
                }
            }
            //2. 将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）；
            exchange(arr, i, min);
        }
        //循环步骤0~2，即在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复
    }
}

缺点

• 一个已经有序的数组（或是主键全部相等的数组）和一个元素随机排列的数组所用的排序时间竟然一样长！

  • 究其原因，是由于步骤1遍历了一遍数组，而未对下次扫描提供有效信息。（成本不低，有效产出太少！）

1.2 插入排序

思想

在已有的有序序列中，插入新元素。

1. 判断新元素的插入位置；
2. 为了给新元素腾出空间，需要将新元素之后的所有元素在都向右移动一位；
3. 插入新元素；
4. 循环1~3。

这种算法叫做插入排序。

代码

package com.book1.chapter2.sort;

public class InsertSort extends Sort{
    /**
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 与选择排序的区别：
     * 选择排序是从待排序序列中挑选最小的元素放到当前索引位置。
     * 插入排序是对当前索引位置（包含）之前的序列进行冒泡排序
     *
     * @return
     */
    @Override
    public void sort(int[] arr) {
        //遍历数组
        // 为什么此处不是从0开始？见问答
        for (int i = 1; i < arr.length; i++) {
            // 在已有的有序序列（arr[0] ~ arr[i]）中,
            //判断新元素的插入位置
            //将新元素之后的元素逐个右移
            for (int j = i; j > 0 && less(arr[j], arr[j - 1]); j--) {
                exchange(arr, j, j - 1);
            }
        }
    }
}

问答

1. 为什么此处不是从0开始？

   因为当数组只有1个元素时，数组本身即是有序的，所以插入排序应该从第 2 个元素开始（对应索引是 1）。

适用场景

• 数组中每个元素距离它的最终位置都不远；
• 一个有序的大数组接一个小数组；
• 数组中只有几个元素的位置不正确。

1.3 希尔排序

? 希尔排序和插入排序类似，但是希尔排序为什么比插入排序快？我们之前讲过排序的本质即是消除逆序数，插入排序每次交换只能消除 1 个逆序数，而希尔排序一次性可以消除多个逆序数。

思想

1. 选择合适的间隔 h；
2. 对间隔为 h 的两个元素进行比较，若后一个大于前一个，则交换；
3. 缩小 h ，循环进行步骤 1 ~ 2。

使数组中任意间隔为 h 的元素都是有序的，则整个数组都会是有序的。

代码

package com.book1.chapter2.sort;

public class ShellSort extends Sort {

    /**
     * 时间复杂度：O(NlogN)
     * 不稳定
     * @return
     */
    @Override
    public void sort(int[] arr) {
        int len = arr.length;
        //初始化间隔
        int h = len / 3 + 1;
        //间隔需要大于等于1。（因为元素的间隔为0则代表元素位置重合）
        while (h >= 1) {
            //以间隔为h，进行插入排序
            for (int i = h; i < len; i++) {
                for (int j = i; j >= h && less(arr[j], arr[j - h]); j = j - h) {
                    exchange(arr, j, j - h);
                }
            }
            //缩小间隔后继续循环
            h /= 3;
        }
    }
}

问答

1. 为什么希尔排序的时间复杂度能突破$O(n^2)$？

   ? 可以用逆序数来理解，假设我们要从小到大排序，一个数组中取两个元素如果前面比后面大，则为一个逆序，容易看出排序的本质就是消除逆序数，可以证明对于随机数组，逆序数是 $O(n^2)$ 的，而如果采用“交换相邻元素”的办法来消除逆序，每次正好只消除一个，因此必须执行 $O(n^2)$ 的交换次数，这就是为啥冒泡、插入等算法只能到平方级别的原因，反过来，基于交换元素的排序要想突破这个下界，必须执行一些比较，交换相隔比较远的元素，使得一次交换能消除一个以上的逆序，希尔、快排、堆排等等算法都是交换比较远的元素，只不过规则各不同罢了。原文链接

未完待续 ~ 欢迎点赞或评论区催更！

如果这篇文章对你有用的话，本人深感荣幸！