c# - 在 C# 中使用递归进行冒泡排序

Question

我写了这段简单的代码。我对此有一个小问题。

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

我觉得调用 sort 4 时间不是最好的解决方案。我还需要一种使用 sort() 来处理这个问题的方法。我还征求您的意见、建议或提示。谢谢

Answer 1

首先，您的排序仅限于整数，但是您可以使用 IComparable<T>接口(interface)将其扩展到任何可比较的类型。或者，您可以为 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);
}

但是，迭代解决方案可能会更有效且更易于理解...