2

我需要在 SML 中为家庭作业实施快速排序，但我迷路了。我以前不熟悉快速排序是如何实现的，所以我阅读了它，但我读到的每个实现都是命令式的。这些看起来不太难，但我不知道如何在功能上实现快速排序。

维基百科恰好有标准 ML 中的快速排序代码（这是我的作业所需的语言），但我不明白它是如何工作的。

维基百科代码： 

val filt = List.filter
fun quicksort << xs = let
fun qs [] = []
 | qs [x] = [x]
 | qs (p::xs) = let
     val lessThanP = (fn x => << (x, p))
     in
       qs (filt lessThanP xs) @ p :: (qs (filt (not o lessThanP) xs))
     end
in
  qs xs
end

特别是，我不明白这一行：qs (filt lessThanP xs) @ p :: (qs (filt (not o lessThanP) xs)). filt 将返回 xs 中小于 p* 的所有内容的列表，该列表与 p 连接，后者被 cons-ed 到所有 >= p.*

*假设当 x < p 时 << (x, p) 函数返回 true。当然不必如此。

实际上，把这个写出来有助于我理解发生了什么。无论如何，我正在尝试将该 SML 函数与 wiki 的快速排序伪代码进行比较，如下所示。

函数快速排序（数组，“左”，“右”）

  // If the list has 2 or more items
  if 'left' < 'right'

      // See "Choice of pivot" section below for possible choices
      choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right'

      // Get lists of bigger and smaller items and final position of pivot
      'pivotNewIndex' := partition(array, 'left', 'right', 'pivotIndex')

      // Recursively sort elements smaller than the pivot
      quicksort(array, 'left', 'pivotNewIndex' - 1)

      // Recursively sort elements at least as big as the pivot
      quicksort(array, 'pivotNewIndex' + 1, 'right')

其中分区定义为

// left is the index of the leftmost element of the array
// right is the index of the rightmost element of the array (inclusive)
//   number of elements in subarray = right-left+1
function partition(array, 'left', 'right', 'pivotIndex')
  'pivotValue' := array['pivotIndex']
  swap array['pivotIndex'] and array['right']  // Move pivot to end
  'storeIndex' := 'left'
  for 'i' from 'left' to 'right' - 1  // left ≤ i < right
      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'

那么，分区到底发生在哪里？还是我错误地考虑了 SML 快速排序？

4

2 回答 2

3

那么，分区到底发生在哪里？还是我错误地考虑了 SML 快速排序？

快速排序的纯粹功能实现通过输入列表上的结构递归来工作（IMO，这值得一提）。此外，如您所见，对“filt”的两次调用允许您将输入列表划分为两个子列表（例如 A 和 B），然后可以单独处理它们。这里重要的是：

  • A 的所有元素都小于或等于枢轴元素（代码中的“p”）
  • B 的所有元素都大于枢轴元素

通过交换同一数组中的元素，命令式实现就地工作。在您提供的伪代码中，“partition”函数的后不变式是您有两个子数组，一个从输入数组的“left”开始（并在“pivotIndex”结束），另一个在“pivotIndex”之后开始' 并以 'right' 结尾。这里重要的是这两个子数组可以看作是子列表 A 和 B 的表示。

我认为到目前为止，您已经知道分区步骤发生在哪里（或者相反，命令式和函数式是如何相关的）。

于 2011-10-31T07:44:58.893 回答
1

你这样说：

filt 将返回 xs 中小于 p* 的所有内容的列表，该列表与 p 连接，后者被 cons-ed 到所有 >= p.*

这不太准确。 filt将返回 xs 中所有内容的列表p，但该新列表不会立即与p. 新列表实际上被传递给qs（递归地），并且任何qs返回都与p.

在伪代码版本中，分区发生在array变量中。这就是你swap在partition循环中看到的原因。就地进行分区比制作副本更能提高性能。

于 2011-10-31T02:58:36.660 回答