如何在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[*]}")); unset IFS
$ printf "[%s]\n" "${sorted[@]}"
[3 5]
[a c]
[b]
[f]

注意: @sorontar 指出,如果元素包含通配符,例如*或?:

sorted =($(...))部分使用"split and glob"运算符.你应该关掉glob:set -for 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' 进行设置以便使用新行作为分隔符扩展元素,然后以每行成为元素的方式创建元素.(即拆分新线.)

通过新线划分非常重要,因为这就是sort操作方式(每行排序).仅按新行拆分并不重要,但需要保留包含空格或制表符的元素.

默认值IFS是空格,制表符,后跟新行,并且不适合我们的操作.

接下来,sort <<<"${array[*]}"部分

<<<在这里称为字符串,"${array[*]}"如上所述,进行扩展,并将其输入到标准输入中sort.

在我们的示例中,sort输入以下字符串:

a c
b
f
3 5

自从sort 分类以来,它产生:

3 5
a c
b
f

接下来,sorted=($(...))部分

这个$(...)名为命令替换的部分使其content(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

请注意,此版本处理包含特殊字符或空格的值(换行符除外)

注意 bash 4+支持readarray.

编辑根据@Dimitre的建议,我已将其更新为:

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

这有利于甚至理解正确嵌入换行符的排序元素.不幸的是,正如@ruakh正确发出信号这并不意味着结果readarray是正确的,因为readarray没有选择使用NUL而不是常规换行作为行分隔符.

Answer 3

这是一个纯粹的Bash quicksort实现:

#!/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
}

在这两种情况下,您都可以更改您使用的顺序:我使用字符串比较,但您可以使用算术比较,比较wrt文件修改时间等,只需使用相应的测试; 你甚至可以使它更通用,并让它使用第一个参数,即测试函数使用,例如,

#!/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

如果您不需要处理数组元素中的特殊shell字符:

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

使用bash,无论如何你都需要一个外部排序程序.

使用zsh不需要外部程序,并且可以轻松处理特殊的shell字符:

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

ksh必须set -s按ASCII排序.

Answer 5

tl;博士:

对数组进行排序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解决方案相比的优势:

• 您不必担心意外的globbing(将数组元素意外解释为文件名模式),因此不需要额外的命令来禁用globbing(set -f并set +f在以后恢复它).

• 你不必担心重新IFS使用unset IFS.^[2]

可选阅读:说明和示例代码

上面将Bash代码与外部实用程序结合使用,sort以获得适用于任意单行元素以及词法或数字排序(可选地按字段)的解决方案:

• 性能:对于大约20个或更多元素,这将比纯Bash解决方案更快 - 一旦超过大约100个元素,显着且越来越多.
  ^{(确切的阈值取决于您的具体输入,机器和平台.)}

  • 它快速的原因是它避免了Bash循环.

• printf '%s\n' "${a_in[@]}" | sort 执行排序(词法上,默认情况下 - 请参阅sortPOSIX规范):

  • "${a_in[@]}"安全地扩展到数组的元素a_in作为单独的参数,无论它们包含什么(包括空格).

  • printf '%s\n' 然后按原样打印每个参数 - 即每个数组元素 - 在它自己的行上.

• 注意使用进程substitution(<(...))来提供排序输出作为read/的输入readarray(通过重定向到stdin <),因为read/ readarray必须在当前 shell中运行(不能在子shell中运行),以便输出变量a_out可见到当前shell(使变量保持在脚本的其余部分中定义).

• 将sort输出读入数组变量:

  • Bash v4 +:readarray -t a_out将输出的各行读sort入数组变量的元素a_out,而不包括\n每个元素中的尾部(-t).

  • Bash v3:readarray不存在,所以read必须使用:
    IFS=$'\n' read -d '' -r -a a_outtell readto read into array(-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

如果你想通过第一个字段进行数字排序,你可以使用sort -k1,1n而不是仅仅sort产生(数字之前的非数字排序,数字排序正确):

*
a c
b
f
5
10

^{[1]为了处理元件具有嵌入换行符,使用下列变型(击V4 +,与GNU sort):
readarray -d '' -t a_out < <(printf '%s\0' "${a_in[@]}" | sort -z).
MichałGórny的有用答案有一个Bash v3解决方案.}

^{[2]当IFS 被在Bash V3变体设置,所述变化是作用域到命令.
相比之下,IFS=$'\n' 在antak的回答中接下来的是赋值而不是命令,在这种情况下,IFS变化是全局的.}

Answer 6

在从慕尼黑到法兰克福的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内部可能使用智能指针,因此交换操作可能很便宜(尽管我对此表示怀疑).但是,bubble_sort证明更多高级函数merge_sort也在shell语言的范围内.

Answer 7

另一个使用外部sort和处理任何特殊字符的解决方案(NULs除外:)).应该使用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内置来写出数组元素,零终止.引用确保数组元素按原样传递,并且shell的细节printf使其为每个剩余参数重用格式字符串的最后部分.也就是说,它等同于:

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

然后传递以null结尾的元素列表sort.该-z选项使它读取以null结尾的元素,对它们进行排序并输出以null结尾的元素.如果你只需要获得独特的元素,你可以通过,-u因为它比它更便携uniq -z.该LC_ALL=C独立保证稳定的排序顺序的语言环境-有时脚本很有用.如果您想要sort尊重语言环境,请删除它.

该<()构造获得要从生成的管道读取的描述符,并将循环<的标准输入重定向while到它.如果您需要访问管道内的标准输入,您可以使用另一个描述符 - 阅读器练习:).

现在,回到开头.该read内置读取重定向标准输入输出.设置为空IFS将禁用在此处不必要的分词 - 因此,read将输入的整个"行"读取到单个提供的变量.-r选项也禁用此处不需要的转义处理.最后,-d ''将行分隔符设置为NUL - 即告诉read读取以零结尾的字符串.

结果,对于每个连续的以零端接的数组元素执行一次循环,并将值存储在其中e.该示例只是将项目放在另一个数组中,但您可能更喜欢直接处理它们:).

当然,这只是实现同一目标的众多方式之一.在我看来,它比在bash中实现完整的排序算法更简单,在某些情况下它会更快.它处理所有特殊字符,包括换行符,并且应该适用于大多数常见系统.最重要的是,它可能会教你一些关于bash的新东西和令人敬畏的东西:).