冒泡排序 - 爲什麼附加循環

這裏是數組：冒泡排序 - 爲什麼附加循環

var ar = [1,2,7,3];

排序它必須有在上環3次迭代在內環3,2,1迭代。所以我寫了一個算法來做到這一點：

function sort() { 
    var i,j; 
    for (i=1; i < ar.length; i++) { 
     for (j=0; j < ar.length - i; j++) { 
      if (ar[j] > ar[j+1]) { 
       ar.swap(j, j+1); 
      } 
     } 
    } 
}

然後我檢查了執行here：

function bubbleSort(items){ 

    var len = items.length, 
     i, j, stop; 

    for (i=0; i < len; i++){ 
     for (j=0, stop=len-i; j < stop; j++){ 
      if (items[j] > items[j+1]){ 
       items.swap(j, j+1); 
      } 
     } 
    } 

    return items; 
}

現在，該算法在上環和4,3,2 4次迭代，在給定數組的內部循環中進行1次迭代。我不明白爲什麼，我錯過了什麼？

來源

2016-02-14 AngularInDepth.com

你假設，當然，在鏈接的算法是在任何方面的權威冒泡實現 –

是的，不是嗎？它是由尼古拉斯Zakas頁，誰是JS –

的大師，他可能是JS的大師 - 並不能讓他實現冒泡的大師......你的循環6次，他的循環14次，optimizied循環5次... 4個元素已經爲了你...循環6次，他的循環14次，優化的循環3次 –

這裏是一個優化的冒泡排序 - 這是高效是你的，在最壞的情況 - 但更有效的接近排序的原數組是

function swap(a, i, j, t) { // dirty hack for swap 
    t = a[i]; 
    a[i] = a [j]; 
    a[j] = t; 
} 
function bubbleSortOptimized(items) { 
    var newn, i, n = items.length; 
    do { 
     newn = 0 
     for(i = 1; i < n; i+=1) { 
      if (items[i-1] > items[i]) { 
       swap(items, i-1, i); 
       newn = i; 
      } 
     } 
     n = newn 
    } 
    while(n); 
    return items; 
}

的方式，對數組沒有交換方法 - 不知道你是如何運行代碼

來源

2016-02-14 08:59:54

哪裏是這種方法的描述？ –

@Maximus - 我不明白的問題。 –

我說的是算法的名稱，如冒泡排序，選擇排序等等，這樣我可以google一下 –

基本上optimized Bubble Sort是停止的時候有在當前迭代沒有掉，因爲它會到那個時候，這在最好的情況（已排序）完全排序將產生O(n)時間複雜度，可以這樣寫：

Demo

function bubbleSort(items) 
{ 
    var len = items.length, i, j, t; 
    var swaps = 0; 

    for (i=0; i < len; i++) 
    { 
     swaps = 0; 

     for (j=0; j < len-i; j++) 
     { 
      if (items[j] > items[j+1]) 
      { 
       t = items[j]; 
       items[j] = items[j+1]; 
       items[j+1] = t; 

       swaps++; 
      } 
     } 

     // stop when there were no swaps in current iteration 
     if (swaps === 0) break; 
    } 

    return items; 
}

來源

2016-02-14 08:42:59

冒泡排序 - 爲什麼附加循環

回答

相關問題