bash quicksort

bash quicksort

用bash实现快速排序
参考Quicksort算法实现，如下：

function swap()
{
  declare -r _array_name=$1
  declare -r _i1=$2
  declare -r _i2=$3
  eval declare -r _tmp=\${${_array_name}[$_i1]}
  eval ${_array_name}[$_i1]=\${${_array_name}[$_i2]}
  eval ${_array_name}[$_i2]=\$_tmp
}
function partition()
{
  declare -r _array_name=$1
  declare -r _left=$2
  declare -r _right=$3
  declare -r _pivot_index=${4:-$_left}
  eval declare -r _pivot_value=\${${_array_name}[$_pivot_index]}
  swap $_array_name $_pivot_index $_right
  declare _store_index=$_left
  for ((_i=_left; _i<_right; _i++)); do
    eval declare _v=\${${_array_name}[$_i]}
    if (( _v < _pivot_value )); then
      swap $_array_name $_i $_store_index
      ((_store_index++))
    fi
  done
  swap $_array_name $_right $_store_index
  #echo "store_index=$_store_index"
  return $_store_index
}
function quick_sort()
{  
  declare -r _array_name=$1
  declare -r _left=$2
  declare -r _right=$3
  #declare -r _tmpfile=${TMPDIR:-/tmp}/qs_tmpfile.$$
  #((_right-_left>256)) && { echo "do not support more than 256 elements in array." >&2; return 1; }
  if ((_left<_right)); then
    declare _pivot_index=$_left
    #partition $_array_name $_left $_right $_pivot_index >$_tmpfile
    #declare _pivot_new_index=$(sed -n '/^store_index=/s/.*=//p' $_tmpfile)
    partition $_array_name $_left $_right $_pivot_index
    declare _pivot_new_index=$?
    quick_sort $_array_name $_left $((_pivot_new_index-1))
    quick_sort $_array_name $((_pivot_new_index+1)) $_right
  fi
  #[ -f $_tmpfile ] && /bin/rm -f $_tmpfile
}

稍微简化一下，改成：

function quick_sort2()
{  
  swap()
  {
    eval declare -r _tmp=\${${_array_name}[$1]}
    eval ${_array_name}[$1]=\${${_array_name}[$2]}
    eval ${_array_name}[$2]=\$_tmp
  }
  declare -r _array_name=$1
  declare -r _left=$2
  declare -r _right=$3
  if ((_left<_right)); then
    declare -r _pivot_index=$_left
    #declare -r _pivot_index=$(( ($_right+$_left)/2 ))
    eval declare _pivot_value=\${${_array_name}[$_pivot_index]}
    swap $_pivot_index $_right
    declare _store_index=$_left
    for ((_i=_left; _i<_right; _i++)); do
      eval declare _v=\${${_array_name}[$_i]}
      if (( _v < _pivot_value )); then
        swap $_i $_store_index
        ((_store_index++))
      fi
    done
    swap $_right $_store_index
    quick_sort2 $_array_name $_left $((_store_index-1))
    quick_sort2 $_array_name $((_store_index+1)) $_right
  fi
}

运行结果

# declare -a a=($(for in in {1..50}; do echo $((RANDOM%200-100)); done))
# quick_sort2 a 0 $((${#a[@]}-1))
# echo "${a[@]}"
-99 -97 -96 -94 -90 -82 -77 -76 -72 -70 -66 -66 -66 -63 -59 -53 -51 -50 -50 -48 -46 -45 -38 -34 -33 -30 -22 -21 -21 -20 -18 -10 0 2 2 3 9 24 26 26 44 46 47 47 62 66 80 95 99 99
#

其实网上有个更简单的办法，Tweetable Quicksort by john，一行脚本就可搞定了。

q(){ l=;g=;[ $# -lt 2 ]&&echo $@||(for n in ${@:2};do [ $n -gt $1 ]&&g="$g$n "||l="$l$n ";done;echo `q $l` $1 `q $g`;)}

运行

# q $(for in in {1..50}; do echo $((RANDOM%200-100)); done)
-100 -96 -92 -91 -80 -75 -71 -66 -54 -52 -44 -43 -40 -33 -32 -29 -28 -23 -20 -12 -12 1 16 22 22 27 27 33 33 35 38 39 41 44 45 48 50 55 58 61 62 66 69 72 83 83 85 94 97 98

外部链接：
一个Quicksort究竟可以写到多么短
快速排序（Quicksort）的Javascript实现
数学之美番外篇：快排为什么那样快


又看到一个SLEEP排序，很有趣
Genius sorting algorithm: Sleep sort

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7

-fin-