插入排序（Insertion Sort）

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

时间复杂度：

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

排序的稳定性

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

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

视频来自网络-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

从VB来看-InsertionSort（VB插入排序）