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

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

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

@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循环相当模糊,它基本上将数组分为一个head(第一个元素)和一个tail(所有其他元素)。Haskell使用符号x:xs来完成,但批处理文件使用一个名为for循环的/f开关来完成。为什么?为什么不呢?

SETLOCAL和ENDLOCAL调用让我们可以执行局部变量——某种程度上。SETLOCAL为我们提供了原始变量的完整副本,但当我们调用ENDLOCAL时,所有更改都被完全删除,这意味着您甚至无法使用全局变量与调用函数通信。这就解释了难看的“ENDLOCAL&set return=%sorted%”语法,不管逻辑指示什么,它实际上都可以工作。当执行该行时,由于该行尚未执行,所以排序后的变量未被擦除-然后,由于该行已执行,所以返回变量未被擦除。必然的

这是我不久前写的一个更清晰的版本:

@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