c++ - 使用递归(无循环)C++ 对数组进行冒泡排序

Question

#include <iostream>
#include <cstdlib>

using std:: cin;
using std:: cout;
using std:: endl;

const int N=10;

void readarray(int array[], int N);
int bubble_sort (int array[], int size, int round,
                 int place);

int main ()
{
    int array[N];
    readarray( array, N );

    int round, place;
    cout << bubble_sort(array, N, place, round);


    return EXIT_SUCCESS;
}


void readarray(int array[], int N)
{
    int i=0;
    if (i < N)
    {
        cin >> array[i];
        readarray(array+1, N-1);
    }
}


int bubble_sort (int array[], int size, int round,
                int place)
{
    round =0;
    place =0;

  if (round < N-1) // this goes over the array again making sure it has 
                   // sorted from lowest to highest
  {
     if (place < N - round -1) // this sorts the array only 2 cells at a 
                               // time
         if (array[0] > array[1])
         {
            int temp = array[1];
            array[1]=array[0];
            array[0]=temp;
            return (array+1, size-1, place+1, round);
         }
   return (array+1, size-1, place, round+1);
   }
}

我知道如何使用两个 for 循环进行冒泡排序，我想使用递归来进行。使用循环你需要两个 for 循环，我认为对于递归它可能还需要两个递归函数/调用。这是我到目前为止所拥有的。问题是它只输出一个数字，要么是 1，要么是 0。我不确定我的返回是否正确。

Answer 1

在c++11中，你可以这样做:

#include <iostream>
#include <vector>


void swap(std::vector<int &numbers, size_t i, size_t j)
{
    int t = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = t;
}

bool bubble_once(std::vector<int> &numbers, size_t at)
{
    if (at >= numbers.size() - 1)
        return false;
    bool bubbled = numbers[at] > numbers[at+1];
    if (bubbled)
        swap(numbers, at, at+1);
    return bubbled or bubble_once(numbers, at + 1);
}

void bubble_sort(std::vector<int> &numbers)
{
    if ( bubble_once(numbers, 0) )
        bubble_sort(numbers);
}

int main() {
    std::vector<int> numbers = {1,4,3,6,2,3,7,8,3};
    bubble_sort(numbers);

    for (size_t i=0; i != numbers.size(); ++i)
        std::cout << numbers[i] << ' ';
}

通常，您可以用递归函数替换每个循环:

1. 检查守卫 -> 如果失败返回。
2. 否则执行正文
3. 递归调用函数，通常使用递增的计数器或其他东西。

但是，为了防止(n 实际)堆栈溢出，在循环同样足够的情况下避免递归是一种很好的做法。此外，循环具有非常规范的形式，因此对于许多程序员来说很容易阅读，而递归可以在许多程序员中完成，因此更难阅读、测试和验证。哦，递归通常比较慢，因为它需要创建一个新的堆栈框架(需要引用，不太确定)。

编辑

使用普通数组:

#include <iostream>
#include <vector>

#define N 10

void swap(int *numbers, size_t i, size_t j)
{
    int t = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = t;
}

bool bubble_once(int *numbers, size_t at)
{
    if (at >= N - 1)
        return false;
    bool bubbled = numbers[at] > numbers[at+1];
    if (bubbled)
        swap(numbers, at, at+1);
    return bubbled or bubble_once(numbers, at + 1);
}

void bubble_sort(int *numbers)
{
    if ( bubble_once(numbers, 0) )
        bubble_sort(numbers);
}

int main() {
    int numbers[N] = {1,4,3,6,2,3,7,8,3,5};
    bubble_sort(numbers);

    for (size_t i=0; i != N; ++i)
        std::cout << numbers[i] << ' ';
}