topirol 发表于 2004-1-8 17:10:00

关于快速找出最小3个数的算法问题

本帖最后由 作者 于 2004-1-8 18:49:21 编辑

数组a(n)   (n>5000)
用什么办法快速找出最小3个值的数组下标 i1,i2,i3？(不改变数组a(n)的结构)

mccad 发表于 2004-1-8 17:38:00

不用排序就简单点，用逐个比较法，先将前三个数保存下来，记录位置，排序，如a1,a2,a3，其中a3为最小，然后后继的数就与这a3比较，如果比A3小，则替换A3，原A3替换A2，原A2替换A1。如果后继的数比A3大，比A2小，则替换A2，原A2替换A1。如果后继的数比A1小比A2大，则替换A1。
这样就行了。

topirol 发表于 2004-1-8 18:26:00

三个值好找，但三个值对应的下标不太好找，可以给一段代码吗

myfreemind 发表于 2004-1-8 18:27:00

用排序法比较好！
for i=1 to 4999
for j=i+1 to 5000
If x(i) > x(j) Then t = x(i): x(i) = x(j): x(j) = t
Next
Next
For i = 1 To 3
debug.Print x(i)
Next

topirol 发表于 2004-1-8 18:46:00

4楼的代码，好像只能找到值，而不能找到对应数组的下标，因为目的是找到最小三个值的下标，而且前提是我不能改变原来数组的值

whyer 发表于 2004-1-8 19:13:00

这类问题，属于数据结构方面的问题，只要看一看，数据结构方面关于排序查找这部分，折半，冒泡等算法只要根据你的题目的需要，都有一个满意的算法。我觉得这道题采用起泡法排序最好。

whyer 发表于 2004-1-8 19:19:00

先自定义一个数据类型。
如：
    type s
    index as interger
    num as integer
    end type
然后dim a(n) as s,根据a(i).num进行排序,只要找到最小的三个数,然后再就能找到它们的index,这样下标就能找到了.
不过这样比较费内存.

whyer 发表于 2004-1-8 19:21:00

其中的index为该数的下标,在程序运行中是不变的,num为该数的值

efan2000 发表于 2004-1-8 19:35:00

这个不知道是否满足。


Option Explicit

' 第2维：0索引，1值
Dim b(0 To 3, 0 To 1) As Double

Sub test()
    ' 生成初始数据
    Dim n As Integer
    n = 5000
    Dim a() As Double
    ReDim a(0 To n)
    Dim i As Integer
    For i = 0 To n
      a(i) = 1000 * Rnd
    Next
   
    ' 赋值
    b(0, 0) = 1
    b(0, 1) = a(0)
    b(1, 0) = 2
    b(1, 1) = a(1)
    b(2, 0) = 3
    b(2, 1) = a(2)
    ' 排序
    MinEx 4, a(3)
    Debug.Print b(0, 0) & ": " & b(0, 1)
    Debug.Print b(1, 0) & ": " & b(1, 1)
    Debug.Print b(2, 0) & ": " & b(2, 1)

    ' 排序
    For i = 4 To n
      MinEx i, a(i)
    Next
    Debug.Print b(0, 0) & "," & b(0, 1)
    Debug.Print b(1, 0) & "," & b(1, 1)
    Debug.Print b(2, 0) & "," & b(2, 1)
End Sub

Sub MinEx(ByVal Index As Long, ByVal Value As Double)
    b(3, 0) = Index ' 索引
    b(3, 1) = Value ' 值
   
    ' 数组排序
    Dim t As Double
    Dim i As Integer
    Dim j As Integer
    For i = 0 To 2
      For j = i + 1 To 3
            If b(i, 1) > b(j, 1) Then
                t = b(i, 0)
                b(i, 0) = b(j, 0)
                b(j, 0) = t
                t = b(i, 1)
                b(i, 1) = b(j, 1)
                b(j, 1) = t
            End If
      Next
    Next
End Sub

leeyeafu 发表于 2004-1-8 20:49:00

我的代码及运行测试结果


'为了得到程序运行时间，所有中间数据都声明为Long长整型，程序忽略了错误处理代码
Dim UserArray As Variant
Private Sub InitialArray()   '初始化数组
Dim SizeOfArray As Long    '数组大小
'当然我输入的是整数
SizeOfArray = CLng(ThisDrawing.Utility.GetString(False, "输入数组大小"))
Randomize
ReDim UserArray(1 To SizeOfArray) As Long
Dim i As Long
For i = 1 To SizeOfArray
    UserArray(i) = Int(1000000 * Rnd)   '随机填写长整数到数组中
Next i
MsgBox "数组初始化完成!"
End Sub

Private Sub Sort()
Dim m(1 To 3) As Long
m(1) = 1: m(2) = 2: m(3) = 3
'排序前三个数，代码可能不太好读，但效率高
Dim i As Long
If UserArray(m(1)) > UserArray(m(2)) Then t = m(1): m(1) = m(2): m(2) = t
If UserArray(m(1)) > UserArray(m(3)) Then t = m(1): m(1) = m(3): m(3) = t
If UserArray(m(2)) > UserArray(m(3)) Then t = m(2): m(2) = m(3): m(3) = t
'使用直接查找算法，仅一次循环
For i = 4 To UBound(UserArray)
    If UserArray(i) <= UserArray(m(1)) Then
      m(3) = m(2)
      m(2) = m(1)
      m(1) = i
    ElseIf UserArray(i) <= UserArray(m(2)) Then
      m(3) = m(2)
      m(2) = i
    ElseIf UserArray(i) <= UserArray(m(3)) Then
      m(3) = i
    End If
Next i
ThisDrawing.Utility.Prompt “最小值下标为：” & m(1)
ThisDrawing.Utility.Prompt “第二小值下标：” & m(2)
ThisDrawing.Utility.Prompt “第三小值下标：” & m(3)
End Sub

另外，对于whyer朋友的一些说法给予纠正：
折半是查找算法，不是排序算法，并且它只能在已经排序的序列中查找，在这个问题中用不上。冒泡是一种非常低效率的排序算法，不宜做大量数据排序。
我的机器，以上代码在ACAD 2004内嵌的VBA中运行，数组大小在百万以下得不到运行时间，数组大小为一百万时耗时约0.05秒，五千万约3.45秒，一亿约6.94秒。(同时运行明经网站和VC.Net 2003)再大的数组(我试了五亿)，我的虚拟内存不足。
页: [1] 2
查看完整版本: 关于快速找出最小3个数的算法问题