2010-12-03 85 views
5

我和一位朋友討論了以下兩種算法的實際泡沫排序,以及哪一個更好,沒有提及哪一個是我的,我只是想聽到關於這兩個算法的這兩個問題的答案(用C++編寫)哪一個是真正的Bubble Sort,哪個更好?

1 - 哪一個是真正的氣泡排序?
2 - 哪個更好?

這裏有兩種算法:

// Number one : 
void BubbleSort(int Arr[], int size) 
{ for (int i=0;i<size-1;i++) 
     for (int j=i+1;j<size;j++) 
      if (Arr[i]>Arr[j]) 
      { int temp = Arr[i]; 
       Arr[i] = Arr[j]; 
       Arr[j] = temp; 
}   } 

// Number two : 
void BubbleSort(int Arr[], int size) 
{ for (int i=0;i<size-1;i++) 
     for (int j=0;j<size-1;j++) 
      if (Arr[j]>Arr[j+1]) 
      { int temp = Arr[j]; 
       Arr[j] = Arr[j+1]; 
       Arr[j+1] = temp; 
}   } 
+3

應該注意的是,冒泡排序決不應該用在任何類型的生產代碼中,因爲它與其他基於比較的排序(比如插入排序)相比顯然很糟糕,例如,它很容易實現,但幾乎勝過冒泡排序(if並非全部)情況。我甚至走得很遠,並且說不應該再教導泡沫排序。 – helpermethod 2010-12-03 17:21:17

+2

Python在大廳裏,第二扇門在右邊。認真:使用C縮進;不要掩飾它。 – pmg 2010-12-03 18:16:14

回答

11

二號更接近真實的。所有的比較應該在相鄰的元素之間。

但真正的冒泡排序將採取while循環,而不是外for循環,而while循環會再次執行只有當要素對最後一關被換,像這樣:

void BubbleSort(int Arr[], int size) 
{ 
    bool swapped; 
    do { 
     swapped = false; 
     for (int j=0;j<size-1;j++) 
      if (Arr[j]>Arr[j+1]) { 
       int temp = Arr[j]; 
       Arr[j] = Arr[j+1]; 
       Arr[j+1] = temp; 
       swapped = true; 
      } 
    } while (swapped); 
} 
+3

我認爲每次傳球后你都需要重新初始化爲假,否? – 2010-12-03 17:25:00

1

對於嵌套循環冒泡排序的僞碼是:

procedure bubbleSort(A : list of sortable items) 
    n := length(A)-1 
    for(i=0; i<= n; i++) 
    for(j=n; j>i; j--) 
     if A[j-1] > A[j] then 
      swap (A[j-1], A[j]) 
     end if 
    end for 
    end for 
end procedure 

這意味着第一最接近因爲內環僅在元件迭代i之後。你展示的第二種方法有一個內部循環遍歷所有元素,即使我之前的元素已經被排序,所以沒有必要浪費時間。

這意味着第一種方法也更好。

1

問題#2的答案:兩者都不是「更好」。兩者都是O(n^2)排序算法(這很糟糕)。除了對排序算法的介紹之外,Bubble Sort是無用的。