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

topirol

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

mccad

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

topirol

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

myfreemind

用排序法比较好！
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

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

whyer

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

whyer

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

whyer

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

efan2000

这个不知道是否满足。

2. 
   
3. Option Explicit
   
4. 
   
5. ' 第2维：0索引，1值
   
6. Dim b(0 To 3, 0 To 1) As Double
   
7. 
   
8. Sub test()
   
9.     ' 生成初始数据
   
10.     Dim n As Integer
    
11.     n = 5000
    
12.     Dim a() As Double
    
13.     ReDim a(0 To n)
    
14.     Dim i As Integer
    
15.     For i = 0 To n
    
16.         a(i) = 1000 * Rnd
    
17.     Next
    
18.    
    
19.     ' 赋值
    
20.     b(0, 0) = 1
    
21.     b(0, 1) = a(0)
    
22.     b(1, 0) = 2
    
23.     b(1, 1) = a(1)
    
24.     b(2, 0) = 3
    
25.     b(2, 1) = a(2)
    
26.     ' 排序
    
27.     MinEx 4, a(3)
    
28.     Debug.Print b(0, 0) & ": " & b(0, 1)
    
29.     Debug.Print b(1, 0) & ": " & b(1, 1)
    
30.     Debug.Print b(2, 0) & ": " & b(2, 1)
    
31. 
    
32.     ' 排序
    
33.     For i = 4 To n
    
34.         MinEx i, a(i)
    
35.     Next
    
36.     Debug.Print b(0, 0) & "," & b(0, 1)
    
37.     Debug.Print b(1, 0) & "," & b(1, 1)
    
38.     Debug.Print b(2, 0) & "," & b(2, 1)
    
39. End Sub
    
40. 
    
41. Sub MinEx(ByVal Index As Long, ByVal Value As Double)
    
42.     b(3, 0) = Index ' 索引
    
43.     b(3, 1) = Value ' 值
    
44.    
    
45.     ' 数组排序
    
46.     Dim t As Double
    
47.     Dim i As Integer
    
48.     Dim j As Integer
    
49.     For i = 0 To 2
    
50.         For j = i + 1 To 3
    
51.             If b(i, 1) > b(j, 1) Then
    
52.                 t = b(i, 0)
    
53.                 b(i, 0) = b(j, 0)
    
54.                 b(j, 0) = t
    
55.                 t = b(i, 1)
    
56.                 b(i, 1) = b(j, 1)
    
57.                 b(j, 1) = t
    
58.             End If
    
59.         Next
    
60.     Next
    
61. End Sub
    

<br /> Option Explicit<br /> <br /> ' 第2维：0索引，1值<br /> Dim b(0 To 3, 0 To 1) As Double<br /> <br /> Sub test()<br />     ' 生成初始数据<br />     Dim n As Integer<br />     n = 5000<br />     Dim a() As Double<br />     ReDim a(0 To n)<br />     Dim i As Integer<br />     For i = 0 To n<br />         a(i) = 1000 * Rnd<br />     Next<br />     <br />     ' 赋值<br />     b(0, 0) = 1<br />     b(0, 1) = a(0)<br />     b(1, 0) = 2<br />     b(1, 1) = a(1)<br />     b(2, 0) = 3<br />     b(2, 1) = a(2)<br />     ' 排序<br />     MinEx 4, a(3)<br />     Debug.Print b(0, 0) & ": " & b(0, 1)<br />     Debug.Print b(1, 0) & ": " & b(1, 1)<br />     Debug.Print b(2, 0) & ": " & b(2, 1)<br /> <br />     ' 排序<br />     For i = 4 To n<br />         MinEx i, a(i)<br />     Next<br />     Debug.Print b(0, 0) & "," & b(0, 1)<br />     Debug.Print b(1, 0) & "," & b(1, 1)<br />     Debug.Print b(2, 0) & "," & b(2, 1)<br /> End Sub<br /> <br /> Sub MinEx(ByVal Index As Long, ByVal Value As Double)<br />     b(3, 0) = Index ' 索引<br />     b(3, 1) = Value ' 值<br />     <br />     ' 数组排序<br />     Dim t As Double<br />     Dim i As Integer<br />     Dim j As Integer<br />     For i = 0 To 2<br />         For j = i + 1 To 3<br />             If b(i, 1) > b(j, 1) Then<br />                 t = b(i, 0)<br />                 b(i, 0) = b(j, 0)<br />                 b(j, 0) = t<br />                 t = b(i, 1)<br />                 b(i, 1) = b(j, 1)<br />                 b(j, 1) = t<br />             End If<br />         Next<br />     Next<br /> End Sub<br />

