萬一添加破到冒泡排序陣列已經排序

我現在有一個（有點雜亂）冒泡排序的對象陣列的所謂的「排序」，代碼如下萬一添加破到冒泡排序陣列已經排序

object storage = 0; 
for (int i = 0; i < sorted.Length; i++) 
{ 
    for (int c = 0; c < sorted.Length - 1; c++) 
    { 
     if (sorted[c].ToString().CompareTo(sorted[c + 1].ToString()) > 0) 
     { 
      storage = sorted[c + 1]; 
      sorted[c + 1] = sorted[c]; 
      sorted[c] = storage; 
     } 
    } 
    return sorted;

問題是無論如何這個函數總是循環遍歷數組。假設「排序」數組可能是一個大數組，並且恰好恰好已經被排序，在這種情況下，該函數仍然會掃描數組並且工作一段時間，這是我想要阻止的。所以問題是，如果數組已被排序，我該如何正確地停止循環？

來源

2017-09-01 c-shark

沒有內置函數來檢查數組是否排序或不是。在每種情況下，您都需要訪問數組的每個元素。排序數組的最佳時間複雜度爲O（n）。 –

插入排序是否適合您？它對於已排序的數組具有O（n）時間複雜度。 – jumper0x08

有一個更一般的優化，你可以限制內循環到最後一次迭代進行交換的位置。 –

氣泡排序會將數組的最大（最小）元素向數組的最後冒泡。這是你的內在循環所做的。首先，您可以利用n次迭代後最後n個元素已經排序的知識，這意味着您的內部循環不需要檢查（n + 1）個元素中的最後n個元素，迭代。其次，如果內部循環沒有改變任何東西，那麼這些元素必須已經在序列中，這對於外部循環的中斷是一個好的點。

既然你這樣做是爲練習練習，我將離開編碼給你:-)

來源

2017-09-01 08:14:36 Ronald

更好，但仍然不是'最佳'的氣泡排序。這是矛盾的。 –

是的，關於更優化優化的評論會讓它更好。理所當然的。這是我第二點的概括。 – Ronald

爲什麼不使用OrderBy而不是自己排序呢？

sorted = sorted.OrderBy(s=> s).ToArray();

如果你堅持使用冒泡排序，你可以這樣做：

bool changed; 
for (int i = 0; i < sorted.Length; i++) 
{ 
    changed = false; 
    for (int c = 0; c < sorted.Length - 1; c++) 
    { 
     if (sorted[c].ToString().CompareTo(sorted[c + 1].ToString()) > 0) 
     { 
      changed = true; 
      storage = sorted[c + 1]; 
      sorted[c + 1] = sorted[c]; 
      sorted[c] = storage; 
     } 
     if(!changed) break; 
    }

我在第一循環設置更改爲false各一次。如果最後沒有改變，那麼數組已經排序。

來源

2017-09-01 08:05:13

只需練習不同的東西，泡沫排序是其中之一:) –

看看我編輯的答案 –

-1

試試這個：

object storage = 0; 
for (int i = 0; i < sorted.Length; i++) 
{ 
    bool swapped = false; 
    for (int c = 0; c < sorted.Length - 1; c++) 
    { 
     if (sorted[c].ToString().CompareTo(sorted[c + 1].ToString()) > 0) 
     { 
      storage = sorted[c + 1]; 
      sorted[c + 1] = sorted[c]; 
      sorted[c] = storage; 
      swapped = true; 
     } 
    } 
    if (!swapped) 
    { 
     break; 
    } 
}

如果它獲得通過沒有通過交換，然後對數組進行排序，因此會break。

來源

2017-09-01 08:13:36 Enigmativity

萬一添加破到冒泡排序陣列已經排序

回答

相關問題