从VB来看-InsertionSort(VB插入排序)

命运对每个人都是一样的,不一样的是各自的努力和付出不同,付出的越多,努力的越多,得到的回报也越多,在你累的时候请看一下身边比你成功却还比你更努力的人,这样,你就会更有动力。

导读:本篇文章讲解 从VB来看-InsertionSort(VB插入排序),希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

插入排序(Insertion Sort)

它是通过不断将未排序数据插入有序序列,一次次循环加入待排序数据扩充有序序列部分,来达到最终的排序目的。很像我们平时发牌时一张张整牌的过程:我的习惯是先把最左边第一张作为有序部分,之后每拿取一张牌进行大小比较,按照升序或降序的方式整理好手里的牌(构建整个有序部分)。 在众多算法的使用对比中,通常在量级小于千的情况下使用插入排序还是令人满意的。


时间复杂度:

若一趟扫描即可完成排序。所需的关键字比较次数 和记录移动次数 均达到最小值时 ,有最好时间复杂度为:O(n)。反之,最坏时间复杂度为;O(n^2)。

排序的稳定性

在插入排序的整个过程中,不断插入待排序数据扩充有序部分,不会改变相同数据的相对位置,所以 是一种 稳定的排序算法。若需要更多讲解举例解释可以看看这个内容 :从VB来看-排序

来看看下面的例子,再次了解一下插入的过程。

1
2
3
视频来自网络-Métodos de Ordenação


从VB来看-插入排序

这是VB-插入排序(互换式)

通过对上图排序过程的了解可以有下面的VB代码。
做了思路的注释,若有什么疑问可以留言。

Sub Insertion(MyArray(), ByVal nOrder As Integer) 
Dim NextElement   '定义将要插入的数据在数组中的位置
Dim Index         '定义将要比较的数据在数组中的位置
Dim TEMP          '定义在执行数据交换时的临时变量

'将数组第一位做为有序部分,那将要插入的数据可以位于数组第二位    
NextElement = LBound(MyArray) + 1    '记录要插入的数据的位置         


  While (NextElement <= UBound(MyArray))    '判断是否还有待插入数据
        Index = NextElement                 '记录将进行比较的数据位置

        Do
            If Index > LBound(MyArray) Then        '判断比较的数据位置是否到数列尽头

                If nOrder = ASCENDING_ORDER Then   '判断是否选择升序排列

                    If MyArray(Index) < MyArray(Index - 1) Then   '判断插入数据是否小于有序部分
                        TEMP = MyArray(Index)                     '数据交换
                        MyArray(Index) = MyArray(Index - 1)
                        MyArray(Index - 1) = TEMP
                        Index = Index - 1                         '移动比较位置
                    Else
                        Exit Do                                   '退出循环-完成一次插入数据                  
                    End If


                ElseIf nOrder = DESCENDING_ORDER Then              '判断是否选择降序排列

                    If MyArray(Index) >= MyArray(Index - 1) Then   '判断插入数据是否小于有序部分
                        TEMP = MyArray(Index)                      '数据交换
                        MyArray(Index) = MyArray(Index - 1)
                        MyArray(Index - 1) = TEMP
                        Index = Index - 1                          '移动比较位置
                    Else
                        Exit Do

                    End If
                End If
            Else
                Exit Do                                            '退出循环-完成一次插入数据                  
            End If
            gIterations = gIterations + 1                          '记录循环次数

        Loop
        NextElement = NextElement + 1                              '移动到下一位插入数据
        gIterations = gIterations + 1                              '记录循环次数

    Wend

有了上图生动的过程,再来看一个例子,想想有什么不同

插入排序
图片来自维基百科

这是VB-插入排序(平移式)

通过对上图排序过程的参考可以有下面的VB代码。

Sub Insertion(MyArray(), ByVal nOrder As Integer)
Dim NextElement   '定义将要插入的数据在数组中的位置
Dim Index         '定义将要比较的数据在数组中的位置
Dim TEMP          '定义在执行数据交换时的临时变量

'将数组第一位做为有序部分,那将要插入的数据可以位于数组第二位    
NextElement = LBound(MyArray) + 1           '记录要插入的数据的位置 


    While NextElement <= UBound(MyArray)    '判断是否还有待插入数据

       TEMP = MyArray(NextElement)          '刷新要插入的数据的位置
       Index = NextElement - 1              '记录将进行比较的数据位置

       Do
          If Index >=LBound(MyArray) Then             '判断比较的数据位置是否到数列尽头

             If nOrder = ASCENDING_ORDER Then         '判断是否选择升序排列

                If TEMP < MyArray(Index) Then         '判断插入数据是否小于有序部分
                MyArray(Index + 1) = MyArray(Index)   '有序部分为插入数据移出空位
                Index = Index - 1   '移动到更小的有序数据位置
                Else: Exit Do       '退出循环-(已找到插入数据位置合理位置)
                End If

             ElseIf nOrder = DESCENDING_ORDER Then    '判断是否选择降序排列

                If TEMP > MyArray(Index) Then         '判断插入数据是否大于有序部分
                MyArray(Index + 1) = MyArray(Index)   '有序部分为插入数据移出空位
                Index = Index - 1   '移动到更大的有序数据位置
                Else: Exit Do       '退出循环-(已找到插入数据位置合理位置)
                End If

             End If

          Else: Exit Do             '退出循环-(已找到插入数据位置合理位置)      
          End If

       Loop

       MyArray(Index + 1) = TEMP       '插入数据
       NextElement = NextElement + 1   '移动到下一位待插入数据位置
       gIterations = gIterations + 1   '记录循环次数

    Wend

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/144350.html

(0)

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!