理解递归（将其应用于冒泡排序）

Question

我想弄清楚如何在程序中使用递归。我了解递归在“阶乘”等经典示例中的工作原理，但不确定如何自己应用它......

我开始将迭代冒泡排序代码转换为递归代码...... 我在网上搜索了相同的内容......但无法找到令人信服的解决方案/解释......

冒泡排序的示例迭代代码是：

arr[n]->包含要排序的元素 (1..n) 的数组

for(i:1 to n)  
    for(j:1 to n-1)  
      if(arr[j+1]>arr[j])  
         swap(arr[j+1],arr[j]);

如果有人能给出有关如何进行的提示，将会很有帮助...

Answer 1

public void sort(int[] arr, int first, int last){

    if(first < last && last > 0){
        if(arr[first] > arr[first+1]){
            int temp = arr[first];
            arr[first] = arr[first+1];
            arr[first+1] = temp;
        }
        sort(arr, first+1, last);
        sort(arr, first, last-1);
    }
    else
        return;
}

迟了两年，但也许对某人有用

Answer 2

我不确定冒泡排序是否是练习递归的好算法。将其转换为递归会非常难看，因为它是一个嵌套循环。它看起来像这样：

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);
}

它是相同的 for 循环，只是定义时间更长，使用更多内存。

相反，您应该尝试实现快速排序。它需要递归，并且在大多数情况下比冒泡排序快得多。大多数平台已经实现了它，因此您不必自己编写它，但了解它是如何工作的很有好处，并且有助于理解递归。

如果您愿意，您也可以尝试使用递归来解决此问题：
您有一个 NxM 数字表和一个起始坐标（位置）。这是^旅行者^的立场。旅行者可以前往相邻的单元格（右、左、上或下），该单元格的编号小于他所在的单元格的编号。您必须编写一个程序来计算旅行者在这些约束下可以通过的最长路径。使用随机生成数组，或手动生成。

Answer 3

递归是一种基于归纳证明的设计技术。考虑您的问题的一个或多个基本（简单）案例，以及使问题更接近基本案例问题的一种或多种方法。然后，在算法的每个步骤中，您要么认识到完成（并适当地处理基本情况），要么使问题稍微接近基本情况。

冒泡排序只是观察排序数组按顺序排列所有相邻元素对的观察的应用。以递归方式定义，其工作原理如下：

1. 基本情况：有一个大小为 1（或更小）的数组需要排序。当然，已经排序了。
2. 归纳情况：将最大元素冒泡到数组顶部。现在有一个较小的单元素数组需要排序，确实如此。

您可以用您选择的编程语言编写这个想法，然后就可以进行冒泡排序。哦，但是你必须定义“冒泡最大元素”的含义。嗯，这是递归设计的另一个机会。不过，我想你已经明白了。

更快的排序主要基于对如何以更少的工作更接近目标的观察。例如，快速排序依赖于这样的概念：如果一个数组已排序，则存在某个元素 P，并且所有小于 P 的元素都位于 P 的左侧，所有大于 P 的元素都位于 P 的右侧。如果您可以在数组上建立该属性，并选择 P，那么您可以在每一步将问题大致减半，而不是简单地减半。

Answer 4

这是 javascript 中的递归冒泡排序：

function bubbleSortRecursive(array, index1, index2) {
    //define index1 and index2 if user doesn't pass them in
    index1 = typeof index1 == "undefined" ? 0 : index1;
    index2 = typeof index2 == "undefined" ? array.length : index2;

    if (index1 > index2) {
        return array;
    } else if (index1 == index2 - 1) {
        return bubbleSortRecursive(array, 0, index2 - 1);
    } else if (array[index1] > array[index1 + 1]) {
        //bubble the larger value towards the end of the array
        var temp = array[index1];
        array[index1] = array[index1 + 1];
        array[index1+1] = temp;
        return bubbleSortRecursive(array, index1 + 1, index2);
    } else {
        return bubbleSortRecursive(array, index1 + 1, index2);
    }
}

