“Quicksort for Just 2 Elements” 可以翻译为 “仅用于两个元素的快速排序”。

huangapple go评论71阅读模式
英文:

Quicksort for Just 2 Elements

问题

在《算法图解》中,作者为快速排序的基本情况提供了以下代码:

def quicksort(array):
  if len(array) < 2:
    # 基本情况,包含0或1个元素的数组已经“排序”
    return array

然后写道:“让我们看看更大的数组。一个具有两个元素的数组也很容易排序 - 检查第一个元素是否小于第二个元素,如果不是,就交换它们。”

稍后在示例中,他写道:“嗯,快速排序的基本情况已经知道如何排序包含两个元素的数组。”

我不明白这是如何实现的。是否有一步丢失了?当然,代码可以工作,但我看不到算法的哪个部分明确处理了包含两个元素的列表,所以请问如何对包含两个元素的列表进行排序呢?也就是说,如何检查第一个元素是否小于第二个元素,如果不是,则交换它们的逻辑在哪里?

完整的算法如下:

def quicksort(array):
  if len(array) < 2:
    # 基本情况,包含0或1个元素的数组已经“排序”
    return array
  else:
    # 递归情况
    pivot = array[0]
    # 所有小于枢轴的元素子数组
    less = [i for i in array[1:] if i <= pivot]
    # 所有大于枢轴的元素子数组
    greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3])
英文:

In "Grokking Algorithms", the author gives this code for the base case of a quicksort implementation:

def quicksort(array):
  if len(array) &lt; 2:
    # base case, arrays with 0 or 1 element are already &quot;sorted&quot;
    return array

and then writes "Let's look at bigger arrays. An array with with two elements is pretty easy to sort, too - check if the first elements is smaller than the second, and of it isn't, swap them."

A bit later, walking through an example, he writes "Well, the quicksort base case already knows how to sort arrays of two elements."

I can't see how this is so. Isn't there a missing step? The code works, of course, but I see not part of the algorithm which explicitly handles a 2-element list, so how does a list of 2 elements get sorted please? I.e. where is the logic to "check if the first elements is smaller than the second, and of it isn't, swap them"?

The full algorithm is below:

def quicksort(array):
  if len(array) &lt; 2:
    # base case, arrays with 0 or 1 element are already &quot;sorted&quot;
    return array
  else:
    # recursive case
    pivot = array[0]
    # sub-array of all the elements less than the pivot
    less = [i for i in array[1:] if i &lt;= pivot]
    # sub-array of all the elements greater than the pivot
    greater = [i for i in array[1:] if i &gt; pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3])

答案1

得分: 1

根据注释,已经有0或1个元素的数组是已经 "sorted"。

len(array) < 2

考虑一个包含两个元素的列表 [2, 1]

pivot = array[0] # pivot = 2
less = [i for i in array[1:] if i <= pivot] # less = [1]
greater = [i for i in array[1:] if i > pivot]  # greater = []
return quicksort(less) + [pivot] + quicksort(greater)

现在我们知道该函数会返回单个元素,所以
这个函数返回

return less + [pivot] + greater
return [1] +  [2]  + []
return [1, 2]

类似地,对于有序的元素也适用

[1, 2]
pivot = array[0] # pivot = 1
less = [i for i in array[1:] if i <= pivot] # less = []
greater = [i for i in array[1:] if i > pivot]  # greater = [2]
return quicksort(less) + [pivot] + quicksort(greater)
return [] + [1] + [2]
return [1, 2]
英文:

As per the comment, arrays with 0 or 1 element are already "sorted"

len(array) &lt; 2

Consider a list of two elements [2, 1]

pivot = array[0] # pivot = 2
less = [i for i in array[1:] if i &lt;= pivot] # less = [1]
greater = [i for i in array[1:] if i &gt; pivot]  # greater = []
return quicksort(less) + [pivot] + quicksort(greater)

Now we know that the function returns single elements as is, so
this function returns

return less + [pivot] + greater
return [1] +  [2]  + []
return [1, 2]

Similarly, this works for elements in order

[1, 2]
pivot = array[0] # pivot = 1
less = [i for i in array[1:] if i &lt;= pivot] # less = []
greater = [i for i in array[1:] if i &gt; pivot]  # greater = [2]
return quicksort(less) + [pivot] + quicksort(greater)
return [] + [1] + [2]
return [1, 2]

答案2

得分: 1

你应该看一下# 递归情况

# 递归情况
pivot = array[0]
# 所有小于pivot的元素的子数组
less = [i for i in array[1:] if i <= pivot]
# 所有大于pivot的元素的子数组
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)

如果有2个元素的情况下,lessgreater其中一个将会是空列表,而另一个(非空)将根据它们的大小被连接到第一个元素(pivot)的左边或右边。

顺便说一下,快速排序算法对于非常短的数组效果不佳,通常建议使用一些更简单的算法,比如冒泡排序,如果元素数量小于,比如说,五个。

英文:

You should take a look at the # recursive case:

# recursive case
pivot = array[0]
# sub-array of all the elements less than the pivot
less = [i for i in array[1:] if i &lt;= pivot]
# sub-array of all the elements greater than the pivot
greater = [i for i in array[1:] if i &gt; pivot]
return quicksort(less) + [pivot] + quicksort(greater)

In case of 2 elements, either less or greater will be an empty list, and the other one (non-empty) will be concatenated to the first element (pivot) on the left on the right side depending on being larger or smaller.

BTW. the quicksort algorithm does not work well for very short arrays, the common wisdom is to use something simpler, like even bubble sort if the number of the elements is less than, say, five.

huangapple
  • 本文由 发表于 2020年1月3日 23:49:20
  • 转载请务必保留本文链接:https://go.coder-hub.com/59581472.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定