quicksort - OZ 语言中的快速排序算法

Question

以下 OZ 程序使用内置分区函数来执行快速排序算法。需要使用原有的分区方案而不是内置的分区函数来修改程序。我搜索并找到了2个原始方案：Lomuto分区方案和Hoare分区方案，但我无法修改程序（我是OZ语言的新手）！所需的两种分区方案在 Wikipedia 中的以下链接中进行了说明：https ://en.wikipedia.org/wiki/Quicksort

我试图修改的 OZ 程序：

声明 fun {QuickSort Xs} case Xs of nil then nil [] Pivot|Xr then fun {IsSmaller X} X

Answer 1

proc {Partition Xs Pivot Left Right}
   case Xs
   of X|Xr then
      if X < Pivot
      then Ln in
         Left = X | Ln
         {Partition Xr Pivot Ln Right}
      else Rn in
         Right = X | Rn
         {Partition Xr Pivot Left Rn}
      end
   [] nil then Left=nil Right=nil
   end
end

fun lazy {LQuickSort Xs}
   case Xs of X|Xr then Left Right SortedLeft SortedRight in
      {Partition Xr X Left Right}
      {LAppend {LQuickSort Left} X|{LQuickSort Right}}
   [] nil then nil
   end
end