快速排序之Powershell代码,Shell代码库,德仔网

代码语言
代码分类
【Shell】快速排序之Powershell
作者:DDT / 发布于2013/2/17/ 1284
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] $left, [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
试试其它关键字
　快速排序　
同语言下
可能有用的
DDT贡献的其它代码(160)