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

虽然通常总是为工作选择合适的语言是好的,但有时候尝试用一种非常不合适的语言来做某事是有益的.

它可以帮助您更好地理解问题.也许你不必须要解决它,你以为你做的方式.

它可以帮助您更好地理解语言.也许它支持的功能比你意识到的要多.

将这个想法推到了不合逻辑的结论......你将如何在批处理文件中实现快速排序？它甚至可能吗？

事实证明,它并不像你想象的那么难.语法很丑陋,但批处理语法实际上能够提供一些令人惊讶的东西,包括递归,局部变量和一些令人惊讶的复杂的字符串解析.不要误会我的意思,这是一种可怕的语言,但令我惊讶的是,它并没有完全瘫痪.我不认为我学到了关于quicksort的任何知识,但我学到了很多关于批处理文件的知识!

在任何情况下,这里都是批处理文件中的快速排序 - 我希望你在阅读它的过程中尝试理解奇怪的语法,就像我在编写它时一样.:-)

@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,但使语法比平时更加​​丑陋.请注意,我们现在有一个由它们的名称引用的变量混合,通过在它们前面添加一个%,在它们前面添加两个%,通过将它们包装在%中,或者将它们包装在!中.这些不同的引用变量的方式几乎完全不可互换!

除此之外,它应该相对容易理解!

这是我之前写的一个更易读的版本:

@echo off

echo Sorting:  %*

set sorted=

:sort
:: If we've only got one left, we're done.
if "%2"=="" (
  set sorted=%sorted% %1
  :: We have to do this so that sorted gets actually set before we print it.
  goto :finalset
)
:: Check if it's in order.
if %1 LEQ %2 (
  :: Add the first value to sorted.
  set sorted=%sorted% %1
  shift /1
  goto :sort
)
:: Out of order.
:: Reverse them and recursively resort.
set redo=%sorted% %2 %1
set sorted=
shift /1
shift /1
:loop
if "%1"=="" goto :endloop
set redo=%redo% %1
shift /1
goto :loop
:endloop
call :sort %redo%
:: When we get here, we'll have already echod our result.
goto :eof

:finalset
echo Final Sort:  %sorted%
goto :eof

例:

C:\Path> sort 19 zebra blah 1 interesting 21 bleh 14 think 2 ninety figure it out

生产:

Sorting:  19 zebra blah 1 interesting 21 bleh 14 think 2 ninety figure it out
Final Sort:   1 2 14 19 21 blah bleh figure interesting it ninety out think zebra