哪種排序算法是這樣的？

-5

我正在努力與這種排序算法，但無法找出算法在互聯網上的名稱。
另外我需要知道這種算法在Big-O格式中的複雜性。

代碼是：哪種排序算法是這樣的？

int i,j; 

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

來源

2014-05-10 user3618573

請一次只問一個問題。原因是你只能將一個答案標記爲已接受，所以如果兩個不同的答案分別回答你的一個問題，你就不能標出一個正確答案，從而造成未來訪問者的混淆。 –

關於你的第一個問題（算法名稱），* *我個人認爲這是一個很好的問題，即使你應該描述你發現的類似算法的工作大致相同，爲什麼你認爲他們仍然不同於算法所示。 –

我認爲tihs是一個單一的問題，如果有人知道這個算法他/她也可以回答複雜性我想，以便未來的訪問者可以同時學習:) – user3618573

這是冒泡排序與O(n²)一個時間複雜度和的O(1)的空間複雜度（其就地操作）。

查看the Wikipedia article瞭解更多信息。

來源

2014-05-10 11:24:50

這是一個optimized version of bubble sort。它利用了冒泡排序在第n遍中找到第n個最大元素的事實，因此它不必查看每次迭代中最後的n-1項。

在維基百科上的最優化形式的僞代碼：

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

您顯示的代碼實現第二for循環的優化，因爲第二循環停止時i == j，從而避免與去年比較n-1元素。

可以通過使用swapped變量在沒有交換操作發生時立即停止進一步優化。

當涉及到運行時間時，最好的情況下（當所有元素都已排序時）冒泡排序的最差情況性能爲O(n^2)和O(n)。但是，由於您的代碼沒有使用變量swapped儘可能早地停止，因此它是清除O(n^2)。

來源

2014-05-10 11:25:17

哪種排序算法是這樣的？

回答

相關問題