leeyeafu

2. 
   
3. '为了得到程序运行时间，所有中间数据都声明为Long长整型，程序忽略了错误处理代码
   
4. Dim UserArray As Variant
   
5. Private Sub InitialArray()   '初始化数组
   
6.   Dim SizeOfArray As Long    '数组大小
   
7. '当然我输入的是整数
   
8.   SizeOfArray = CLng(ThisDrawing.Utility.GetString(False, "输入数组大小"))  
   
9.   Randomize
   
10.   ReDim UserArray(1 To SizeOfArray) As Long
    
11.   Dim i As Long
    
12.   For i = 1 To SizeOfArray
    
13.     UserArray(i) = Int(1000000 * Rnd)   '随机填写长整数到数组中
    
14.   Next i
    
15.   MsgBox "数组初始化完成!"
    
16. End Sub
    
17. 
    
18. Private Sub Sort()
    
19.   Dim m(1 To 3) As Long
    
20.   m(1) = 1: m(2) = 2: m(3) = 3
    
21.   '排序前三个数，代码可能不太好读，但效率高
    
22.   Dim i As Long
    
23.   If UserArray(m(1)) > UserArray(m(2)) Then t = m(1): m(1) = m(2): m(2) = t
    
24.   If UserArray(m(1)) > UserArray(m(3)) Then t = m(1): m(1) = m(3): m(3) = t
    
25.   If UserArray(m(2)) > UserArray(m(3)) Then t = m(2): m(2) = m(3): m(3) = t
    
26.   '使用直接查找算法，仅一次循环
    
27.   For i = 4 To UBound(UserArray)
    
28.     If UserArray(i) <= UserArray(m(1)) Then
    
29.       m(3) = m(2)
    
30.       m(2) = m(1)
    
31.       m(1) = i
    
32.     ElseIf UserArray(i) <= UserArray(m(2)) Then
    
33.       m(3) = m(2)
    
34.       m(2) = i
    
35.     ElseIf UserArray(i) <= UserArray(m(3)) Then
    
36.       m(3) = i
    
37.     End If
    
38.   Next i
    
39.   ThisDrawing.Utility.Prompt “最小值下标为：” & m(1)
    
40.   ThisDrawing.Utility.Prompt “第二小值下标：” & m(2)
    
41.   ThisDrawing.Utility.Prompt “第三小值下标：” & m(3)
    
42. End Sub
    

<br /> '为了得到程序运行时间，所有中间数据都声明为Long长整型，程序忽略了错误处理代码<br /> Dim UserArray As Variant<br /> Private Sub InitialArray()   '初始化数组<br />   Dim SizeOfArray As Long    '数组大小<br /> '当然我输入的是整数<br />   SizeOfArray = CLng(ThisDrawing.Utility.GetString(False, "输入数组大小"))  <br />   Randomize<br />   ReDim UserArray(1 To SizeOfArray) As Long<br />   Dim i As Long<br />   For i = 1 To SizeOfArray<br />     UserArray(i) = Int(1000000 * Rnd)   '随机填写长整数到数组中<br />   Next i<br />   MsgBox "数组初始化完成!"<br /> End Sub<br /> <br /> Private Sub Sort()<br />   Dim m(1 To 3) As Long<br />   m(1) = 1: m(2) = 2: m(3) = 3<br />   '排序前三个数，代码可能不太好读，但效率高<br />   Dim i As Long<br />   If UserArray(m(1)) > UserArray(m(2)) Then t = m(1): m(1) = m(2): m(2) = t<br />   If UserArray(m(1)) > UserArray(m(3)) Then t = m(1): m(1) = m(3): m(3) = t<br />   If UserArray(m(2)) > UserArray(m(3)) Then t = m(2): m(2) = m(3): m(3) = t<br />   '使用直接查找算法，仅一次循环<br />   For i = 4 To UBound(UserArray)<br />     If UserArray(i) <= UserArray(m(1)) Then<br />       m(3) = m(2)<br />       m(2) = m(1)<br />       m(1) = i<br />     ElseIf UserArray(i) <= UserArray(m(2)) Then<br />       m(3) = m(2)<br />       m(2) = i<br />     ElseIf UserArray(i) <= UserArray(m(3)) Then<br />       m(3) = i<br />     End If<br />   Next i<br />   ThisDrawing.Utility.Prompt “最小值下标为：” & m(1) <br />   ThisDrawing.Utility.Prompt “第二小值下标：” & m(2) <br />   ThisDrawing.Utility.Prompt “第三小值下标：” & m(3) <br /> End Sub<br />

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