form1.frm

此程序主要用于选择问题的分治算法！！！！！！！欢迎下载

VERSION 5.00
Begin VB.Form Form1 
   Caption         =   "Form1"
   ClientHeight    =   3615
   ClientLeft      =   60
   ClientTop       =   450
   ClientWidth     =   5055
   LinkTopic       =   "Form1"
   ScaleHeight     =   3615
   ScaleWidth      =   5055
   StartUpPosition =   3  '窗口缺省
   Begin VB.TextBox Text3 
      Height          =   375
      Left            =   1800
      TabIndex        =   4
      Top             =   360
      Width           =   615
   End
   Begin VB.CommandButton Command2 
      Caption         =   "寻找第k小元素"
      Height          =   495
      Left            =   240
      TabIndex        =   2
      Top             =   2880
      Width           =   4575
   End
   Begin VB.TextBox Text1 
      Height          =   1575
      Left            =   240
      MultiLine       =   -1  'True
      TabIndex        =   1
      Top             =   1080
      Width           =   4575
   End
   Begin VB.CommandButton Command1 
      Caption         =   "输入数据"
      Height          =   375
      Left            =   2880
      TabIndex        =   0
      Top             =   360
      Width           =   1935
   End
   Begin VB.Label Label2 
      Caption         =   "请输入元素个数："
      Height          =   375
      Left            =   120
      TabIndex        =   3
      Top             =   360
      Width           =   1455
   End
End
Attribute VB_Name = "Form1"
Attribute VB_GlobalNameSpace = False
Attribute VB_Creatable = False
Attribute VB_PredeclaredId = True
Attribute VB_Exposed = False
Dim n As Integer, k As Integer 'n为数组元素个数，k为要查找的第k小的元素
Dim aryNum() As Integer '将要查找的数组

Function minK(aryNum() As Integer, low As Integer, high As Integer, ByVal k As Integer) '寻找第k小的元素
    Dim j As Integer
    If low = high Then
        minK = aryNum(low)
       Exit Function
    End If
    
    Pivot = Partition(aryNum(), low, high) '获得轴值的位置
    j = Pivot - low + 1
    If k = j Then
        minK = aryNum(Pivot)
        Exit Function
    End If
    
    '用分治策略递归地寻找第 k 小元素
    If k < j Then
        minK = minK(aryNum(), low, Pivot - 1, k)
        
    Else
        minK = minK(aryNum(), Pivot + 1, high, k - j)
    Exit Function
    End If
    
End Function
'寻找轴值
Function Partition(aryNum() As Integer, first As Integer, ende As Integer)
    Dim i, j As Integer
    i = first
    j = ende
    Do While i < j
        Do While i < j And aryNum(i) <= aryNum(j) '扫描右侧
            j = j - 1
        Loop
        If i < j Then
            Call Swap(aryNum(i), aryNum(j)) '将较小值 交换到前面
            i = i + 1
        End If
        Do While i < j And aryNum(i) <= aryNum(j) '扫描左侧
            i = i + 1
        Loop
        If i < j Then
            Call Swap(aryNum(i), aryNum(j)) '将较大值 交换到后面
            j = j - 1
        End If
    Loop
    Partition = i
End Function
Sub Swap(n1 As Integer, n2 As Integer) '交换两个数
    Dim temp As Integer
    temp = n1
    n1 = n2
    n2 = temp
End Sub


Private Sub Command1_Click()
Dim i As Integer
If Text3 = "" Then '排错：n不得为空
    MsgBox ("请输入元素个数")
    Exit Sub
Else
    n = Text3 '输入数族元素的个数
End If
Text1 = "共有" & n & "个数" & vbCrLf
ReDim aryNum(0 To n - 1)
For i = 0 To n - 1 '输入数组
    aryNum(i) = InputBox("第" & i + 1 & "个数为：")
    Text1 = Text1 & aryNum(i) & "; "
Next i
End Sub

Private Sub Command2_Click()
k = InputBox("k=")
If k > n Or k <= 0 Then '排错：k不得大于n,且不能小于1
    MsgBox ("k最大值为" & n & "最小值为1" & ",请重新输入")
    k = InputBox("k=")
End If
t = minK(aryNum(), LBound(aryNum), UBound(aryNum), k) '调用minK函数求第k小的元素
Text1 = Text1 & vbCrLf & "第" & k & "小的元素为" & t
End Sub