☰

如何对 POSIX sh 中的位置参数列表进行排序

tag-icon • tag-icon shell-script shell sort posix array
如何对 POSIX sh 中的位置参数列表进行排序

有没有办法对 POSIX sh 中的位置参数列表进行排序？每个位置参数可以包含任意字符（例如空格、换行符、制表符等）。排序算法应该足够通用，能够根据程序员定义的任何比较对列表进行排序（例如使用数字/字典排序expr比较、仅考虑每个位置参数的子字符串的排序等）。

看来POSIX sh的位置参数列表同时具有堆栈和队列的特征。它支持push( set -- "$x" "$@")、pop( x="$1"; shift)、enqueue( set -- "$@" "$x")和dequeue( x="$1"; shift)操作。但是，只能有一个列表，这意味着排序必须就地完成，并且我无法使用合并排序和快速排序等常见算法。

样本：

#!/bin/sh

set -- "Hello" "world" 9 8 7 "$(printf "0\n1")" "$(printf "1\t2")"

# How do I sort the positional parameters above using comparison
# `expr "$x" \< "$y"` such that the result is the list below?
#
# "$(printf "0\n1")" "$(printf "1\t2")" 9 8 7 "Hello" "world"

注 1：我正在寻找一种 POSIX 解决方案，适用于用户提供的任意位置参数和程序员指定的任意比较。

注2：我并不是想解决任何实际问题。我向自己挑战了这个sh排序问题，但我无法想出解决方案，所以我将其发布在 Stack Exchange 上。

答案1

可能最简单的方法是使用awk可以进行strcoll()、strcmp()和数字比较（包括浮点数）的方法。

为了避免重新发明轮子，我们可以使用 awk 的快速排序实现https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#AWK（GPLv2）。

然后使用（编辑：请进一步查看更好、更安全的方法）：

code=$(
  awk -v q="'" -- '
    code-from-that-link-above
    BEGIN {
      delete ARGV[0]
      n = qsortArbIndByValue(ARGV, sorted)
      printf "set --"
      for (i = 1; i <= n; i++) {
        s = ARGV[sorted[i]]
        gsub(q, q "\\" q q, s)
        printf " %s", q s q
      }
    }' "$@"
) || exit
eval "$code"

假设位置参数包含用户区域设置中的有效文本，并且列表足够小以适合命令行参数（以及 awk 的数组大小限制）。

如果操作数被识别为数字，则使用awk's运算符进行数字比较，否则进行比较。您可以通过将比较从to更改为强制比较（将语言环境固定为 C 进行比较），并通过更改为强制数字比较（也可以是 POSIX，但实际上不可移植），或者您始终可以编写自定义awk 函数来执行任何操作你想要的比较。<strcoll()strcoll()a < ba"" < b""strcmp()a+0 < b+0+a < +bcompare()

请注意，为了符合 POSIX 标准，该代码应该代替gsub(q, q "\\\\" q q, s)，gsub(q, q "\\" q q, s)但是后者，即使 POSIX 产生未指定的行为更具可移植性，因为前者不能正常工作，gawk除非$POSIXLY_CORRECT在环境中或 busybox 中awk。

如果不能保证数据是用户区域设置中的有效文本，则可以将区域设置设置为C，然后字符串将被视为字节数组并按strcmp()（在基于 ASCII 的系统上）排序，而不是按照用户的区域设置排序顺序。

给出可能是未指定行为的结果的东西是相当不舒服的，但转念一想，如果我们不输出类似 的输出，而是输出 ，eval那么应该可以使其可靠。awkset -- '3rd argument hoped to be quoted correctly' 'first' 'second'set -- "${3}" "${1}" "${2}"

这也应该更容易做到、更短、更高效：

code=$(
  awk -- '
    code-from-that-link-above
    BEGIN {
      delete ARGV[0]
      n = qsortArbIndByValue(ARGV, sorted)
      printf "set --"
      for (i = 1; i <= n; i++)
        printf " \"${%s}\"", sorted[i]
    }' "$@"
) || exit
eval "$code"

答案2

您需要首先使用 shell 对eval这些字符串进行排序，然后对结果进行排序，对排序后的字符串以及原始索引数组应用相同的操作。下面我来举例说明。