函数内的前两行允许用户调用bubbleSortRecursive(array)，函数将定义index1和index2

Answer 5

这是使用冒泡排序对数组进行递归排序的另一种简单方法。

static void recursive_bubble_sort(int[] Arr, int l)
{// 'Arr' is the array where 'l' is the length of the array

    if (l == 0) {
       return;
    }

    for (int j = 0; j < l - 1; j++) {
        if (Arr[j] > Arr[j + 1]) {
            swap(Arr[j], Arr[j + 1]);
        }
    }

    recursive_bubble_sort(Arr, l - 1);
}

对于递归解决方案，必须更新长度，以便函数始终适用于数组中的其余项目。

Answer 6

因为我发现这个问题是第一个例子，所以我想提供另一种方法来进行递归，而不需要额外的参数：

function bubblesort (input: some integer array):
  if input is empty:
    return input
  else:
    do one bubble sort run for input
    subarray = bubblesort(unsorted part of input)
    return subarray append sorted part of input

通过这种方式，我们将为每次调用对整个数组进行分段排序。

为什么它有效？因为每次冒泡排序运行，我们都会至少将最大的元素放入最右边的索引。
我们知道，直到最后一次交换的所有元素都处于未知状态，所有在最后一次交换之后都已排序。

Java 中的实现（数组/列表参数修改/不修改）可以在那里找到： https://codereview.stackexchange.com/questions/24006/recursive-bubble-sort-in-java/24133#24133

Answer 7

#include <stdio.h>
#include <stdlib.h>

void sort(int *arr, int first, int last){

    if(first < last && last > 0){
        if(arr[first] > arr[first+1]){
            int temp = arr[first];
            arr[first] = arr[first+1];
            arr[first+1] = temp;
        }
        sort(arr, first+1, last);
        sort(arr, first, last-1);
    }
    else
        return;
}
int main(void) {

    int data [] = { 3, 5 , 6, 2, 1, 10, 4};
    int len = sizeof(data)/sizeof(int);
    int i = 0;
    sort(data,0,len-1);
    for(i=0;i<len;i++)
        printf("%d ",data[i]);

    return EXIT_SUCCESS;
}

Answer 8

这是我的答案。它本质上与 VladimFromUa 的答案（冒泡排序的递归变体）相同，但不是执行固定数量的运行，而是仅在检测到数组在上一次运行中重新排序时才执行额外的运行。

另外两个差异如下：

1. 通过在递归调用中偏移数组地址，删除了数组中索引起始点的参数。
2.Vlad 中的检查“if(first0)”或我的代码中的“if (--p_length == 1)”最好在递归调用之前执行，这会导致数组长度为 1，因为它在堆栈上少了一次调用。

为了方便起见，我添加了一些代码来从命令行读取输入并打印未排序和排序的数组。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef enum { FALSE, TRUE } boolean_t;

void
swap_int(int *a, int *b) {

    int temp = *a;

    *a = *b;
    *b = temp;
}

boolean_t
sort_array(int p_array[], int p_length) {

    boolean_t result;

    if (p_array[0] > p_array[1]) {
        swap_int(p_array, p_array + 1);
        result = TRUE;
    } else {
        result = FALSE;
    }

    if (--p_length == 1) {
        return result;
    }

    result |= sort_array(p_array + 1, p_length);

    if (result) {
        sort_array(p_array, p_length);
    }

    return result;
}

void
print_array_int(int p_array[], int p_length) {

    int n;

    for (n = 0; n < p_length - 1; n++) {
        printf("%d, ", p_array[n]);
    }

    printf("%d\n", p_array[n]);
}

int
main(int argc, char **argv) {

    int *array;
    int array_length = argc - 1;
    int n;

    array = malloc(array_length * sizeof(*array));

    for (n = 0; n < array_length; n++) {
        sscanf(argv[n + 1], "%d", array + n);
    }

    printf("\nUnsorted array:\n");
    print_array_int(array, array_length);
    sort_array(array, array_length);
    printf("\nSorted array:\n");
    print_array_int(array, array_length);

return 0;
}

