用递归解决冒泡排序问题-主体结构

时间：2024-07-05 10:10:08

前面说到, 递归分成 基本情形(base case) 和 递归情形(recursive case), 所以, 不管三七二十一, 先把主体结构写出来:

private static void bubbleSort(int[] array) {
    // TODO
    if (baseCase) {
        return;
    } else {
        // 1. do something maybe
        // ...
        // 2. 递归调用
        // bubbleSort(xxx);
    }
}

基本情形(base case)

这个简单, 当只有一个元素时, 自然就无需排序了, 所以:

if (array.length == 1) {
    return;
}

显然, base case 没做任何事, 因此只要把代码条件反转一下, 就可以省略掉这个 base case 了.

递归情形(recursive case)

如何找出递归模式呢? 我们从一个具体的事例考虑:

假如有四个元素: 6 9 8 4, 假设向右边冒泡, 那么从左向右两两比较并根据情况决定是否交换:

第一次比较 6 和 9, 6 比 9 小, 无需交换, 继续；

第二次比较 9 和 8, 9 比 8 大, 所以交换它们得到: 6 8 9 4；

第三次比较 9 和 4, 9 比 4 大, 交换, 得到: 6 8 4 9.

那么, 经过一轮冒泡之后, 最大的元素 9 已经冒泡到了最右边上, 然后下一步就可以只考虑剩下的三个元素了, 而这正好可视作一个新的待排序的数组.

先不考察冒泡的细节, 用一个抽象的 bubble 表示它, 那么可以归纳出如下递归模式:

bubbleSort 一个元素为 N 的数组就是:

  1. 进行一轮冒泡(bubble),
  2. 然后对左边的 N-1 个元素(子数组)递归地进行 bubbleSort.

如下图示:

冒泡排序 递归方式

据此, 写出以下代码(省略了 base case):

private static void bubbleSort(int[] array) {
    // TODO pseudo code
    if (array.length > 1) {
        bubble(array);
        bubbleSort(array.subArray(0, array.length - 1));
    }
}

你可能会想, array 并没有 subArray 方法呀, 另外应该是在原数组上排序.

没错, 这里也注明了这是伪代码(pseudo code), 此刻只需要思考抽象的逻辑是否有问题即可, 诸如是否会发生无限递归呀等情况.

敲定细节

代码中还是伪代码的形式, 显然我们是要在原数组上排序, 这使得我们必须增加一个显式的参数.

如果 array 有更加对象化的方法来能直观表示 subArray(并非指复制的那种, 而是一种指向新位置的引用), 那么增加参数就不是必要的了.

目前我们无法摆脱 array 的结构限制去思考. (这其实暴露了 java 在表达能力上的缺陷或者说 array 的设计上存在一些问题, 使得我们只能笨拙地去表达我们想要的意思)

根据前面的归纳, 定为 N-1 来表示子数组 subArray:

bubbleSort(n – 1, array);

注: 你可能忍不住会把这里的 n 想像成 array 的 index. 没错, 它最终是要映射到 index 上, 但此刻你只要抽象地从概念上把握它即可, 这里的 n 就是指 n 个元素, 它不是什么 index.

方法要形成递归, 所以定义处也修改, 增加一参数 n:

private static void bubbleSort(int n, int[] array)

公共接口里调用时也因此要作改动, 需要显式传入 N, 对于初始情况, N 也即是 array.length:

bubbleSort(array.length, array);

另外有一点要特别注意, 因为不是传递 subArray, array.length 始终不变, 所以 if 语句中的判断已经不正确:

必须由 if(array.length > 1) 改为 if(n > 1)

现在考察 bubble, 显然 N 跟 array 都要往里面传. 现在直接将 bubble 方法考虑成递归的, 以减少中间环节. 那么, 还要再增加一个参数 bn, 表示有几个元素需要 bubble.

让 IDE 生成方法签名, 最终结果如下:

// 对外接口
public static void sort(int[] array) {
    if (array != null && array.length > 1) {
        bubbleSort(array.length, array);
    }
}

// 具体内部实现
private static void bubbleSort(int n, int[] array) {
    if (n > 1) {
        bubble(n, n, array);
        bubbleSort(n - 1, array);
    }
}

private static void bubble(int bn, int n, int[] array) {
    // TODO
}

注: bubble(n, n, array) 中

第一个 n 表示有 n 个元素需要冒泡;

第二个 n 表示有 n 个元素需要排序.

其实你也能感觉到, 这完全就是面向过程式的编程.

至此, 主体结构已经 OK 了. 现在考虑冒泡 bubble 的实现问题.

相关文章