气泡无循环递归排序

Question

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

我的函数只会采用带有数字和大小的数组。

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中，您通常不会以这种方式实现冒泡排序；相反，您将使用迭代方法（即循环）。

此递归实现严格用于教学目的。一些所谓的“纯功能”语言没有任何循环，它们只有递归。一种语言是Erlang。

[请注意，对bubble_sort的递归调用是bubble_sort中的最后一条语句。这称为“尾递归”，它允许编译器优化将返回地址推入堆栈的过程。 C编译器（可能）不会进行这种尾部递归优化，但是功能编译器（例如Erlang编译器）会进行优化。

[bubble_sort_pass中对bubble_sort_pass的递归调用当前不是尾部递归调用，但是可以很容易地将其更改为尾部递归调用（亲自验证一下！）