哪种排序算法是这样的？

-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

哪种排序算法是这样的？

回答

相关问题