没有循环的递归冒泡排序

Question

是否可以在没有任何 global/static 变量、只有一个数组且没有循环的情况下进行冒泡排序？我想知道这是否可能，如果可能，很难吗？

我的函数只接受带有数字和大小的数组。

int bubble_sort_asc_rec(int tab[], int size)

Answer 1

#include <stdio.h>

int bubble_sort_pass(int array[], int size)
{
    /* We return the number of swaps in this iteration. */
    int swaps = 0;

    /* If the array contains 0 or 1 elements, it is already sorted. */
    if (size < 2) {
        return swaps;
    }

    /* Array contains at least 2 elements. */
    if (array[0] > array[1]) {
        /* First two elements are in wrong order. We need to swap them. */
        printf("Swap value %d with value %d\n", array[0], array[1]);
        int temp = array[0];
        array[0] = array[1];
        array[1] = temp;
        swaps += 1;
    }

    /* Recursively bubble sort the array starting at the 2nd element. */
    swaps += bubble_sort_pass(array + 1, size - 1);
    return swaps;
}

void bubble_sort(int array[], int size)
{
    /* Do one pass of bubble sorting the entire array. */
    printf("Start a bubble sort pass.\n");
    int swaps = bubble_sort_pass(array, size);

    /* If there was at least one swap, we have to do another pass. */
    if (swaps >= 1) {
        bubble_sort(array, size);
    }

}


int main()
{
    int numbers[] = {10, 8, 3, 7, 2, 1, 4, 6, 5, 9};
    int count = sizeof(numbers) / sizeof(numbers[0]);
    bubble_sort(numbers, count);
    for(int i=0; i<count; ++i) {
        printf("numbers[%d] = %d\n", i, numbers[i]);
    }
    return 0;
}

在 C 中，您通常不会以这种方式实现冒泡排序；相反，您将使用迭代方法（即循环）。

此递归实现仅用于教学目的。一些所谓的 "pure functional" 语言没有任何循环，它们只有递归。 Erlang 就是这样一种语言。

请注意，对 bubble_sort 的递归调用是 bubble_sort 中的最后一条语句。这称为 "tail recursion"，它允许编译器优化将 return 地址压入堆栈。 C 编译器（可能）不会进行这样的尾递归优化，但函数式编译器（例如 Erlang 编译器）会。

bubble_sort_pass中对bubble_sort_pass的递归调用目前不是尾递归调用，但很容易变成尾递归调用（自己验证！）

Answer 2

这是一个使用 Python 的实现。但是，函数的第二个参数不是数组的长度，而是一个计数变量。我还包含了两个测试用例。

def get_largest(arr, count):
    if len(arr) <= 1:
        return arr
    if arr[0] >= arr[1]:
        temp = arr[0]
        arr[0] = arr[1]
        arr[1] = temp
        return get_largest(arr, count)
    else:
        return [arr[0]] + get_largest(arr[1:], count)

def bubblesort(arr, count):
    if count == len(arr):
        return arr
    arr = get_largest(arr, count)
    return bubblesort(arr, count + 1)

arr_test = [item for item in reversed(range(1,10))]
arr_test2 = [3, 5, 1, 7, 8, 9, 4]

print('First Test Array: ', arr_test)
print('Sorted: ', bubblesort(arr_test, 0))

print('Second Test Array: ', arr_test2)
print('Sorted: ', bubblesort(arr_test2, 0))

没有循环的递归冒泡排序

bubble sort recursively without loops

c

recursion

bubble-sort