您当然可以在 shell 脚本中实现您自己的排序算法。因为该语言非常不适合这样的数据结构/算法，所以瞄准比它更复杂（理论上效率更低）的东西可能没有多大意义。冒泡排序。它会相当短、丑陋且搞笑。

  1. 您问题中给出的原始数组。
  2. 获取数组的长度，并用于seq生成数组 1, 2, …, N
  3. 创建一个长度相同的新数组，让 shell 评估原始条目的每个条目（这样就$(printf "0 \n"变成了0 \n）。这就是我们实际需要排序的内容
  4. 实现冒泡排序：
    1. 将第一个元素与第二个元素进行比较。如果第一个更大，根据您的排序标准（我不确定，您对此有点模糊），然后交换（使用临时变量）这两个值，以及相同位置
    2. 继续比较第二个和第三个；重复上面的规则；按顺序对每对值进行冲洗和重复。
    3. 在对倒数第二个元素与最后一个元素进行比较（和交换）后，再次从头开始（您可以停止比上一次运行更早地比较一个元素）
    4. 在某个时刻，你已经把一切都安排好了。停止！
  5. 使用重新排序的索引数组，您现在可以构造包含原始（未解释）值的重新排序的数组。

答案3

这是一个想法：

  • 在 中sh，对每个位置参数中的所有换行符和反斜杠字符进行转义，以便我们可以使用换行符作为分隔符。
  • 将换行符分隔的位置参数通过管道传输到awk。
  • 在 中awk，使用快速排序对参数进行排序，并将换行符分隔的排序后的参数写入标准输出。
  • 在 中，通过按换行符拆分，sh将未排序的位置参数列表替换为换行符分隔的排序参数。awk
  • 取消转义已排序位置参数列表中的所有换行符和反斜杠字符。

执行：

#!/bin/sh
# Run this shell script to sort this list of positional parameters:
set -- \
    'Hello' \
    '  0  1  ' \
    '' \
    '*' \
    '\0150\0151' \
    "$(printf '\a\b\e\f\n\r\t\v')" \
    '\a\b\e\f\n\r\t\v%%\\' \
    'qwerty
uiop' \
    '

new

lines

'

printf '====== NOT YET SORTED ======\n'
for param; do
    printf '%s' "$param" | od -ab
done

quicksort() {
    for param; do
        # * Escape newlines (newline -> "\n" [two characters]).
        #   Rationale:
        #   * To be able to use newline as AWK record separator.
        #   * To be able to use it as the shell's $IFS for separating records.
        # * Escape backslashes (backslash -> "\\" [two characters]).
        #   Rationale:
        #   * To distinguish between escaped newlines and the two-character
        #     string "\n" (escaped version: "\\n" [three-character string]).
        #   * To avoid special interpretation of backslashes when passed to
        #     `printf '%b' ...`.
        #
        # `sed` solution adapted from:
        # https://unix.stackexchange.com/questions/761885/how-to-convert-all-newlines-to-n-in-posix-sh-strings
        printf '%s\n' "$param" | LC_ALL=C sed '
            :1
            $ ! {
                N
                b1
            }
            s/\\/\\\\/g
            s/\n/\\n/g'
    done | awk -f ./quicksort.awk
}

# Create temporary file.
tmpfile="$(printf 'mkstemp(template)' \
    | m4 -D template="${TMPDIR:-/tmp}/XXXXXX")" || exit 1
exec 3>"$tmpfile" 4<"$tmpfile"  # Open tmpfile for writing and reading.
rm -f -- "$tmpfile"

quicksort "$@" >&3 3>&-

set --
while IFS= read -r line; do
    # Unescape backslashes and newlines.
    # To preserve trailing newlines (if any), insert a trailing character 'x'
    # and later remove it.
    elem="$(printf '%bx' "$line")"
    set -- "$@" "${elem%x}"
done <&4 4<&-

printf '\n====== SORTED RESULTS ======\n'
for param; do
    printf '%s' "$param" | od -ab
done

这是quicksort.awk：

# Takes newline-separated records from standard input and sorts them according
# to the `compare` function. Outputs the sorted newline-separated records to
# standard output.
#
# Backslash and newline characters supplied within each input record must be
# escaped like this:
# * backslash character -> "\\" (two backslash characters)
# * newline character -> "\n" (backslash character followed by the "n" character)
#
# Backslash and newline characters within each output record will be escaped in
# the same manner.
#
# Usage: awk -f quicksort.awk
#
# Attribution:
# Functions `quicksort` and `quicksort_swap` are adapted from the public domain
# quicksort implementation by Arnold Robbins retrieved from
# https://git.savannah.gnu.org/cgit/gawk.git/tree/awklib/eg/lib/quicksort.awk?h=gawk-5.3.0

function compare(a, b) {
    # Unescape backslashes and newlines.
    gsub(/\\/, "\\", a)
    gsub(/\\/, "\\", b)
    gsub(/\\n/, "\n", a)
    gsub(/\\n/, "\n", b)

    # For sorting in ascending lexicographic order.
    return a < b
}

function quicksort(data, left, right,    i, last) {
    if (left >= right)  # Do nothing if array contains fewer than two elements.
        return

    quicksort_swap(data, left, int((left + right) / 2))
    last = left
    for (i = left + 1; i <= right; i++)
        if (compare(data[i], data[left]))
            quicksort_swap(data, ++last, i)
    quicksort_swap(data, left, last)
    quicksort(data, left, last - 1, less_than)
    quicksort(data, last + 1, right, less_than)
}

function quicksort_swap(data, i, j,    temp) {
    temp = data[i]
    data[i] = data[j]
    data[j] = temp
}

{
    lines[counter++] = $0
}

END {
    quicksort(lines, 0, counter - 1)
    for (k = 0; k < counter; k++)
        print lines[k]
}

测试于：

  • Debian 12、达世币 0.5.12、GNU sed 4.9、Gawk 5.2.1
  • Debian 12、Dash 0.5.12、Busybox 1.35.0sed和awk
  • FreeBSD 13.2 的sh、sed和awk

答案4

这是 POSIX sh 中的插入排序：

sort ()
{
    f=false
    for x
    do
        if ! $f
        then
            set -- "$1"
            f=true
        else
            q=false
            # marginally faster than while + "$1" in my tests
            for y
            do
                if $q || "$cmp" "$x" "$y"
                then
                    set -- "$@" "$y"
                else
                    set -- "$@" "$x" "$y"
                    q=true
                fi
                shift
            done
            $q || set -- "$@" "$x"
        fi
    done
    "$cont" "$@"
}

islonger ()
{
    [ ${#1} -gt ${#2} ]
}

puts ()
{
    printf %s\\n "$@"
}

cmp=islonger
cont=puts
sort "$@"

虽然不是效率的顶峰，但在我的机器上 bash 运行速度足够快，足以在非常小的输入上有用：

$ shuf /usr/share/dict/words | head -n 50 | xargs -d '\n' sh -c 'time sh sort.sh "$@"' sh
sic
alto
Biko
needs
Capet
scuba
bowed
sicks
waxier
Kodaly
Tuvalu
hubbub
Gide's
panache
Joann's
peeling
mermaid
wingnut
savvies
crybaby
Python's
nitwit's
junction
tailored
tussocks
rotaries
Brandi's
leafiest
banknote
Spence's
Heriberto
prepaying
telephony
indelible
addendum's
stampeding
hatchway's
pathogenic
Englishman
escarole's
outstaying
synonymous
Youngstown
rebroadcast
overstuffed
interweaves
deliquescent
grandmothers
Cryptozoic's
mammography's

real    0m0.039s
user    0m0.038s
sys     0m0.001s

我相信许多排序算法都可以在 POSIX shell 中相当简单地实现。最大的痛点是不存在交换操作。当然，如果你愿意做序列化之类的事情eval，一切皆有可能。

这是使用相同原理的合并排序：

sort ()
{
    n=1
    while [ $n -lt $# ]
    do
        h=0
        k=$n
        l=$n
        while [ $h -lt $# ]
        do
            i=0
            j=0
            if [ $(($# - h)) -lt $((n << 1)) ]
            then
                if [ $(($# - h)) -le $n ]
                then
                    k=$(($# - h))
                    l=0
                else
                    l=$(($# % n))
                fi
            fi
            for x
            do
                [ $i -eq 0 ] && shift $k
                while [ $j -lt $l ]
                do
                    if [ $i -eq $k ] || "$cmp" "$x" "$1"
                    then
                        set -- "$@" "$1"
                        shift
                        j=$((j + 1))
                    else
                        break
                    fi
                done
                [ $i -eq $k ] && break
                set -- "$@" "$x"
                i=$((i + 1))
            done
            h=$((h + (n << 1)))
        done
        n=$((n << 1))
    done
    "$cont" "$@"
}

$ shuf /usr/share/dict/words | head -n 1000 | xargs -d '\n' sh -c 'time sh sort.sh "$@"' sh >/dev/null
 
real    0m19.918s
user    0m19.917s
sys     0m0.001s

相关内容