sortalogrithm.vb

说明: 这一段在复习数据结构和算法

Public Class SortAlogrithm

    Protected Overridable Sub Exch(ByRef A As Integer, ByRef B As Integer, ByVal i As Integer, ByVal j As Integer)
        Dim T As Integer
        T = A
        A = B
        B = T
    End Sub

    Protected Overridable Function Compare(ByRef A As Integer, ByRef B As Integer, ByVal i As Integer, ByVal j As Integer) As Boolean
        If A < B Then
            Return True
        Else
            Return False
        End If
    End Function

    Protected Overridable Sub Evalvalue(ByRef ToData As Integer, ByRef FromDate As Integer, ByVal i As Integer, ByVal j As Integer)
        ToData = FromDate
    End Sub

    Public Sub InsertSort(ByRef Item() As Integer, ByVal l As Integer, ByVal r As Integer)
        Dim i, j As Integer
        Dim t As Integer
        For i = r To l + 1 Step -1
            If Compare(Item(i), Item(i - 1), i, j) Then
                Exch(Item(i), Item(i - 1), i, j)
            End If
        Next
        For i = l + 2 To r Step 1
            t = Item(i)
            j = i
            While Compare(t, Item(j - 1), i, j)
                Evalvalue(Item(j), Item(j - 1), i, j)
                j -= 1
            End While
            Evalvalue(Item(j), t, i, j)
        Next
    End Sub

    Public Sub SelectSort(ByRef Item() As Integer, ByVal l As Integer, ByVal r As Integer)
        Dim i, j As Integer
        Dim min As Integer
        For i = l To r Step 1
            min = i
            For j = i To r Step 1
                If Compare(Item(j), Item(min), i, j) Then
                    min = j
                End If
            Next
            Exch(Item(i), Item(min), i, j)
        Next
    End Sub

    Public Sub BubbleSort(ByRef Item() As Integer, ByVal l As Integer, ByVal r As Integer)
        Dim i, j As Integer
        For i = l + 1 To r Step 1
            For j = r To i Step -1
                If Compare(Item(j), Item(j - 1), i, j) Then
                    Exch(Item(j), Item(j - 1), i, j)
                End If
            Next
        Next
    End Sub

    Public Sub QuickSort(ByRef Item() As Integer, ByVal l As Integer, ByVal r As Integer)
        If r <= l Then
            Exit Sub
        End If
        Dim i As Long
        i = Partition(Item, l, r)
        QuickSort(Item, l, i - 1)
        QuickSort(Item, i + 1, r)
    End Sub

    Private Function Partition(ByRef Item() As Integer, ByVal l As Long, ByVal r As Long) As Integer
        Dim i, j As Integer
        Dim v As Integer
        i = l - 1
        j = r
        v = Item(r)
        While True
            Do
                i = i + 1
            Loop While Compare(Item(i), v, i, j)
            Do
                j = j - 1
                If j = l Then Exit Do
            Loop While Compare(v, Item(j), i, j)
            If i >= j Then Exit While
            Exch(Item(i), Item(j), i, j)
        End While
        Exch(Item(i), Item(r), i, j)
        Return i
    End Function

End Class