如何實現這種氣泡排序？

我正在尋找實施氣泡排序。我寫了下面的代碼，它使用do循環內的for循環。我怎樣才能做到這一點使用兩個for循環的泡沫排序？如何實現這種氣泡排序？

這裏是我的代碼：

do { 
    switched = false; 
    for (int i = 1; i < size; i++) { 
     if (a[i] < a[i-1]) { 
      int temp = a[i]; 
      a[i] = a[i-1]; 
      a[i-1] = temp; 
      switched = true; 
     } 
    } 
} while (switched);

（這是標記的功課，但是這是期末考試，沒有實際的功課學習）

來源

2011-12-19 Moshe

「我期待實施泡沫排序」 - 這是您的問題！（說真的，爲什麼他們會繼續堅持教Bubblesort的使用......） –

@MitchWheat，實現bubblesort只是教學排序的開始......並且它可以幫助您瞭解其他排序技術。 –

你不應該從零開始？ –

因爲你知道在列表的最後一個元素將始終進行排序（因爲它冒泡到頂部），你可以停在那裏。

for(int x = size; x >= 0; x--) { 
    bool switched = false; 
    for(int i = 1; i < x; i++) { 
     if(blah) { 
      // swap code here 
      switched = true; 
     } 

    } 
    if(!switched) break; // not the biggest fan of this but it gets the job done 
}

來源

2011-12-19 23:14:40 corsiKa

這是你的教授正在尋找的答案。 –

如果你不喜歡'break'，你可以在條件中做'i

@Jon對CS101作業進行評分之前，是的，我同意。這將是教授最可能尋找的東西，特別是關於「最近最高元素」總是如何排序的小片段。 – corsiKa

有點專，但是，嘿，你自找的：

for(bool switched=true; switched;) 
{ 
    switched = false; 
    for (int i = 1; i < size; i++) { 
     if (a[i] < a[i-1]) { 
      int temp = a[i]; 
      a[i] = a[i-1]; 
      a[i-1] = temp; 
      switched = true; 
     } 
    } 
}

兩個for循環...

來源

2011-12-19 23:09:00 sehe

我不想upvote，因爲...哇，這很糟糕！同時，我不想低調，因爲它是聰明的，2）是正確的。撕裂！ – corsiKa

你應該被報告對'for'陳述的殘忍待遇！ –

@glowcoder：隨意不投票。評論非常感謝！我在這個快速回答和jabby評論之間被撕碎了:) – sehe

可以運行內環size次而不是檢查switched，通過具有外部循環for(int j=0; j<size; ++j)。爲了使效率稍低一點，你可以讓內循環每次縮短一步。

來源

2011-12-19 23:13:23

循環的第一次完整傳遞（即您的外部do循環的第一次循環）將保證位置爲a[size - 1]的最大元素。（你知道爲什麼嗎？）接下來的全面檢查保證不會改變，和，此外，把第二大元素a[size - 2]位置。（再次，你明白爲什麼？）等等。所以第一遍需要i去從1到size - 1，但第二隻需要i去從1到size - 2，第三隻需要i去從1到size - 3，等等。總體而言，你需要最多size - 1通行證（含最後一關只是遮蓋位置1和比較a[1]到a[0]以確保最小的元件到位）。

所以，你的外for -loop需要改變max_i，初始設置爲size - 1和1結束了，和你的內心for -loop需要從1變化i到max_i。

來源

2011-12-19 23:14:08 ruakh

想想do循環可以執行的最大次數。

來源

2011-12-19 23:18:16

由於內循環運行的最大次數爲size次，因此您知道外循環只能由size約束。

for (int x = 0; x < size; x++) 
{ 
    switched = false; 
    for (int i = 1; i < size; i++) 
    { 
     if (a[i] < a[i - 1]) 
     { 
      int temp = a[i]; 
      a[i] = a[i - 1]; 
      a[i - 1] = temp; 
      switched = true; 
     } 
    } 

    if(switched) 
    { 
     break; 
    } 
}

來源

2011-12-19 23:19:35

一個非常愚蠢的方法使用兩個for循環將如下所示：

for(bool switched=true;switched;) 
{ 
    switched=false; 
    for(int i=1; i<size; ++i) 
    { 
     if (a[i] < a[i-1]) 
     { 
      int temp = a[i]; 
      a[i] = a[i-1]; 
      a[i-1] = temp; 
      switched = true; 
     } 
    } 
}

更嚴重的答案可能如下是...但現在，我想想這可能不是冒泡排序：

for(int i=0; i<(size-1); ++i) 
{ 
    for(int j=(i+1); j<(size-1); ++j) 
    { 
     if(a[i]>a[j]) 
     { 
      temp=a[i]; 
      a[i]=a[j]; 
      a[j]=temp; 
     } 
    } 
}

來源

2011-12-19 23:19:50

一個簡單的改進，冒泡排序是要記住的最後位置的交換髮生的位置。每次通過之後，超出該點的元素將被排序。下次只通過循環迭代到先前的高位標記。

void bubble_sort(int *arr, int size) 
{ 
    for (int hwm; size > 1; size = hwm) 
    { 
     hwm = 0; 
     for (int i = 1; i < size; ++i) 
     { 
      if (arr[i] < arr[i-1]) 
      { 
       std::swap(arr[i], arr[i-1]); 
       hwm = i; 
      } 
     } 
    } 
}

來源

2011-12-20 01:02:37 Blastfurnace

如何實現這種氣泡排序？

回答

相關問題