为什么叫递归快速排序方式的不同？ [英] Why the different ways of calling quicksort recursively?

问题描述

我已经注意到，在快速排序的方法有差异被称为递归。

I've noticed a discrepancy in the way quicksort is called recursively.

的方法之一是

quicksort(Array, left, right)
  x = partition(Array, left, right)
  quicksort(Array, left, x-1)
  quicksort(Array, x+1, right)



  partition(array, left, right)
     pivotIndex := choose-pivot(array, left, right)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right]
     storeIndex := left
     for i from left to right - 1
         if array[i] ≤ pivotValue
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right]  // Move pivot to its final place
     return storeIndex

[例]

这是有道理的，因为快速排序的工作原理是分割周围的支点其他元素，该元素数组[X]应在其最终位置。因此，范围[左，partion-1]和[分区+ 1，右]仍然存在。

This makes sense because quicksort works by partitioning the other elements around the pivot so the element Array[x] should be in its final position. Therefore the range [left, partion-1] and [partition+1, right] remains.

的另一种方法

quicksort(Array, left, right)
  x = partition(Array, left, right)
  quicksort(Array, left, x)
  quicksort(Array, x+1, right)

PARTITION(A,p,r)

x  A[p]    
i  p - 1    
j  r + 1   
while TRUE  
   do repeat j  j - 1   
        until A[j]  x   
      repeat i  i + 1    
        until A[i]  x    
      if i < j    
          then exchange A[i]  A[j]
          else return j

[例]

注意-1缺失。这些似乎表明，该阵列正确的分区，但没有一个单一的元素是在其最终位置。这两种方式是不可互换的，如果我把在一个-1在第二方式的输入阵列不当排序。

Notice the -1 is missing. These seems to suggest that the array was partitioned correctly but no single element is in its final position. These two ways are not interchangeable, if I put in a -1 in the second way an input array is improperly sorted.

是什么原因导致的差异？显然，这是某处的划分方法，它都与霍尔的或Lumuto的算法使用？

What causes the difference? Obviously it's somewhere in the partition method, does it have to do with Hoare's or Lumuto's algorithm was used?

推荐答案

如果不出意外，排除或通过分区索引可能被关闭，半开间隔之间的差异：对可能是第一个索引不要碰 - 不从不完整的片段，告诉没有引用。

If nothing else, excluding or passing the partition index might be the difference between closed and half-open intervals: right might be the first index not to touch - no telling from incomplete snippets without references.

这篇关于为什么叫递归快速排序方式的不同？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！