Answer 9

这种解决方案怎么样：

package recursive.bubble;

public class RecursiveBubble {

    public static boolean sort(int []arr){
        if(!bubbleSorted(arr, 0)){
            return sort(arr);
        }
        return true;
    }
    public static boolean bubbleSorted(int []a,int index){    
        if(a.length<2){
            return true;
        }
        if(index==a.length-2){
            if(a[index+1]<a[index]){
                swap(a,index,index+1);
                return false;
            }
            return true;
        }
        boolean isSorted=false;
        if(a[index]<=a[index+1]){
            isSorted=true;
        }else{
            swap(a,index,index+1);
        }
        return isSorted && bubbleSorted(a, index+1);
    }
    private static void swap(int[] a, int index, int i) {
        int tmp=a[index];
        a[index]=a[i];
        a[i]=tmp;
    }
    public static void main(String[] args) {
        int []a={4,5,6,2,2,3,9,1,8};
        if(sort(a))
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

Answer 10

def bubble_sort(l):
    for i, num in enumerate(l):
        try:
            if l[i+1] < num:
                l[i] = l[i+1]
                l[i+1] = num
                bubble_sort(l)
        except IndexError:
            pass
    return l

Answer 11

#include <stdio.h>
void bubbleSort(int *,int ,int ,int );
void swap(int *, int *);
void printArray(int *,int);

int main()
{
    int n,c;

    printf("Enter number of elements\n");
    scanf("%d", &n);

    int array[n];

    printf("Enter %d integers\n", n);

    for (c = 0; c < n; c++)
        scanf("%d", &array[c]);

    printf("Before Sorting:\n");
    printArray(array,n);

    bubbleSort(array,0,0,n);

    printf("After Soring:\n");
    printArray(array,n);

 }

 void bubbleSort(int *array,int i,int j,int n)
 {
     if(j==n-i-1)
     {
         i = i+1;
         j = 0;
     }
     if(i==n-1)
         return;

     if(array[j]>array[j+1])
         swap(&array[j],&array[j+1]);

     j++;
     bubbleSort(array,i,j,n);
 }

 void swap(int *p,int *q)
 {
     int t = *q  ;
     *q = *p;
     *p = t;
 }

 void printArray(int *array,int n)
 {
     int c=0;
     for (c = 0; c < n; c++)
        printf("%d ", array[c]);
    printf("\n");
 }

Answer 12

这是scala函数代码。一切都是一成不变的。这就是尾递归。所以堆栈应该没问题

def sort(initial: List[Int], result: List[Int] = Nil): List[Int] = {

  def getBiggest(list: List[Int], rest: List[Int] = Nil): (List[Int], Int) = list match {
    case x1 :: x2 :: tail =>
      if(x1 > x2)
        getBiggest(x1 :: tail, x2 :: rest)
      else
        getBiggest(x2 :: tail, x1 :: rest)
    case x :: Nil => (rest, x)
  }

  initial match {
    case _ :: _ :: _ =>
      getBiggest(initial) match {
        case (rest, biggest) => sort(rest, biggest :: result)
      }
    case x :: Nil => x :: result
    case Nil => Nil
  }
}

Answer 13

这是另一个 javascript 递归版本，其中包含一些 es6/7 语法，例如默认参数：

let unsorted = [4, 2, 4, 99, 1, 1, 5];

const bubSort = (arr, end = 0) => {
  // base case
  if (end >= arr.length) {
    return arr;
  }

  // bubble sort, goes through once
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i + 1]) {
      // swap!
      let hold = arr[i + 1];
      arr[i + 1] = arr[i];
      arr[i] = hold;
    }
  }

  // down the rabbit hole; updating `end` is a small optimization
  return bubSort(arr, ++end);
}

const sorted = bubSort(unsorted);
console.log(sorted);

Answer 14

package com.examplehub.sorts;

