sorting - 如何使用批处理文件实现快速排序？

Question

虽然通常情况下总是为工作选择正确的语言是件好事，但有时尝试用一种非常不合适的语言做一些事情可能会很有启发性。

1. 它可以帮助您更好地理解问题。也许您不必按照您认为的方式解决问题。
2. 它可以帮助您更好地理解语言。也许它支持的功能比您想象的还要多。

并将这个想法推向不合逻辑的结论...您将如何在批处理文件中实现快速排序？这可能吗？

Answer 1

事实证明，这并不像您想象的那么难。语法非常丑陋，但批处理语法实际上能够完成一些令人惊讶的事情，包括递归、局部变量和一些令人惊讶的复杂字符串解析。不要误会我的意思，这是一种糟糕的语言，但令我惊讶的是，它并没有完全瘫痪。我认为我没有学到任何有关快速排序的知识，但我学到了很多有关批处理文件的知识!

无论如何，这里是批处理文件中的快速排序 - 我希望您在阅读它时能够像我在编写它时一样享受尝试理解奇怪语法的乐趣。 :-)

@echo off
SETLOCAL ENABLEDELAYEDEXPANSION

call :qSort %*
for %%i in (%return%) do set results=!results! %%i
echo Sorted result: %results%
ENDLOCAL
goto :eof

:qSort
SETLOCAL
    set list=%*
    set size=0
    set less=
    set greater=
    for %%i in (%*) do set /a size=size+1
    if %size% LEQ 1 ENDLOCAL & set return=%list% & goto :eof
    for /f "tokens=2* delims== " %%i in ('set list') do set p=%%i & set body=%%j
    for %%x in (%body%) do (if %%x LEQ %p% (set less=%%x !less!) else (set greater=%%x !greater!))
    call :qSort %less%
    set sorted=%return%
    call :qSort %greater%
    set sorted=%sorted% %p% %return%
ENDLOCAL & set return=%sorted%
goto :eof

通过给它一组要在命令行上排序的数字来调用它，用空格分隔。示例:

C:\dev\sorting>qsort.bat 1 3 5 1 12 3 47 3
Sorted result:  1 1 3 3 3 5 12 47

这段代码有点难以理解。它基本上是标准的快速排序。关键是我们将数字存储在字符串中——穷人的数组。第二个 for 循环非常晦涩，它基本上将数组分成头(第一个元素)和尾(所有其他元素)。 Haskell 使用符号 x:xs 来完成此操作，但批处理文件使用/f 开关调用的 for 循环来完成此操作。为什么？为什么不呢？

SETLOCAL 和 ENDLOCAL 调用让我们可以处理局部变量 - 某种程度。 SETLOCAL 为我们提供了原始变量的完整副本，但是当我们调用 ENDLOCAL 时，所有更改都将被完全删除，这意味着您甚至无法使用全局变量与调用函数进行通信。这解释了丑陋的“ENDLOCAL & set return=%sorted%”语法，尽管逻辑表明它实际上有效。当执行该行时，排序变量尚未被删除，因为该行尚未执行 - 然后返回变量不会被删除，因为该行已经被执行。符合逻辑!

此外，有趣的是，您基本上不能在 for 循环中使用变量，因为它们无法更改 - 这消除了 for 循环的大部分意义。解决方法是设置 ENABLEDELAYEDEXPANSION ，它可以工作，但会使语法比正常情况更难看。请注意，我们现在拥有仅通过名称引用的变量的混合，通过在它们前面添加一个 % 前缀，通过在它们前面添加两个 %，通过将它们包装在 % 中，或者通过将它们包装在 ! 中。而且这些引用变量的不同方式几乎完全不可互换!

除此之外，应该还是比较容易理解的!