在C中使用递归进行气泡排序＃

我写过这段简单的代码。我有一个小问题。在C中使用递归进行气泡排序＃

int [] x = [50,70,10,12,129]; 
sort(x, 0,1); 
sort(x, 1,2); 
sort(x, 2,3); 
sort(x, 3,4); 

for(int i = 0; i < 5; i++) 
Console.WriteLine(x[i]); 

static int [] sort(int [] x, int i, int j) 
{ 
    if(j ==x.length) 
     return x; 
    else if(x[i]>x[j]) 
    { 
     int temp = x[i]; 
     x[i] = x[j]; 
     x[j] = temp; 
     return sort(x, i, j+1); 
    } 
    else 
     return sort(x, i, j+1); 
}

我觉得打电话排序4次不是最好的灵魂。我需要一种方法来处理这个使用sort（）也。我也会问你的建议，建议或提示。谢谢

来源

2009-10-29 Loai Nagati

是否有你滚动自己的sort（）方法，而不是使用Array.Sort（）或List.Sort（）？ – LBushkin 2009-10-29 15:16:27

是的，我想自己做！ – 2009-10-29 15:16:56

首先，您的排序仅限于整数，但您可以使用IComparable<T>接口将其扩展为任何可比类型。或者，您可以使用另一个参数Comparer<T>以允许用户定义如何比较输入中的项目。

递归冒泡排序可能会是这个样子：（注：未测试...）

public static T[] BubbleSort(T[] input) where T : IComparable<T> 
{ 
    return BubbleSort(input, 0, 0); 
} 

public static T[] BubbleSort(T[] input, int passStartIndex, int currentIndex) where T : IComparable<T> 
{ 
    if(passStartIndex == input.Length - 1) return input; 
    if(currentIndex == input.Length - 1) return BubbleSort(input, passStartIndex+1, passStartIndex+1); 

    //compare items at current index and current index + 1 and swap if required 
    int nextIndex = currentIndex + 1; 
    if(input[currentIndex].CompareTo(input[nextIndex]) > 0) 
    { 
     T temp = input[nextIndex]; 
     input[nextIndex] = input[currentIndex]; 
     input[currentIndex] = temp; 
    } 

    return BubbleSort(input, passStartIndex, currentIndex + 1); 
}

然而，迭代求解可能会更有效，更容易理解......

来源

2009-10-29 15:36:40 Lee

简单bubblesort不应该需要递归。你可以做这样的事情，只是通过阵列排序：

public int[] Sort(int[] sortArray) 
    { 
     for (int i = 0; i < sortArray.Length - 1; i++) 
     { 
      for (int j = sortArray.Length - 1; j > i; j--) 
      { 
       if (sortArray[j] < sortArray[j - 1]) 
       { 
        int x = sortArray[j]; 
        sortArray[j] = sortArray[j - 1]; 
        sortArray[j - 1] = x; 

       } 
      } 
     } 
     return sortArray; 
    }

来源

2009-10-29 15:27:41 Robban

嗯，应用于递归算法时，“需要”总是很有趣，如果这是自我教育的练习，那么想要使用递归并不是不合理的。 – Murph 2009-10-29 15:37:03

也许Robban应该说泡沫排序不会自动递归。使用为递归设计的算法对递归排序进行编码可能更具教育意义。当然，这取决于OP希望学习什么。 – 2009-10-29 15:46:34

我可以做到不递归。但是，如果我使用递归，我只想看看事情会如何发展。这只是好奇心！ – 2009-10-29 17:48:22

想学习没有错 - 几件明显的事情。

首先，你已经意识到数组的长度属性 - 所以你可以使用它来创建一个循环，摆脱多个调用，在开始时进行排序，并使数组的长度不成问题。

其次，你可能想要考虑排序的工作方式 - 这个怎么样：你试图将一个值冒泡到列表中的正确位置（或者如果你愿意的话，可以放下！） - 对于列表n项，删除第一个，排序剩余的n - 1项（这是递归位），然后泡第一个项目到位。

去过十年因为我想过这个，好开心！

来源

2009-10-29 15:35:09 Murph

另一个只有2 PARAMS：对啊：

static void Sort(IList<int> data) 
{ 
    Sort(data, 0); 
} 

static void Sort(IList<int> data, int startIndex) 
{ 
    if (startIndex >= data.Count) return; 

    //find the index of the min value 
    int minIndex = startIndex; 
    for (int i = startIndex; i < data.Count; i++) 
     if (data[i] < data[minIndex]) 
      minIndex = i; 

    //exchange the values 
    if (minIndex != startIndex) 
    { 
     var temp = data[startIndex]; 
     data[startIndex] = data[minIndex]; 
     data[minIndex] = temp; 
    } 

    //recurring to the next 
    Sort(data, startIndex + 1); 
}

注：这是在现实生活中完全地无用的，因为 - 它非常缓慢 - 它的递归迭代是线性的意思，当你有超过1K的项目，它将stackoverflow

来源

2009-10-29 15:44:07

在C中使用递归进行气泡排序＃

回答

相关问题