冒泡排序——PowerShell版

  1. 云栖社区>
  2. 博客>
  3. 正文

冒泡排序——PowerShell版

天外归云 2015-10-02 14:57:00 浏览889
展开阅读全文

继续读啊哈磊算法有感系列。上一篇是桶排序,在结尾总结了一下简化版桶排序的缺点。这一篇来说一下冒泡排序,冒泡排序可以很好的克服桶排序的缺点。下面我们先来说说冒泡排序的过程与思想——

冒泡排序的过程:

一轮排序:如果有5个数从大到小排序,第一位数与第二位数进行比较,如果第一位小,则第一位数和第二位数交换位置。之后按照这个逻辑对第二位数与第三位数,第三位数与第四位数,第四位数与第五位数分别进行比较与交换。一共会进行4次比较交换次数小于等于4。这样一轮比较下来,最小的数就排在了最后面;

二轮排序:由于最小的数已经排在了最后面,所以第二轮排序只需要考虑前四位数。对前四位数按照第一轮排序的方法进行排序,将最小的数排到最后,也就是5个数中的倒数第二位;

三轮排序:排前三位

四轮排序:排前两位

冒泡排序的思想(思想就是对过程的抽象与总结):

先进行抽象:我们对上面的冒泡排序过程进行抽象,如果有n个数第一轮会有n-1次比较(交换次数小于等于n-1),之后每轮的比较次数逐次减1,一共进行n-1轮排序。

再进行总结:冒泡排序就是每轮比较选出一个最小的数放在最后,进行n-1轮比较,将n个数按从大到小进行排列。(也可以是从小到大,这里按从大到小排序进行举例)

现在将我们的总结转换为代码的形式(由于PowerShell中貌似没有C语言中的结构体,我就用两个数组studentName和studentScore来替代了),其中粉色字体为排序部分的关键代码:

$count = Read-Host "Enter the amout number of the students"
$studentName = New-Object System.Collections.ArrayList
$studentScore = New-Object System.Collections.ArrayList
for($i=1;$i -le [int]$count;$i++)
{
    $name = Read-Host "Enter the name"
    $score= Read-Host "Enter the score"
    $studentName.Add($name)
    $studentScore.Add($score)
}
#Sort begin.
for($i=1;$i -le $count-1;$i++)
{
    for($j=1;$j -le $count-$i;$j++)
    {
        #Compare the students' values.
        if([int]$studentScore[$j-1] -le [int]$studentScore[$j])
        {
            #Exchange the score.
            $s = $studentScore[$j-1] 
            $studentScore[$j-1] = $studentScore[$j]
            $studentScore[$j] = $s
            #Exchange the name.
            $n = $studentName[$j-1] 
            $studentName[$j-1] = $studentName[$j]
            $studentName[$j] = $n
        }
    }
    $i++
}
#Print the sorted result.
Write-Host "Below is the sorted result:"
for($i=0;$i -le $count-1;$i++)
{
    $j=$i+1
    $tip = "NO."+$j+":"+$studentName[$i]+",score:"+$studentScore[$i]
    Write-Host $tip -ForegroundColor Green
}

对于粉色字体:

1、外for循环代表进行$count-1轮排序;

2、内for循环代表从第一轮排序开始,第“$i”轮排序将进行$count-$i次比较。

运行界面如下——

输入学生数:

输入学生姓名:

输入学生分数:

排序结果为:

由于冒泡排序的核心是内外双层嵌套循环,时间复杂度为O(N*N),这是一个非常高的时间复杂度。

网友评论

登录后评论
0/500
评论
天外归云
+ 关注