public class BubbleSortRecursion implements Sort {
  @Override
  public void sort(int[] numbers) {
    sortRecursion(numbers, numbers.length);
  }

  /**
   * BubbleSort algorithm implements using recursion.
   *
   * @param numbers the numbers to be sorted.
   * @param length the length of numbers.
   */
  public void sortRecursion(int[] numbers, int length) {
    boolean swapped = false;
    for (int i = 0; i < length - 1; ++i) {
      if (numbers[i] > numbers[i + 1]) {
        int temp = numbers[i];
        numbers[i] = numbers[i + 1];
        numbers[i + 1] = temp;
        swapped = true;
      }
    }
    if (!swapped) {
      return;
    }
    sortRecursion(numbers, length - 1);
  }

  @Override
  public <T extends Comparable<T>> void sort(T[] array) {
    sortRecursion(array, array.length);
  }

  /**
   * Generic BubbleSort algorithm implements using recursion.
   *
   * @param array the array to be sorted.
   * @param length the length of array.
   * @param <T> the class of the objects in the array.
   */
  public <T extends Comparable<T>> void sortRecursion(T[] array, int length) {
    boolean swapped = false;
    for (int i = 0; i < length - 1; ++i) {
      if (array[i].compareTo(array[i + 1]) > 0) {
        T temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        swapped = true;
      }
    }
    if (!swapped) {
      return;
    }
    sortRecursion(array, length - 1);
  }
}

来源

Answer 15

戈兰：

// BubbleSortRecursive ...
func BubbleSortRecursive(data []int) {

    i := 0
    max := len(data)

    bubbleSortRecursive(data, i, max)
}

func bubbleSortRecursive(data []int, i, max int) {

    fmt.Printf("data = %v, i = %v, max = %v\n", data, i, max)

    if i == max-1 {
        max--
        i = 0
    }

    if i < max-1 {
        if data[i] > data[i+1] {
            data[i], data[i+1] = data[i+1], data[i]
        }
        bubbleSortRecursive(data, i+1, max)
    }
}

Answer 16

希望这有帮助。

    public class Main {
public static void swapping(int[] arr2, int m, int n) {
    if (m == n) {
        return;
    }
    if (arr2[m - 1] > arr2[m]) {
        int temp = arr2[m];
        arr2[m] = arr2[m - 1];
        arr2[m - 1] = temp;
    }
    
    swapping(arr2, m + 1, n);
}

public static int[] recurrsionBubbleSort(int[] arr2, int n) {
    if (n == 1) {
        return arr2;
    }
    /*
    IF YOU DONT WANT TO USE ITERATION AT ALL, SKIP THIS STEP AND USE SWAPPING() FUNCTION.
    for(int j=1;j<n;j++){
        if(arr2[j-1]>arr2[j]){
            int temp=arr2[j];
                arr2[j]=arr2[j-1];
                arr2[j-1]=temp;
        }
    }
    */
    swapping(arr2, 1, n);
    recurrsionBubbleSort(arr2, n - 1);
    
    return arr2;
}

public static void main(String[] args) {

    int[] arr2 = new int[] {8,2,4,5,1,0,7,6};
    System.out.println("Sorting using recursion");
    recurrsionBubbleSort(arr2, arr2.length);
    for (int i = 0; i < arr2.length; i++) {
        System.out.println(arr2[i]);
    }
 }
}

Answer 17

Bubble sort: recursive and efficient

public static void bubbleSort(int[] ele, int counter, int index) {
            int temp=-1;
            if (counter < ele.length) {
                if (index < ele.length - 1) {
                    if (ele[index] > ele[index+1]) {
                        ele[index] += ele[index+1];
                        ele[index+1] = ele[index] - ele[index+1];
                        ele[index] = ele[index] - ele[index+1];
                        temp = ele[index];
                    }
                    bubbleSort(ele, counter, index+1);
                    //temp = sortedIndex;
                    return;
                }
                if(counter == ele.length-1 && temp==-1){
                    return;
                }
                bubbleSort(ele, counter+1, 0);
            }

        }