快速排序的非递归实现 --Bash

写blog的好处是，琢磨过的东西不用再琢磨第二次了。

?

快速排序算法的非递归实现：

#!/bin/bashdeclare -a inputArray=(2 3 5 0 1 5 7 1 2 9 0);declare -a startStack;declare -a endStack;#init inputArray randomlyfor((i=0;i<10000;i++))do    inputArray[$i]=$RANDOM;donearrayLength=${#inputArray[@]};lastIndex=$((arrayLength-1));startStack[0]=0;endStack[0]=$lastIndex;stackDeep=1;while [[ $stackDeep -ne 0 ]]do    ## pop stack    topIndex=$((stackDeep-1));    low=${startStack[$topIndex]};    hig=${endStack[$topIndex]};    stackDeep=$((stackDeep-1));    ##partition here    if [[ $low -lt $hig ]]; then        low1=$low;        hig1=$hig;        partition=0;        # select the first element for the base splitor        tmp=${inputArray[$low1]};        while [[ $low1 -ne $hig1 ]]        do            while [[ $low1 -lt $hig1 && ${inputArray[$hig1]} -ge $tmp ]]            do                hig1=$((hig1-1));            done            if [[ $low1 -lt $hig1 ]]; then                inputArray[$low1]=${inputArray[$hig1]};                low1=$((low1+1));            fi            while [[ $low1 -lt $hig1 && ${inputArray[$low1]} -le $tmp ]]            do                low1=$((low1+1))            done            if [[ $low1 -lt $hig1 ]]; then                inputArray[$hig1]=${inputArray[$low1]};                hig1=$((hig1-1));            fi        done        inputArray[$low1]=$tmp;        partition=$low1;        ## push stack        if [[ $low -lt $partition ]]; then            lowp=$((partition-1));            startStack[$stackDeep]=$low;            endStack[$stackDeep]=$lowp;            stackDeep=$((stackDeep+1));        fi        if [[ $hig -gt $partition ]]; then            higp=$((partition+1));            startStack[$stackDeep]=$higp;            endStack[$stackDeep]=$hig;            stackDeep=$((stackDeep+1));        fi    fidone

?

用栈操作模拟递归实现而已。

?

?

给点意见呗 4 楼 liuzhiqiangruc 2012-05-27 效率有点低下，和sort命令比起来没法比啊。