您现在的位置: 3edu教育网 >> 海量教案 >> 数学教案 >> 高二数学教案 >> 正文    3edu教育网,百万资源,完全免费,无需注册,天天更新!

算法与程序设计——选择排序

算法与程序设计——选择排序

分类:高二数学教案   更新:2013/1/21   来源:网友提供

算法与程序设计——选择排序

in,用它记录最小的一个数据的下标。首先,不管实际情况如何,我们先假设数组中第1个元素为最小,于是有Min=1,再把这个元素与从第2个元素开始的所有元素作比较,一旦有比d(Min)更小的元素存在,则修改Min变量值为新的较小元素下标。这样,在d(Min)经过了从第2个元素到最后一个元素的一一比较后,

    in,用它记录最小的一个数据的下标。
    首先,不管实际情况如何,我们先假设数组中第1个元素为最小,于是有Min=1,再把这个元素与从第2个元素开始的所有元素作比较,一旦有比d(Min)更小的元素存在,则修改Min变量值为新的较小元素下标。这样,在d(Min)经过了从第2个元素到最后一个元素的一一比较后,所得到Min应该就是第1到N个元素中的选举出来的最小元素下标了。
    然后用类似的方法,把第2到N个元素中最小数选举出来;把第3到N个元素中最小数选举出来……
    I←1:Min←1:J←2
    开始
    J<N ?
    d(J)<d(Min) ?
    Min←J
    Y
    Y
    N
    ………………
    J=J+1
    最后把每次选举出来的结果依次输出即可实现升序排列。
    [学生完成第1遍处理过程的流程图片断]
    [依据流程图写出代码]
    Dim Min As Integer
    Dim J As Integer
    Min=1
    For J=2 To N
    If d(J)<d(Min) Then  Min=J
    Next J
    [小组讨论]
    在遍历了一遍后如果发现第1-N个数中的最小数d(Min),根据选择排序的思想,需要把它与第1个数字进行交换。如何进行?
    [请同学发言]打个比方,在厨房里有一瓶酱油、一瓶醋和一个空瓶,如何利用这个空瓶实现酱油与醋?
    ——可先把酱油倒到空瓶中,再把醋倒到原来装酱油的瓶中,然后从原来的空瓶中把酱油倒到原来装醋现在已经空的瓶中,即可实现换位。
    [教师]大家动动脑筋,用这种思想,试试把d(1)与d(Min)换位,并写出相应的代码。
    Dim Temp As Integer
    Temp = d(I):d(I)=d(Min):d(Min)=Temp    ’关键在于引入“空瓶”变量Temp
    [思考]是不是每遍历一遍后必须做这样的一次交换?
    ——不是必须的,只有当确实发现有比d(1)小的数后才交换
    [教师]那怎么知道有没有发现比d(1)更小的数呢?
    I←1:Min←1:J←2
    开始
    J<N ?
    d(J)<d(Min) ?
    Min←J
    Y
    N
    N
    ………………
    Min<>1 ?
    Temp = d(1)
    d(1)=d(Min)
    d(Min)=Temp
    Y
    J=J+1
    ——其实在遍历之前我们已经假设第1个元素最小,即Min=1,所以在遍历一遍后我们只需要验证一下Min=1是否还成立。成立则表明没有比第1个元素小的数,不成立则表明有比第1个元素小的数,且它的下标为Min,此时要交换d(1)与d(Min)。
    [学生完善流程图及代码]
    If Min <> 1 then
    Temp = d(1):d(1)=d(Min):d(Min)=Temp
    End If
    [教师]我们先前说过,对于规模为N的数组,需要遍历处理次数为N-1次,以上的流程就是这N-1次中需要重复做的事,对于重复处理的事,可以用什么结构?
    ——循环,以上的比较、交换即为循环体
    [教师]大家试着把这个循环结构流程图画出来
    [学生完善流程图及代码]
    开始
    J<N ?
    d(J)<d(Min) ?
    Min←J
    Y
    N
    输出排序结果
    N
    Min<>I ?
    Temp = d(I)
    d(I)=d(Min)
    d(Min)=Temp
    Y
    I<=N-1
    I←1
    Y
    N
    结束
    I=I+1
    J=J+1
    Min=I:J=I+1
    For I = 1 To N-1
    Min = I
    For J = I + 1 To N
    If d(J) < d(Min) Then Min = J
    Next J
    If Min <> I Then
    Temp = d(I):d(I) = d(Min):d(Min) = Temp
    End If
    Next I
    For M = 1 To N
    Print(Str(d(M)))
    Next M
    [调试程序]
    [扩展提高]
    我们知道,冒泡排序的效率比较低,主要因为数据交换的次数多,那我们如何知道选择排序中数据交换的次数?
    [学生带着问题思考并实践]
    ——可利用一个自定义Integer型变量,初值0,记录数据交换次数,在程序交换数据部分令其自加1,程序结束时输出结果。
    [完整的程序为]
    Dim I,J,Min,M,Cishu As Integer
    Cishu=0
    For I = 1 To N-1
    Min = I
    For J = I + 1 To N
    If d(J) < d(Min) Then Min = J
    Next J
    If Min <> I Then
    Temp = d(I):d(I) = d(Min):d(Min) = Temp:Cishu=Cishu+1
    End If
    Next I
    For M = 1 To N
    Print(Str(d(M)))
    Next M
    Print(Str(Cishu))
    【问题研讨】
    对于规模非常大时,计算选择排序与冒泡排序交换次数,研究时间、空间复杂度
    利用网络、图书,发现更优秀的排序算法,并对各种算法进行效率分析

| 设为首页 | 加入收藏 | 联系我们 | 版权申明 | 隐私策略 | 关于我们 | 手机3edu | 返回顶部 |