bash归并排序
#!/bin/bash rest() { shift; echo $@; } length() { echo $#; } first() { echo $1; } merge() { declare left=$1 right=$2 result= declare length_left=$(length $left) declare length_right=$(length $right) while (( length_left>0 || length_right>0 )); do if (( length_left>0 && length_right>0 )); then if [ $(first $left) -le $(first $right) ]; then result="$result $(first $left)" left=$(rest $left) else result="$result $(first $right)" right=$(rest $right) fi elif [ $(length $left) -gt 0 ]; then result="$result $(first $left)" left=$(rest $left) elif [ $(length $right) -gt 0 ]; then result="$result $(first $right)" right=$(rest $right) fi length_left=$(length $left) length_right=$(length $right) done echo $result } merge_sort() { [ $# -le 1 ] && { echo $@; return; } declare -i middle=$(($#/2+1)) declare left= right= result= for ((i=1;i<middle;i++)); do left="$left ${!i}" done for ((i=middle;i<=$#;i++)); do right="$right ${!i}" done left=$(merge_sort $left) right=$(merge_sort $right) result=$(merge "$left" "$right") echo $result } merge_sort $@
执行:
# ./merge_sort.sh $(for in in {1..50}; do echo $((RANDOM%200-100)); done) -99 -89 -88 -84 -83 -83 -81 -76 -75 -70 -70 -70 -54 -53 -51 -51 -49 -49 -40 -40 -30 -27 -24 -19 -15 -13 -12 -12 -8 -2 -2 -2 2 4 10 17 20 24 28 34 39 39 40 42 45 48 48 49 62 83
算法参考:Merge sort
-fin-
No comments:
Post a Comment