使用遞歸排序數組的氣泡（無循環）C++

#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。我不確定我的退貨是否正確。使用遞歸排序數組的氣泡（無循環）C++

來源

2016-01-23 Ancient Dragon

你忘了函數名'return'後，使之遞歸調用本身。另外，如果你的函數返回一個非空值（但是爲什麼呢），你需要一個「基本情況」return語句（沒有遞歸調用），可能在函數的最後。 – leemes

爲什麼？無論如何，這是一個可怕的算法。爲什麼會變得更糟？如果你想要一個低效的O（N^2）排序，插入排序和選擇排序至少簡單易懂。如果你只是想排序的東西，使用'std :: sort'。 –

@AlanStokes我想練習遞歸函數和冒泡排序似乎是一個很好的做法。所以任何幫助，將不勝感激。 –

在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] << ' '; 
}

一般來說，你可以通過遞歸函數替換每個循環：

檢查後衛 - >如果失敗返回。
其他執行主體
遞歸調用函數，通常使用遞增的計數器或某物。

但是，爲了防止A（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] << ' '; 
}

來源

2016-01-23 20:36:18 Herbert

謝謝，不是很熟悉std :: vectors，如果有另一種方式，它將非常感激。 –

如果您願意，您可以將std :: vector 與int [N]和number.size（）交換爲N。 – Herbert

只是爲了確認，size_t代表vector的大小，如果可以，我可以用其他東西替換它。（用矢量還不是很舒服）。非常感謝！ –

請仔細閱讀this post

function pass(i,j,n,arr) 
{ 
    if(arr[i]>arr(j)) 
    swap(arr[i],arr[j]); 

    if(j==n) 
    { 
    j=0; 
    i=i+1; 
    } 
    if(i==n+1) 
    return arr; 

    return pass(i,j+1,n,arr); 
}

來源

2016-01-23 21:17:02

使用遞歸排序數組的氣泡（無循環）C++

回答

相關問題