2013-04-05 172 views
3

我有一個編碼雙向氣泡排序的作業分配。有人可以看看我的邏輯是否正確。我不想要代碼,因爲我想知道自己。我只想要一個邏輯檢查我的理解。雙向氣泡排序c#

正如我所理解的雙向氣泡排序,你實現了2 for循環,從列表中的位置1開始並執行正常的氣泡排序。當第一個for循環到達結尾時,第二個循環實現反向工作。我只是不完全明白每個循環的終止條件是什麼。

for for循環條件如下所示?

環1 - for(i = 0; i < Count -i; i++)

環2 - for(j = Count - i; j > i; j--)

在每個循環將被指定的交換條件

由於

+0

真棒排序視頻:http://www.youtube.com/watch?v=SJwEwA5gOkM – 2013-04-05 08:39:06

+0

這可能更多是http://programmers.stackexchange.com/或http://codereview.stackexchange.com/問題。 – 2013-04-05 08:39:19

+0

@TiesonT。雖然「程序員」可以合適,但「codereview」需要由OP編寫完整的,有效的代碼片段。 – dasblinkenlight 2013-04-05 08:40:32

回答

3

「經典」冒泡排序經過在每次迭代整個陣列,所以環路應該

for(i = 0; i < Count - 1; i++) 

for(j = Count - 1; j > 0; j--) 

兩個環路跳過一個指數:第一個循環跳過最後一個索引,而第二個循環跳過最後一個索引。這樣可以讓您的代碼安全地比較data[i]data[i+1]data[j]data[j-1]

EDIT"optimized"冒泡排序跳過上k次迭代的初始k元件。由於您的冒泡排序是雙向的,你就可以跳過初始k和尾k元素,像這樣:

int k = 0; 
do { // The outer loop 
    ... 
    for(int i = k; i < Count - k - 1; i++) 
     ... 
    for(int j = Count - k - 1; j > k ; j--) 
     ... 
    k++; 
} while (<there were swaps>); 
+0

因此,反向迭代不依賴於第一個循環的位置?即使循環1已經檢查了那些循環,它總是會進入位置1? – user2046257 2013-04-05 08:41:00

+1

@ user2046257正確,因爲第一個循環可能有移動元素在它檢查的數組部分,這是冒泡排序效率低下的原因之一 – dasblinkenlight 2013-04-05 08:44:17

+1

技術上,在第一次通過(即上和下)之後,你不再需要檢查第一個或最後一個元素,因爲它們是已知的成爲最低和最高的元素,所以我並不總是需要從0開始,j並不總是需要以0結束。 – Xantix 2013-04-05 08:51:48

2

雙向冒泡排序是這樣的:

,而不是從底部穿過名單每次頂部(氣泡排序),您將從列表的頂部開始一次在底部每第二次。

維基百科的文章做了更好的方式工作,在解釋它:

http://en.wikipedia.org/wiki/Cocktail_sort

- 豐富