左神算法学习笔记 - 004 三傻排序 & 005 对数器

Weijian Duan

2025-02-13

这篇文章对应左神算法课的这两节：

文章总结一下最经典的三个排序：选择排序、冒泡排序、插入排序，而且也是效率最低的三个排序。

选择排序

SelectionSort，基本想法是从 0 ~ n-1 的范围上选择出一个最小的数放在 0 位置，然后继续从 1 ~ n-1 继续选择出一个最小的数放到 1 位置，以此类推直到倒数第二个位置选择完成之后，最后一个位置也就自然完成了，整体完成。

理解上可以想象为一个一遍一遍从左到右的过程，每次解决左边的一个下标，下次遍历的长度就缩短一个。但同时需要注意外层循环的边界条件即可。

class Solution {
    public int[] sortArray(int[] nums) {
        insertionSort(nums);

        return nums;
    }

    public void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int minIndex, i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

冒泡排序

第二个是最为人熟知的冒泡排序。其思路是将最大的数“冒泡”到数组的末尾、数组的倒数第二个位置、倒数第三个位置... 完成整个过程之后，数组就是从小到大有序了的。

我个人理解冒泡排序和选择排序非常像，只不过是一个找最小值放到前面，一个找最大值放到后面，而且一个是比较之后记住下标然后交换，一个是在过程中就把数交换。

class Solution {
    public int[] sortArray(int[] nums) {
        bubbleSort(nums);

        return nums;
    }

    public void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        for (int end = arr.length - 1; end > 0; end--) {
            for (int i = 0; i < end; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

插入排序

插入排序虽然慢，但是思路还挺有意思的，它是一个从小到大把这个有序数组构建出来的过程。插入过程的核心可以理解为，左边的数组已经是有序的了，然后右边来了一个数，我们通过不断地左移比较来把这个数插入到正确的位置，然后得到一个更大的有序数组。

当我们从数组第二个元素开始（第一个元素本身有序），一直进行到最后一个元素，整个数组就有序了。

下面是代码，如何把这种思路在循环条件中写出来是关键：

class Solution {
    public int[] sortArray(int[] nums) {
        insertionSort(nums);
        return nums;
    }

    public void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        // 注意 j 的边界是可以等于 0 的，因为是 j 和 j + 1 的比较
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j+1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

排序总结

关于三种经典排序，还有亮点值得总结：

它们都依赖于「交换」这个行为，因此都需要实现一个 swap 函数
对于排序来说，有一个代码上的注意点是，可以通过 if (arr == null || arr.length < 2) 的判断直接返回，处理脏输入。

对数器

接下来就是对数器，其思路就是「当大量随机 case 都过的时候，就可以认为是正确的」，它可以被认为是本地的 OJ 系统。

比如说，对于排序的比较来说，我们的对数器测试的代码架子就可以这么来写：

public static void main(String[] args) {
    int N = 200; // 输入数组的最大长度
    int V = 1000; // 数组元素值的最大范围
    int testTimes = 50000; // 对数测试多少次

    System.out.println("测试开始");

    for(int i = 0; i < testTimes; i++) { // 那我们就测试那么多次
        int n = (int) (Math.random() * N); // 根据最大长度 -> 随机一个数组长度

        int[] arr = randomArray(n, V); // 根据随机长度，构建一个随机数组，并复制三份
        int[] arr1 = copyArray(arr);
        int[] arr2 = copyArray(arr);
        int[] arr3 = copyArray(arr);

        // 用三种解法来分别算出结果
        selectionSort(arr1);
        bubbleSort(arr2);
        insertionSort(arr3);

        // 进行手动比较，出错停止
        if (!sameArray(arr1, arr2) || !sameArray(arr1, arr3)) {
            System.out.println("出错了");
        }
    }
    
    // 没有错误就是没有问题
    System.out.println("测试结束");
}

// 辅助函数，生成随机数组
public static int[] randomArray(int n, int v) {
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = (int) (Math.random() * v) + 1; // 这是得到一个 [1, V] 的 int 的写法
    }
    return arr;
}

// 复制一个相同的数组
public static int[] copyArray(int[] arr) {
    int[] ans = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        ans[i] = arr[i];
    }
    return ans;
}

// 遍历判断两个数组是否相等
public static boolean sameArray(int[] arr1, int[] arr2) {
    int n = arr1.length;
    for (int i = 0; i < n; i++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}

重点在于理解这个对数器的大的代码框架，如何把这个「自己判题验证」的架子搭起来的。另外就是随机数 API 的使用Math.random() 返回 [0, 1) 范围的数，在它的基础上进行操作就可以得到想要的范围。