在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中使用遞歸進行氣泡排序＃

回答

相關問題