shell脚本实现快速排序算法

Author Avatar
LittleYou Don't Know 12月 12, 2016

近段需要在shell中实现自定义排序，联想数据结构课程，哈哈，没多想，遂决定使用快速排序算法。然而百度之，发现很多相同的版本，而且呵呵哒，完全不理解为什么写的那么恶心啊。
自己对照C语言版本的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# cat quick_sort.sh 
#!/bin/bash
a=(132 2 239 27 92 -12 23)
quick_sort()
{
    if [ $1 -ge $2 ]; then
         return
    fi
    
    i=$1
    j=$2
    key=${a[$1]}
    
    while [  $i -lt  $j ]
    do
        while [  $i -lt  $j ] && [  $key -le  ${a[$j]} ]
        do
            j=$(($j-1))
        done
        mid=${a[$i]}
        a[$i]=${a[$j]}
        a[$j]=$mid
        while [  $i -lt  $j ] && [  $key -ge  ${a[$i]} ]
        do
            i=$(($i+1))
        done
        mid=${a[$j]}
        a[$j]=${a[$i]}
        a[$i]=$mid
    done
    arr[$si]=$key
    quick_sort $1 $(($i-1))
    quick_sort $(($i+1)) $(($2))
}
len=$((${#a[@]}-1))
quick_sort 0 $len 
for ((i=0;i<=$len;i++))
do
     echo -n ${a[$i]} " "
done
echo

测试结果：

1
2
#./quick_sort.sh 
-12  2  23  27  92  132  239

expand_less