快速排序之Powershell

以下代码由PHP站长网 52php.cn收集自互联网

现在PHP站长网小编把它分享给大家，仅供参考

param ( $theArray = @() ) 
 
$global:counter = 0 
 
# Swaps the array values at indexes $x and $y 
function swap ($theArray,$x,$y) 
{ 
    $temp = $theArray[$x] 
    $theArray[$x] = $theArray[$y] 
    $theArray[$y] = $temp 
} 
 
# Uses insertion sort algorithm to sort a subarray 
# $theArray is an array of comparable objects 
# $left is the left-most index of the subarray 
# $right is the right-most index of the subarray 
function insertionsort ($theArray,$left,$right) 
{ 
    for ($i = $left; $i -le $right; $i++) 
    { 
        $temp = $theArray[$i] 
        for ($j = $i; $j -gt 0 -and $temp -lt $theArray[$j - 1]; $j--) 
        { 
            $theArray[$j] = $theArray[$j - 1] 
        } 
        $theArray[$j] = $temp 
    } 
} 
 
# Returns the median of left,center,and right 
function median ($theArray,[int] $left,[int] $right) 
{ 
    [int] $center = [Math]::Floor(($left + $right) / 2) 
    if ($theArray[$center].CompareTo($theArray[$left]) -lt 0) 
    { 
        swap $theArray $left $center 
    } 
    if ($theArray[$right].CompareTo($theArray[$left]) -lt 0) 
    { 
        swap $theArray $left $right 
    } 
    if ($theArray[$right].CompareTo($theArray[$center]) -lt 0) 
    { 
        swap $theArray $center $right 
    } 
     
    # Place pivot at position $right - 1 
    swap $theArray $center ($right - 1) 
    return $theArray[$right - 1] 
} 
 
# Makes recursive calls 
# Uses median-of-three partitioning and a cutoff of 10 
# $theArray is an array of comparable objects 
# $left is the left-most index of the subarray 
# $right is the right-most index of the subarray 
function quicksorter ($theArray,[int] $right) 
{ 
    if ($left + 10 -le $right) 
    { 
        $pivot = median $theArray $left $right 
         
        # Begin partitioning 
        $i = $left 
        $j = $right - 1 
        for ( ; ; ) 
        { 
            $global:counter++ 
            while ($theArray[++$i] -lt $pivot) {} 
            while ($pivot -lt $theArray[--$j]) {} 
            if ($i -lt $j) 
            { 
                swap $theArray $i $j 
            } 
            else 
            { 
                break 
            } 
        } 
         
        # Restore pivot 
        swap $theArray $i ($right - 1) 
         
        # Sort small elements 
        quicksorter $theArray $left ($i - 1) 
         
        # Sort large elements 
        quicksorter $theArray ($i + 1) $right 
    } 
    else 
    { 
        # Use insertion sort to sort the subarray 
        insertionsort $theArray $left $right 
    } 
} 
 
quicksorter $theArray 0 ($theArray.Count - 1) 
 
Write-Host "Array items: `t" $theArray.Count 
Write-Host "Iterations: `t" $global:counter

以上内容由PHP站长网【52php.cn】收集整理供大家参考研究

如果以上内容对您有帮助，欢迎收藏、点赞、推荐、分享。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!