冒泡排序算法實現

Question

我學習的冒泡排序算法，我碰到貫徹它，我的問題是，這是更好，爲什麼2種方式？

for(k=0;k<array.length-1;k++){ 
      if(array[k] > array[k+1]){ 
       int temp = array[k]; 
       array[k] = array[k+1]; 
       array[k+1] = temp; 
      } 
     } 

---

第二比約其

for(i=array.length-1;i>=0;i--){ 
     for(k=0;k<i;k++){ 
      if(array[k] > array[k+1]){ 
       int temp = array[k]; 
       array[k] = array[k+1]; 
       array[k+1] = temp; 
      } 
     } 
     } 

Answer 1

更多孰優孰劣 - 其所有關於這一個排在陣列第一和答案是第二屆一個

檢查this獲得更多的想法

Answer 2

你實現第一次沒有使正確排序becouse算法可以切換僅2相鄰的元素。

Ex。

輸入數據{6,5,4,3,2}

第一次迭代使這 - > {5,6,4,3,2}和現在5是第一位置，並且沒有機會改變這一立場，becouse循環索引（k）爲1，而進一步的迭代會增加..

冒泡排序需要2路總是

public static void bubbleSort(int[] array){ 
    for (int i = 0; i < array.length - 1; i++) { 
     for (int j = 0; j < array.length - i - 1; j++) { 
      if(array[j] < array[j+1]){ 
       int tmp = array[j]; 
       array[j] = array[j+1]; 
       array[j+1] = tmp; 
      } 
     } 
    } 
} 

Answer 3

不要使用冒泡（使用插入排序代替）。

編輯：

由於人們不斷向下投票這一點，請閱讀http://warp.povusers.org/grrr/bubblesort_misconceptions.html

冒泡是帕累託效率低，因爲它既是慢，難度比例如插入排序和選擇排序理解。只是不要使用（也不教）Bubblesort。

Answer 4

我發現更高效的維基百科（http://en.wikipedia.org/wiki/Bubble_sort）

procedure bubbleSort(A : list of sortable items) 
    n = length(A) 
    repeat 
     newn = 0 
     for i = 1 to n-1 inclusive do 
      if A[i-1] > A[i] then 
      swap(A[i-1], A[i]) 
      newn = i 
      end if 
     end for 
     n = newn 
    until n = 0 
end procedure 

Answer 5

第二個將數組進行排序。但是，只有在上次迭代中至少有一次交換時，纔可以通過運行來減少第二次循環中的比較。

Answer 6

你的第一個解決方案將無法工作，它不會對數組進行排序。但第二個方法會起作用，它會將數據從最小到最大排序。有關詳細說明，請參見下文：

嘛，後面冒泡排序算法的想法是要經過數據的陣列/集，而比較每對相鄰的項目，並交換他們，如果他們是在錯誤的順序。重複傳遞數組/列表直到不需要交換，這表明列表/數組已排序。 時間複雜度：爲O（n^2）。和我們將使用原始數組的空間。請使用以下數組說明上述段落中的說明：

//array of integer to be sorted 
    int[] arrayToSort=new int[]{1,7,81,2,-2,9,9,6,-6}; 
    //repeat until we're done sorting 
    while (true){ 
     //flag to check if we did swap number(s) 
     boolean didSort=false; 
     /* 
     * this inner loop is being used to find numbers that need to be  
     * swapped and then help in swapping them 
     */ 
     for(int count=0;count<arrayToSort.length-1;count++){ 
      //check if we need to swap 
      if(arrayToSort[count]>arrayToSort[count+1]){ 
       int temp=arrayToSort[count+1]; 
       arrayToSort[count+1]=arrayToSort[count]; 
       arrayToSort[count]=temp; 
       //set our swap flag so that we will know that we did swap 
       didSort=true; 
      } 

     } 

     //check we did a swap in our last inner loop iteration if not will 
     //be done sorting, then break the outer loop 
     if(!didSort){ 
      break; 
     } 
    } 

    //let's print the sorted array. 
    for(int i=0;i<arrayToSort.length;i++){ 
     System.out.print(arrayToSort[i]+", "); 
    }