（快速）对 POSIX sh 中的文件列表进行排序

Question

很多时候，我发现自己认为拥有一个尽可能可移植的通用解决方案会很好，“如果我在奇怪或受限的机器上需要它”。

我一直在寻找一种方法来或多或少地以相反的顺序对目录中的文件列表进行排序，仅使用 POSIX sh 和工具。

这应该适用于任意命名的文件，包括名称中带有控制代码字符（例如，换行符）的文件。

Answer 1

据我所知，此代码完全 POSIX 兼容。唯一不 POSIX 兼容的部分是使用 pwgen 生成测试数据。我不想在这方面做得太过分，因为我不认为它是实际代码的一部分——它只是为了方便……测试它。

好的部分：

它正在使用数组！（实际上，它确实以一种兼容的方式模拟了数组。）
迭代，几乎具有随机主元选择的就地快速排序算法。这真是greybeard's answer的改编版。 “almost”部分来自使用堆栈模拟来跟踪间隔，如果我没记错的话，它平均使用大约 O(log(n)) 额外的 space .
文件名可以包含任何字符（但是 NUL，这是 POSIX shell 中的一个常见问题，而且文件系统通常不允许这样做）。
比较函数 comp_lex_rev 可以很容易地换成不同的 one/modified 到其他行为，例如，如果您需要按顺序对数字进行排序 - 即，它是模块化的。

丑陋的部分：

rand() 的随机数生成，但其他任何事情都很难移植。我的初始代码用于读取 /dev/urandom 并解析该数据，但当然，这不是 POSIX.
奇怪的函数前缀变量名。这是 POSIX sh 不支持局部变量的直接后果。可以（在某种程度上）通过保存旧值、使用您认为合适的变量并最终恢复原始值来模拟它们，但这确实会使代码更加不可读（并且容易出错，因为您要么需要一个函数中的固定退出点或在每个可能的退出点复制恢复功能）。使用唯一（啊哈）字符串为变量添加前缀可以解决此问题，以可读性换取范围能力。
需要直接访问全局输入伪数组。在 subshell 中调用函数而不处理结果只会浪费 CPU 时间，因为父进程中的原始数据不会被更改。这是 shell 脚本中的一个普遍问题，但可能值得一提。
整数很棘手。最初，我明确地将随机数获取部分限制为 2^16 - 1，因为这是保证的最小整数大小——这可能意味着 shell 也必须至少支持它。但是，在那里强制执行限制没有意义。相反，我在生成输入数组时选择了某种溢出检测。请记住，shell 中可用的最大整数大小是特定于实现的，具有硬性下限。
基于shell，与直接二进制实现相比，它相当慢，例如，C。 expr 因速度慢而臭名昭着，并且分叉到其他程序使得 shell 脚本更慢。作为一个轶事，通过使用 zsh 内部正则表达式处理替换 grep 和 sed 调用，我能够大大减少 zsh 脚本中的处理时间。同样，这一点是 shell 脚本编写的一个普遍问题，与我的代码无关，但牢记这一点也很好。

#!/bin/sh

#set -x

comp_lex_rev () {
  comp_lex_rev_a="${1:?'No lhs passed to comp_lex_rev(), this is invalid.'}"
  comp_lex_rev_b="${2:?'No rhs passed to comp_lex_rev(), this is invalid.'}"

  comp_lex_rev_expr_out="$('expr' "x${comp_lex_rev_a}" '>' "x${comp_lex_rev_b}")"
  if [ '1' -eq "${comp_lex_rev_expr_out}" ]; then
    return '0'
  else
    return '1'
  fi
}

get_rand () {
  get_rand_min="${1:?'No minimum value passed to get_rand(), this is invalid.'}"
  get_rand_max="${2:?'No maximum value passed to get_rand(), this is invalid.'}"

  # Minimum value must be positive.
  if [ '0' -gt "${get_rand_min}" ]; then
    return '1'
  fi

  # Max > min doesn't make sense... (we could just swap them here, but meh.)
  if [ "${get_rand_min}" -gt "${get_rand_max}" ]; then
    return '1'
  fi

  # Not much to do if both are the same value.
  if [ "${get_rand_min}" -eq "${get_rand_max}" ]; then
    'printf' '%s\n' "${get_rand_min}"
    return '0'
  fi

  # Just be extra careful.
  get_rand_out=''
  while [ -z "${get_rand_out}" ] || [ "${get_rand_min}" -gt "${get_rand_out}" ] || [ "${get_rand_max}" -lt "${get_rand_out}" ]; do
    get_rand_out="$('awk' '
      BEGIN {
        srand ();
        printf ("%u", (rand () * (('"${get_rand_max}"' - '"${get_rand_min}"') + 1)) + '"${get_rand_min}"');
      }')"
  done

  'printf' '%s\n' "${get_rand_out}"
}

