Perl 快排

看了下算法导论中的快排，实现方法不太一样，重新练习一下。

如图为比较过程中的移动：

代码：

# 递归
sub qsort2 {
    return () unless @_;
    (
        qsort( grep        { $_ < $_[0] } @_[ 1 .. $#_ ] ),$_[0],qsort( grep { $_ >= $_[0] } @_[ 1 .. $#_ ] )
    );
}

# 非递归
sub qsort {
    if ( !@_ ) {
        return ();
    }
    else {

        # 以$_[0] 作为基准比较，前后两个方向逼近，不象算法导论中单向向右逼近
        my $low  = 1;
        my $high = $#_;
        while ( $high >= $low ) {
            while ( $low <= $high && $_[$low] < $_[0] ) {
                $low++;
            }
            while ( $high >= $low && $_[$high] >= $_[0] ) {
                $high--;
            }
            print "@_ => $low $highn";
            if ( $low < $high ) {
                ( $_[$low],$_[$high] ) = ( $_[$high],$_[$low] );
            }
            print "@_ n";
        }

        # 与基准位的判断，不同则互换
        if ( $high != 0 ) { ( $_[0],$_[0] ) }
        print "----------n@_n---------- n";
        qsort( @_[ 0 .. ( $high - 1 ) ] );
        qsort( @_[ ( $high + 1 ) .. $#_ ] );
    }
}

@a = map { int rand 100 } 1 .. 10;
print "@an";
qsort(@a);
print "@an";