Как отсортировать массив в Bash

Question

У меня есть массив в Bash, например:

array=(a c b f 3 5)

Мне нужно отсортировать массив.Не просто отображать содержимое отсортированным способом, но чтобы получить новый массив с отсортированными элементами.Новый отсортированный массив может быть совершенно новым или старым.

Answer 1

Вам не нужно столько кода:

IFS=$'\n' sorted=($(sort <<<"${array[*]}"))
unset IFS

Поддерживает пробелы в элементах (если это не перевод строки), и работает в Bash 3.x.

например:

$ array=("a c" b f "3 5")
$ IFS=$'\n' sorted=($(sort <<<"${array[*]}"))
$ printf "[%s]\n" "${sorted[@]}"
[3 5]
[a c]
[b]
[f]

Примечание: @sorontar имеет указал , что необходимо соблюдать осторожность, если элементы содержат символы подстановки, такие как *или ?:

Часть sorted = ($ (...)) использует оператор «split and glob».Вы должны отключить glob: set -f или set -o noglob или shopt -op noglob, или элемент массива, такой как *, будет расширен до списка файлов.

Что происходит:

Результатом является кульминация шести вещей, которые происходят в следующем порядке:

1. IFS=$'\n'
2. "${array[*]}"
3. <<<
4. sort
5. sorted=($(...))
6. unset IFS

Во-первых, IFS=$'\n'

Это важная частьнашей операции, которая влияет на результат 2 и 5 следующим образом:

Дано:

• "${array[*]}" распространяется на каждый элемент, ограниченный первым символом IFS
• sorted=() создает элементы путем разбиения на каждый символ IFS

IFS=$'\n' устанавливает элементы так, чтобы элементы расширялись с использованием aновая строка в качестве разделителя, а затем создается таким образом, что каждая строка становится элементом.(т. е. разделение на новую строку.)

Важное значение имеет разделение новой строкой, поскольку именно так работает sort (сортировка по строке).Разделение только на * - новая строка не так важна, но необходима для сохранения элементов, содержащих пробелы или табуляции.

Значение по умолчанию IFS равно пробел , табуляция , за которой следует новая строка , и она будет непригодна для нашей операции.

Далее, sort <<<"${array[*]}" part

<<<, называемый здесь строки , принимает расширение "${array[*]}", как описано выше, и подает его на стандартный ввод sort.

В нашем примере sort подается следующая строка:

a c
b
f
3 5

Так как sort сортирует , он выдает:

3 5
a c
b
f

Далее,sorted=($(...)) part

