Как реализовать быструю сортировку, используя пакетный файл?

Обновить

December 2018

Просмотры

3.8k раз

11

Хотя обычно это хорошо, чтобы всегда правильно выбрать язык для работы, иногда это может оказаться полезным, чтобы попытаться сделать что-то на языке, который дико неуместно.

  1. Это может помочь вам понять проблему лучше. Может быть , вы не должны решить это так , как вы думали , что вы сделали.
  2. Это может помочь вам понять язык лучше. Может быть, он поддерживает больше возможностей, чем вы поняли.

И толкая эту идею, что это нелогично заключение ... как бы реализовать быструю сортировку в пакетном файле? Возможно ли это?

2 ответы

5

Вот более разборчивая версия, которую я написал некоторое время назад:

@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
23

Оказывается, это не так сложно, как вы могли бы подумать. Синтаксис некрасиво, как ад, но партия синтаксис на самом деле способен некоторые удивительных вещи, в том числе рекурсии, локальных переменных, и некоторые удивительно сложный разбора строк. Не поймите меня неправильно, это ужасный язык, но, к моему удивлению, он не полностью калека. Я не думаю, что я узнал что-нибудь о быстрой сортировке, но я многое узнал о пакетных файлах!

В любом случае, здесь быстрая сортировка в пакетном файле - и я надеюсь, что вы так же весело, пытаясь понять странный синтаксис, читая его, как я сделал в то время его написания. :-)

@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

Код немного боли, чтобы понять. Это в основном стандарт быстрой сортировки. Ключевые биты, что мы хранение чисел в строке - массив бедняка. Второй цикл довольно неясные, это в основном разделение массива в голова (первый элемент) и хвост (все остальные элементы). Haskell делает это с обозначениями х: хз, но командные файлы делать это с циклом вызывается с параметром / ф. Зачем? Почему бы и нет?

В SETLOCAL и Endlocal вызовы позволяют нам делать локальные переменные - своего рода. SETLOCAL дает нам полную копию исходному переменному, но все изменения полностью уничтожены, когда мы называем Endlocal, что означает, что вы не можете даже общаться с вызывающей функцией с помощью глобал. Это объясняет некрасиво «ENDLOCAL и установить возвращение =% отсортировано%» синтаксис, который на самом деле работает, несмотря на то, что логика будет указывать. Когда линия выполнена отсортированный переменная не была уничтожена, потому что линия не была выполнена еще - то после этого переменная возврат не вытерли, потому что линия уже была выполнена. Логическое!

Кроме того, занятно, вы в принципе не можете использовать переменные для цикла, потому что они не могут изменить - которая удаляет большую часть точки, имеющий цикл. Чтобы обойти эту проблему, чтобы установить ENABLEDELAYEDEXPANSION, который работает, но делает синтаксис даже нелицеприятную, чем обычно. Заметьте, что мы теперь имеем сочетание переменных ссылочных только по имени, предваряя их с одного%, предваряя их двумя%, путем оборачивать их в%, или оборачивать их!. И эти различные способы привязки переменных почти полностью не взаимозаменяемы!

Кроме этого, она должна быть относительно легко понять!

Связанные вопросы