qsort () {
  qsort_arr="${1:?'No array base passed to qsort(), this is invalid.'}"
  qsort_n="${2:?'No array length passed to qsort(), this is invalid.'}"

  if [ '2' -gt "${qsort_n}" ]; then
    # One or zero elements are always sorted.
    return '0'
  fi

  qsort_range_0='0'
  qsort_range_1="$((${qsort_n} - 1))"
  qsort_range_n='2'
  # Must have at least one pair entry in the range "stack".
  while [ '1' -lt "${qsort_range_n}" ]; do
    qsort_range_n="$((${qsort_range_n} - 1))"
    eval 'qsort_high="${qsort_range_'"${qsort_range_n}"'}"'
    qsort_range_n="$((${qsort_range_n} - 1))"
    eval 'qsort_low="${qsort_range_'"${qsort_range_n}"'}"'

    qsort_cur_i="${qsort_low}"
    qsort_pivot_i="$('get_rand' "${qsort_low}" "${qsort_high}")"
    if [ '0' -ne "${?}" ]; then
      # Fetching random value failed, fall back to rightmost element.
      qsort_pivot_i="${qsort_high}"
    fi

    eval 'qsort_pivot="${'"${qsort_arr}"'_'"${qsort_pivot_i}"'}"'

    # Move pivot up if it isn't already.
    if [ "${qsort_high}" != "${qsort_pivot_i}" ]; then
      eval "${qsort_arr}"'_'"${qsort_pivot_i}"'="${'"${qsort_arr}"'_'"${qsort_high}"'}"'
      eval "${qsort_arr}"'_'"${qsort_high}"'="${qsort_pivot}"'
      qsort_pivot_i="${qsort_high}"
    fi

    eval 'qsort_cur="${'"${qsort_arr}"'_'"${qsort_cur_i}"'}"'
    while [ "${qsort_pivot_i}" -gt "${qsort_cur_i}" ]; do
      if 'comp_lex_rev' "${qsort_cur}" "${qsort_pivot}"; then
        qsort_cur_i="$((${qsort_cur_i} + 1))"
        eval 'qsort_cur="${'"${qsort_arr}"'_'"${qsort_cur_i}"'}"'
      else
        eval "${qsort_arr}"'_'"${qsort_pivot_i}"'="${qsort_cur}"'
        qsort_pivot_i="$((${qsort_pivot_i} - 1))"
        eval "${qsort_arr}"'_'"${qsort_cur_i}"'="${'"${qsort_arr}"'_'"${qsort_pivot_i}"'}"'
        eval 'qsort_cur="${'"${qsort_arr}"'_'"${qsort_pivot_i}"'}"'
      fi
    done
    eval "${qsort_arr}"'_'"${qsort_pivot_i}"'="${qsort_pivot}"'

    qsort_lhs_size="$((${qsort_pivot_i} - ${qsort_low}))"
    qsort_rhs_size="$((${qsort_high} - ${qsort_pivot_i}))"
    if [ "${qsort_lhs_size}" -le "${qsort_rhs_size}" ]; then
      if [ '1' -lt "${qsort_lhs_size}" ]; then
        eval 'qsort_range_'"${qsort_range_n}"'="$((${qsort_pivot_i} + 1))"'
        qsort_range_n="$((${qsort_range_n} + 1))"
        eval 'qsort_range_'"${qsort_range_n}"'="${qsort_high}"'
        qsort_range_n="$((${qsort_range_n} + 1))"

        eval 'qsort_range_'"${qsort_range_n}"'="${qsort_low}"'
        qsort_range_n="$((${qsort_range_n} + 1))"
        eval 'qsort_range_'"${qsort_range_n}"'="$((${qsort_pivot_i} - 1))"'
        qsort_range_n="$((${qsort_range_n} + 1))"
      fi
    else
      eval 'qsort_range_'"${qsort_range_n}"'="${qsort_low}"'
      qsort_range_n="$((${qsort_range_n} + 1))"
      eval 'qsort_range_'"${qsort_range_n}"'="$((${qsort_pivot_i} - 1))"'
      qsort_range_n="$((${qsort_range_n} + 1))"
    fi

    if [ '1' -lt "${qsort_rhs_size}" ]; then
      eval 'qsort_range_'"${qsort_range_n}"'="$((${qsort_pivot_i} + 1))"'
      qsort_range_n="$((${qsort_range_n} + 1))"
      eval 'qsort_range_'"${qsort_range_n}"'="${qsort_high}"'
      qsort_range_n="$((${qsort_range_n} + 1))"
    fi
  done
}