Часть $(...), называемая подстановка команд , заставляет ее содержимое (sort <<<"${array[*]}) запускаться как обычная команда, принимаярезультирующий стандартный вывод в качестве литерала, который идет туда, где когда-либо был $(...).

В нашем примере это производит нечто похожее на простое написание:

sorted=(3 5
a c
b
f
)

sorted затемстановится массивом, который создается путем разделения этого литерала на каждую новую строку.

Наконец, unset IFS

Это сбрасывает значение IFS к значению по умолчанию, и это просто хорошая практика.

Это сделано для того, чтобы мы не создавали проблем ни с чем, что опирается на IFS позже в нашем скрипте.(В противном случае нам нужно помнить, что мы все изменили - что может быть непрактично для сложных сценариев.)

Answer 2

Исходный ответ:

array=(a c b "f f" 3 5)
readarray -t sorted < <(for a in "${array[@]}"; do echo "$a"; done | sort)

вывод:

$ for a in "${sorted[@]}"; do echo "$a"; done
3
5
a
b
c
f f

Примечание эта версия работает со значениями, содержащими специальные символы или пробел ( кроме переводы строки)

Примечание readarray поддерживается в bash 4+.

---

Редактировать Основываясь на предложении @Dimitre, я обновил его до:

readarray -t sorted < <(printf '%s\0' "${array[@]}" | sort -z | xargs -0n1)

, что дает преимущество даже понимания сортировка элементов с символами новой строки, вставленными правильно.К сожалению, как правильно сообщил @ruakh, это не означало, что результат readarray будет правильный , потому что readarray не имеет возможности использовать NUL вместо обычных новых строк как разделители строк.

Answer 3

Вот простая реализация быстрой сортировки Bash:

#!/bin/bash

# quicksorts positional arguments
# return is in array qsort_ret
qsort() {
   local pivot i smaller=() larger=()
   qsort_ret=()
   (($#==0)) && return 0
   pivot=$1
   shift
   for i; do
      if [[ $i < $pivot ]]; then
         smaller+=( "$i" )
      else
         larger+=( "$i" )
      fi
   done
   qsort "${smaller[@]}"
   smaller=( "${qsort_ret[@]}" )
   qsort "${larger[@]}"
   larger=( "${qsort_ret[@]}" )
   qsort_ret=( "${smaller[@]}" "$pivot" "${larger[@]}" )
}

Использовать как, например,

$ array=(a c b f 3 5)
$ qsort "${array[@]}"
$ declare -p qsort_ret
declare -a qsort_ret='([0]="3" [1]="5" [2]="a" [3]="b" [4]="c" [5]="f")'

Эта реализация является рекурсивной ... так что вот итерационная быстрая сортировка:

#!/bin/bash

# quicksorts positional arguments
# return is in array qsort_ret
# Note: iterative, NOT recursive! :)
qsort() {
   (($#==0)) && return 0
   local stack=( 0 $(($#-1)) ) beg end i pivot smaller larger
   qsort_ret=("$@")
   while ((${#stack[@]})); do
      beg=${stack[0]}
      end=${stack[1]}
      stack=( "${stack[@]:2}" )
      smaller=() larger=()
      pivot=${qsort_ret[beg]}
      for ((i=beg+1;i<=end;++i)); do
         if [[ "${qsort_ret[i]}" < "$pivot" ]]; then
            smaller+=( "${qsort_ret[i]}" )
         else
            larger+=( "${qsort_ret[i]}" )
         fi
      done
      qsort_ret=( "${qsort_ret[@]:0:beg}" "${smaller[@]}" "$pivot" "${larger[@]}" "${qsort_ret[@]:end+1}" )
      if ((${#smaller[@]}>=2)); then stack+=( "$beg" "$((beg+${#smaller[@]}-1))" ); fi
      if ((${#larger[@]}>=2)); then stack+=( "$((end-${#larger[@]}+1))" "$end" ); fi
   done
}

В обоих случаях вы можете изменить используемый порядок: я использовал сравнение строк, но вы можете использовать арифметические сравнения, сравнивать время изменения файла и т. Д., Просто используйте соответствующий тест; вы даже можете сделать его более общим и использовать его в качестве первого аргумента, который используется тестовой функцией, например,

#!/bin/bash

# quicksorts positional arguments
# return is in array qsort_ret
# Note: iterative, NOT recursive! :)
# First argument is a function name that takes two arguments and compares them
qsort() {
   (($#<=1)) && return 0
   local compare_fun=$1
   shift
   local stack=( 0 $(($#-1)) ) beg end i pivot smaller larger
   qsort_ret=("$@")
   while ((${#stack[@]})); do
      beg=${stack[0]}
      end=${stack[1]}
      stack=( "${stack[@]:2}" )
      smaller=() larger=()
      pivot=${qsort_ret[beg]}
      for ((i=beg+1;i<=end;++i)); do
         if "$compare_fun" "${qsort_ret[i]}" "$pivot"; then
            smaller+=( "${qsort_ret[i]}" )
         else
            larger+=( "${qsort_ret[i]}" )
         fi
      done
      qsort_ret=( "${qsort_ret[@]:0:beg}" "${smaller[@]}" "$pivot" "${larger[@]}" "${qsort_ret[@]:end+1}" )
      if ((${#smaller[@]}>=2)); then stack+=( "$beg" "$((beg+${#smaller[@]}-1))" ); fi
      if ((${#larger[@]}>=2)); then stack+=( "$((end-${#larger[@]}+1))" "$end" ); fi
   done
}

Тогда у вас может быть эта функция сравнения:

compare_mtime() { [[ $1 -nt $2 ]]; }

и использование:

$ qsort compare_mtime *
$ declare -p qsort_ret

для сортировки файлов в текущей папке по времени изменения (сначала самое новое).

Примечание. Эти функции являются чистыми Bash! никаких внешних утилит, и никаких оболочек! они безопасны относительно любых забавных символов, которые у вас могут быть (пробелы, символы новой строки, символы глобуса и т. д.).

Answer 4

Если вам не нужно обрабатывать специальные символы оболочки в элементах массива:

array=(a c b f 3 5)
sorted=($(printf '%s\n' "${array[@]}"|sort))

С bash вам все равно понадобится внешняя программа сортировки.

При zsh внешние программы не требуются, а специальные символы оболочки легко обрабатываются:

% array=('a a' c b f 3 5); printf '%s\n' "${(o)array[@]}" 
3
5
a a
b
c
f

ksh имеет set -s для сортировки ASCIIbetically .

Answer 5

В 3-часовой поездке на поезде из Мюнхена во Франкфурт (до которой мне было трудно добраться, потому что завтра начинается Октоберфест), я думал о своем первом посте.Использование глобального массива - гораздо лучшая идея для общей функции сортировки.Следующая функция обрабатывает произвольные строки (переводы строк, пробелы и т. Д.):

declare BSORT=()
function bubble_sort()
{   #
    # @param [ARGUMENTS]...
    #
    # Sort all positional arguments and store them in global array BSORT.
    # Without arguments sort this array. Return the number of iterations made.
    #
    # Bubble sorting lets the heaviest element sink to the bottom.
    #
    (($# > 0)) && BSORT=("$@")
    local j=0 ubound=$((${#BSORT[*]} - 1))
    while ((ubound > 0))
    do
        local i=0
        while ((i < ubound))
        do
            if [ "${BSORT[$i]}" \> "${BSORT[$((i + 1))]}" ]
            then
                local t="${BSORT[$i]}"
                BSORT[$i]="${BSORT[$((i + 1))]}"
                BSORT[$((i + 1))]="$t"
            fi
            ((++i))
        done
        ((++j))
        ((--ubound))
    done
    echo $j
}

bubble_sort a c b 'z y' 3 5
echo ${BSORT[@]}

Это печатает:

3 5 a b c z y

Тот же вывод создается из

BSORT=(a c b 'z y' 3 5) 
bubble_sort
echo ${BSORT[@]}

Обратите внимание, что, вероятно, Bash внутренне использует smart-указатели, поэтому операция подкачки может быть дешевой (хотя я сомневаюсь в этом).Тем не менее, bubble_sort демонстрирует, что более продвинутые функции, такие как merge_sort, также доступны для языка оболочки.

Answer 6

tl; dr :

Сортировать массив a_in и сохранить результат в a_out (элементы не должны иметь внедренных новых строк ^[1] ):

Bash v4 +:

readarray -t a_out < <(printf '%s\n' "${a_in[@]}" | sort)

Bash v3:

IFS=$'\n' read -d '' -r -a a_out < <(printf '%s\n' "${a_in[@]}" | sort)

Преимущества более решение antak :

• Вам не нужно беспокоиться о случайном смещении (случайное восприятие элементов массива как шаблонов имени файла), поэтому для отключения сглаживания не требуется дополнительная команда(set -f и set +f, чтобы восстановить его позже).

• Вам не нужно беспокоиться о сбросе IFS с unset IFS. ^[2]

---

Необязательное чтение: пояснение и пример кода

Приведенное выше объединяет код Bash с внешней утилитой sort для решения, которое работает с произвольными одиночными линейными элементами и лексической или числовой сортировкой (необязательно по полю) :

• Производительность : Для около 20 или более элементов , это будет на быстрее , чем чистое решение Bash - значительно и все больше, когда вы преодолеете около 100 элементов.
  ^{(Точные пороговые значения будут зависеть от вашего конкретного входа, машины и платформы.)}

  • Причина, по которой это быстро, заключается в том, что избегает петель Bash .

• printf '%s\n' "${a_in[@]}" | sort выполняет сортировку (лексически, по умолчанию - см. sort POSIX spec ):

  • "${a_in[@]}" безопасно расширяется до элементов массива a_in как отдельных аргументов , независимо от того, что они содержат (включая пробелы).

  • printf '%s\n' затем печатает каждый аргумент, т. Е. Каждый элемент массива, в отдельной строке, как есть.

• Обратите внимание на использование замены процесса (<(...)) для предоставления отсортированного вывода в качестве входных данных дляread / readarray (через перенаправление на стандартный ввод, <), потому что read / readarray должен работать в current shell (не должен запускаться в subshell ), чтобы выходная переменная a_out была видна текущей оболочке (чтобы переменная оставалась определенной в оставшейся части скрипта).

• Чтение вывода sort в переменную массива :

  • Bash v4 +: readarray -t a_out читает вывод отдельных строк как sort в элементы переменной массива a_out, без включения конечного \n в каждом элементе (-t).

  • Bash v3: readarray не существует,поэтому необходимо использовать read:
    IFS=$'\n' read -d '' -r -a a_out указывает read прочитать в массив (-a) переменную a_out, прочитать весь ввод через строки (-d ''), но разбить его на массивэлементы по новым строкам(IFS=$'\n'.$'\n', который производит буквальный перевод строки (LF), является так называемой строкой в ​​кавычках ANSI C ).
    (-r, параметр, который практически всегда должен использоваться с read, отключает неожиданную обработку \ символов.)

Аннотированный пример кода:

#!/usr/bin/env bash

# Define input array `a_in`:
# Note the element with embedded whitespace ('a c')and the element that looks like
# a glob ('*'), chosen to demonstrate that elements with line-internal whitespace
# and glob-like contents are correctly preserved.
a_in=( 'a c' b f 5 '*' 10 )

# Sort and store output in array `a_out`
# Saving back into `a_in` is also an option.
IFS=$'\n' read -d '' -r -a a_out < <(printf '%s\n' "${a_in[@]}" | sort)
# Bash 4.x: use the simpler `readarray -t`:
# readarray -t a_out < <(printf '%s\n' "${a_in[@]}" | sort)

# Print sorted output array, line by line:
printf '%s\n' "${a_out[@]}"

Из-заиспользование sort без параметров дает лексическую сортировку (цифры сортируются перед буквами, а последовательности цифр обрабатываются лексически, а не как числа):

*
10
5
a c
b
f

Если вы хотите числовая сортировка по 1-му полю, вы бы использовали sort -k1,1n вместо просто sort, что приводит к (не числа сортируются перед числами, а числа сортируются правильно):

*
a c
b
f
5
10

---

^{[1] Для обработки элементов со встроенными символами новой строки используйте следующий вариант (Bash v4 +, с GNU sort):
readarray -d '' -t a_out < <(printf '%s\0' "${a_in[@]}" | sort -z).
Полезный ответ Михаила Гурни имеет решение Bash v3.}

^{[2] В то время как IFS установлено в варианте Bash v3, tизменение ограничено командой .
Byнапротив, то, что следует за IFS=$'\n' в ответе антака, является назначением , а не командой, и в этом случае изменение IFS равно global .}

Answer 7

Другое решение, которое использует внешний sort и справляется с любыми специальными символами (за исключением NUL :)). Должен работать с bash-3.2 и GNU или BSD sort (к сожалению, POSIX не включает -z).

local e new_array=()
while IFS= read -r -d '' e; do
    new_array+=( "${e}" )
done < <(printf "%s\0" "${array[@]}" | LC_ALL=C sort -z)

Сначала посмотрите на перенаправление ввода в конце. Мы используем printf встроенный для записи элементов массива, заканчивающихся нулем. Заключение в кавычки гарантирует, что элементы массива передаются как есть, а специфика оболочки printf заставляет ее повторно использовать последнюю часть строки формата для каждого оставшегося параметра. То есть это эквивалентно чему-то вроде:

for e in "${array[@]}"; do
    printf "%s\0" "${e}"
done

Список элементов с нулевым символом в конце затем передается в sort. Опция -z заставляет его читать элементы с нулевым символом в конце, сортировать их и выводить также символ с нулевым символом в конце. Если вам нужно было получить только уникальные элементы, вы можете передать -u, поскольку он более переносим, ​​чем uniq -z. LC_ALL=C обеспечивает стабильный порядок сортировки независимо от локали - иногда полезно для сценариев. Если вы хотите, чтобы sort уважал язык, удалите его.

Конструкция <() получает дескриптор для чтения из порожденного конвейера, а < перенаправляет на него стандартный ввод цикла while. Если вам нужен доступ к стандартному вводу внутри канала, вы можете использовать другой дескриптор - упражнение для читателя:).

Теперь вернемся к началу. Встроенный read считывает вывод с перенаправленного стандартного ввода. Установка пустого IFS отключает разделение слов, которое здесь не нужно - в результате read считывает всю «строку» ввода в единственную предоставленную переменную. Опция -r отключает обработку escape, которая также нежелательна. Наконец, -d '' устанавливает разделитель строки в NUL, то есть read говорит читать строки с нулем в конце.

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

Конечно, это только один из многих способов достижения той же цели. На мой взгляд, это проще, чем реализовать полный алгоритм сортировки в bash, а в некоторых случаях это будет быстрее. Он обрабатывает все специальные символы, включая символы новой строки, и должен работать в большинстве распространенных систем. Самое главное, он может научить вас чему-то новому и удивительному в bash:).

Answer 8

мин сортировка:

#!/bin/bash
array=(.....)
index_of_element1=0

while (( ${index_of_element1} < ${#array[@]} )); do

    element_1="${array[${index_of_element1}]}"

    index_of_element2=$((index_of_element1 + 1))
    index_of_min=${index_of_element1}

    min_element="${element_1}"

        for element_2 in "${array[@]:$((index_of_element1 + 1))}"; do
            min_element="`printf "%s\n%s" "${min_element}" "${element_2}" | sort | head -n+1`"      
            if [[ "${min_element}" == "${element_2}" ]]; then
                index_of_min=${index_of_element2}
            fi
            let index_of_element2++
        done

        array[${index_of_element1}]="${min_element}"
        array[${index_of_min}]="${element_1}"

    let index_of_element1++
done

Answer 9

попробуйте это:

echo ${array[@]} | awk 'BEGIN{RS=" ";} {print $1}' | sort

Вывод будет:

3
5
a
b
c
f

Проблема решена.

Answer 10

array=(a c b f 3 5)
new_array=($(echo "${array[@]}" | sed 's/ /\n/g' | sort))    
echo ${new_array[@]}

Эхо-содержимое new_array будет:

3 5 a b c f