print_arr () {
  print_arr_arr="${1:?'No array base passed to print_arr(), this is invalid.'}"
  print_arr_n="${2:?'No array length passed to print_arr(), this is invalid.'}"

  print_arr_i='0'
  while [ "${print_arr_n}" -gt "${print_arr_i}" ]; do
    if [ '0' -ne "${print_arr_i}" ]; then
      'printf' '===\n'
    fi
    eval "'"'printf'"'"' '"'"'%s\n'"'"' "${'"${print_arr_arr}"'_'"${print_arr_i}"'}"'
    print_arr_i="$((${print_arr_i} + 1))"
  done
}

generate_testdata () {
  generate_testdata_dir="${1:?'No testdata directory passed to generate_testdata(), this is invalid.'}"

  generate_testdata_i='0'
  generate_testdata_n='100'
  (
    'mkdir' "${generate_testdata_dir}"
    'cd' "${generate_testdata_dir}"
    while [ "${generate_testdata_n}" -gt "${generate_testdata_i}" ]; do
      # We'll map the first underscore character to a space character and
      # ditto for right curly bracket vs. newline since pwgen generates no
      # such characters by default.
      ':' > "$('pwgen' '-s' '-y' '-c' '-n' '-r' '/' '100' '1' | 'sed' '-e' 's#_# #' '-e' 's#}#\
#')"
      generate_testdata_i="$((${generate_testdata_i} + 1))"
    done
  )
}

main () {
  main_testdir='testdata'
  if [ ! -d "${main_testdir}" ]; then
    'generate_testdata' "${main_testdir}"
  fi

  main_cur_file=''
  main_flist_n='0'
  main_flist_old_n="${main_flist_n}"
  for main_cur_file in "${main_testdir}"/*; do
    if [ -f "${main_cur_file}" ]; then
      eval 'main_flist_'"${main_flist_n}"'="${main_cur_file}"'
      main_flist_n="$((${main_flist_n} + 1))"

      if [ "${main_flist_old_n}" -ge "${main_flist_n}" ]; then
        # Overflow (or... none-flow?), stop working.
        'printf' 'Too many files to handle, aborting.\n' >&'2'
        return '1'
      else
        main_flist_old_n="${main_flist_n}"
      fi
    fi
  done

  # Sort, in reverse order.
  'qsort' 'main_flist' "${main_flist_n}"

  # And finally print out.
  'print_arr' 'main_flist' "${main_flist_n}"

  # In GNU terms,
  # 'find' "${main_testdir}" '-type' 'f' '-print0' | 'sort' '-rz' | 'sed' '-e' 's#\x0#\n===\n#g'
  # should return about the same data, only with an additional separator at the end.
}

# Actual main code.
'main'

Answer 2

所以这个想法是按照字典倒序处理一组文件。如您所知，由于奇怪的文件名，您无法解析 ls。由于这是 POSIX，我们没有数组。所以这是一个可能有效的解决方案。

Glob 表达式return 按字典顺序排列的可能文件名列表。所以你可以做类似

的事情

for file in /path/to/dir/*; do
    [ -e "${file}" ] || continue
    some_command "${file}"
done

如果你想反转它，你可以这样做：

set -- /path/to/dir/*
i=$#
while [ "$i" -gt 0 ]; do 
    eval "file=${${i}}"; i=$((i-1));
    [ -e "${file}" ] || continue
    some_command "$file"
done

注意：我们必须使用evil eval来计算位置变量。

更新：位置变量可能已被使用。在这种情况下，您可以执行以下操作：

j=$#
set -- /path/to/dir/* "$@"
i=$(($#-$j))
while [ "$i" -gt 0 ]; do 
    eval "file=${${i}}"; i=$((i-1));
    [ -e "${file}" ] || continue
    some_command "$file"
done
shift "$i"

（快速）对 POSIX sh 中的文件列表进行排序

(Quick-) sorting a list of files in POSIX sh

sorting

posix

sh

quicksort