算法，又见算法，10个自然数，选中任意一个，列出和它最接近的5个数字， 高分求最快速的算法！！！！！！

Question

如题： 10 个大于0的整数。 从中间任意取出一个来，用对快的速度得到和此数字最接近的5个数字。大家动脑劲吧，偶老了，只想出排序等的方法，可是光排序就要用到2次循环，不是很满意。喜欢研究算法的朋友们帮忙啦，偶老蔡开贴从来不会不结的。

Answer 1

to sparkwong(天天跑来蹭分)左边右边无所谓，要是有相同的值，可以任意取一个或多个。例如： 3，3，1，6，2，7，5，8，9，7
指定数为6
列出： 5，7，7，8，3（或者9）

Answer 2

先頂一把，晚上有時間了，好好想想。--------
www.vicmiao.com
努力就有美好時光！

Answer 3

const ALL as long =  10
const NEAR as long = 5dim a(ALL-1) as int
' 初始化 a(0) 到 a(ALL-1)
dim test as int 
' test从中间选一个dim i as long,j as long, k as long 
dim dif(NEAR-1) as long  
for i=0 to NEAR-1 : dif(i) = &h7fffffff&: next i
for i = 0 to ALL-1
   if a(i) = test then next for   '是这么忽略本次循环吗? 不记得了
   j = NEAR-1
   do while abs(a(i)-test) < dif(j) and j>=0 : j=j-1 : loop
   for k=NEAR-1 to j+2 step -1 :  dif(k)=dif(k-1) : next k
   if j<NEAR-1 then a(j+1) = test
next i
   
'最进的5个数(排除相等的)存在dif(i)中

Answer 4

刚刚随便写的， 没调, 这个调试通过Private Sub Form_Load()
    func
End SubPrivate Sub func()
    Const ALL As Long = 10
    Const NEAR As Long = 5
    
    Dim a(ALL - 1) As Long
    ' 初始化 a(0) 到 a(ALL-1)
    a(0) = 3: a(1) = 3: a(2) = 1: a(3) = 6: a(4) = 2
    a(5) = 7: a(6) = 5: a(7) = 8: a(8) = 9: a(9) = 7
    Dim test As Long
    ' test从中间选一个
    test = 6
    
    Dim i As Long, j As Long, k As Long
    Dim dif(NEAR - 1) As Long
    For i = 0 To NEAR - 1: dif(i) = &H7FFFFFFF: Next i
    For i = 0 To ALL - 1
        If a(i) <> test Then
            j = NEAR - 1
            Do While Abs(a(i) - test) < Abs(dif(j) - test)
                j = j - 1
                If j < 0 Then Exit Do
            Loop
            For k = NEAR - 1 To j + 2 Step -1: dif(k) = dif(k - 1): Next k
            If j < NEAR - 1 Then dif(j + 1) = a(i)
        End If
    Next i
    
    For i = 0 To NEAR - 1
        Debug.Print dif(i)
    Next i
End Sub

Answer 5

Const ALL As Long = 10
    Const NEAR As Long = 5这2个数相差越大,效率越高, 如果all的大小可以忽略near
则算法为 o(n)

Answer 6

这个问题可推广如下；
一个整数集合中有n个数。从中任选一个数m，求这个集合中最接近m的k个数。我们知道最好的k-selection算法在最坏情况下时间复杂度是O(n)。
而这个问题很容易在O(n)时间内转化为k-selection问题，所以可以有O(n)算法。

Answer 7

可是实际看下来，这个算法比排序还要慢阿。在我的机器上循环1000000次测试用上面的算法平均耗时3.2秒
用排序法耗时1.3秒我的排序法如下：Private Sub FSort(ByVal Test As Long)
Dim A(9) As Long
A(0) = 3: A(1) = 3: A(2) = 1: A(3) = 6: A(4) = 2
A(5) = 7: A(6) = 5: A(7) = 8: A(8) = 9: A(9) = 7
Dim D(9) As Long
Dim I As Long
Dim L As Long
Dim M As Long
Dim N As Long
Dim GG As Long
T = timeGetTime
For GG = 0 To 1000000
For I = 0 To 9
   D(I) = Abs(A(I) - Test)
Next
For N = 8 To 1 Step -1
   For I = 0 To N
      L = I + 1
      If D(I) > D(L) Then
         M = D(I)
         D(I) = D(L)
         D(L) = M
         
         M = A(I)
         A(I) = A(L)
         A(L) = M
      End If
   Next
Next
Next
Me.Cls
For I = 1 To 5
   Me.Print A(I)
Next
Me.Print timeGetTime - T
End Sub
调用： 
Private Sub Command1_Click()
FSort 6
End Sub

Answer 8

偶用的方法和shan1119(大天使)说的基本是一样的。

Answer 9

又仔细想了一下，因为只是需要列出最接近的5个数字，没有必要按照插值从近到远排列。
因此连排序都不用了，时间又省下一半来。（半调子折半法）在我的机器上循环1000000次测试
平均耗时：0.7秒代码如下：Private Sub FSort1(ByVal Test As Long)
Dim A(9) As Long
A(0) = 3: A(1) = 3: A(2) = 1: A(3) = 6: A(4) = 2
A(5) = 7: A(6) = 5: A(7) = 8: A(8) = 9: A(9) = 7
Dim D(9) As Long
Dim I As Long
Dim L As Long
Dim M As Long
Dim N As Long
Dim GG As Long
T = timeGetTime
For GG = 0 To 1000000
   For I = 0 To 9
      D(I) = Abs(A(I) - Test)
   Next
   For N = 0 To 5
      For I = 5 To 9
         
         If D(N) > D(I) Then
            M = D(N)
            D(N) = D(I)
            D(I) = M
            
            M = A(N)
            A(N) = A(I)
            A(I) = M
            Exit For
         End If
      Next
   Next
Next
Me.Cls
For I = 0 To 4
   If A(I) = Test Then
      A(I) = A(5)
      Exit For
   End If
Next
For I = 0 To 4
   Me.Print A(I)
Next
Me.Print timeGetTime - T
End Sub调用：
Private Sub Command1_Click()
FSort1 6
End Sub

Answer 10

好久没用vb了，为什么max，min方法都不能用啊？我想max取得最大的，直接给它赋成0，取4次或者5次，剩下的应该是结果对应的索引了吧？是不能直接用max，min吗？都忘光了快

Answer 11

TO shan1119(大天使)
哪有什么MIN,MAX可用阿？
就算有，也是比较两个数的

Answer 12

再次修正半吊子折半法，使之可以查找出最近的任意个：Option Explicit
Private Declare Function timeGetTime Lib "winmm.dll" () As Long
Const ALL As Long = 1000
Const NEAR As Long = 5
Dim T As Long
Dim A(ALL - 1) As LongPrivate Sub Form_Load()
Dim I As Long
For I = 0 To ALL - 1
   A(I) = I
Next
End SubPrivate Sub FSort1(ByVal Test As Long)Dim D(ALL - 1) As Long
Dim I As Long
Dim L As Long
Dim M As Long
Dim N As Long
Dim GG As Long
T = timeGetTime
For GG = 0 To 10000
   For I = 0 To ALL - 1
      D(I) = Abs(A(I) - Test)
   Next
   For N = 0 To 5
      For I = 5 To 999
         
         If D(N) > D(I) Then
            M = D(N)
            D(N) = D(I)
            D(I) = M
            
            M = A(N)
            A(N) = A(I)
            A(I) = M
            'Exit For
         End If
      Next
   Next
Next
Me.Cls
For I = 0 To 4
   If A(I) = Test Then
      A(I) = A(5)
      Exit For
   End If
Next
For I = 0 To 4
   Me.Print A(I)
Next
Me.Print timeGetTime - T
End Sub调用：
Private Sub Command1_Click()
FSort1 990
End Sub试试这个吧，将待选数字扩大到1000个，选择5个最近的，循环10000次

Answer 13

数组初始化这样整多好
    Dim Temp As Variant
    Temp = Array(3, 5, 6, 7, 8, 9, 6, 5, 4, 3)

Answer 14

有你们那么复杂吗?  我想loop 一次就可以搞定了

Answer 15

TO qscandwh(思成)
LOOP一次试试看吧

Answer 16

楼上的想的不对
考虑一下下面的算法没时间了
先写出算法常量 a = 数字总数=10
常量 b = 取出的数的个数=5
常量 c = 标准数 =x声明数组 array[b][2];
声明数组 buf[a]; //用作存储待比较的数字 array[0][0]=buf[0]
array[0][1]=|buf[0]-x|loop n=1
取buf[]中前b个数作2分排序 
n++
end loop while n<bloop n=b
以后每取一个数
均插入到array[][]中的合适位置
合适位置的查找采用二分法n++
end loop while n=a结束效率取决于b的大小
b越小效率越高

Answer 17

漏写几点
1.前b次的结果放入array[][]
2.后a-b次，插入后将array[][]最后一个元素删除

Answer 18

效率应该是前b次
log  b
   2
后几次应该是n(log  b)
     2
......

Answer 19

TO jjmm2035...
以后每取一个数
均插入到array[][]中的合适位置
合适位置的查找采用二分法
...这好像就是最慢的部分了吧，可不要省略阿。

Answer 20

TO WallesCai(沧海明月一度,西风残阳无悔.) 
确实
不过
这也是排序最根本的问题
最基本的排序
......
看那个算法快就用哪个吧
......
嘿嘿

Answer 21

TO zswang(伴水清清)(专家门诊清洁工)
不是20次，是100次TO Modest(塞北雪貂)·(偶最欣赏楼主的分)
请仔细想想，先排序再取临近值肯定不是最快的。并且在取“临近值”的时候还是存在一个插值排序的过程，这样更慢了。

Answer 22

TO WallesCai:然后求这个数组中最小的若干个数
-------又回到排序上来了,就是这个最慢
从n个数中找第k小的是k-selection问题，最好的算法是O(n).
找到第k小的数后在遍历一次树祖，可以得到最小的k个数。（如果有重复的数，最多遍历两次）。所以整个问题的复杂度在最坏情况下是O(n)，和k的大小无关。很长时间没用过basic了，所以写不出程序。:(不过你可以很容易google到k-selection的算法。

Answer 23

来一个用对象的方法，纯粹开阔一下思路，无需考虑效率。（大约比楼主的慢100倍）Private Sub FSort2(ByVal Test As Long)
Dim A(9) As Long
Dim D(9) As Long
Dim I As Long
Dim J As LongDim C1 As New Collection
Dim ExitBool As BooleanA(0) = 3: A(1) = 3: A(2) = 1: A(3) = 6: A(4) = 2
A(5) = 7: A(6) = 5: A(7) = 8: A(8) = 9: A(9) = 7
Dim Num(4) As LongDim GG As Long
T = timeGetTimeFor GG = 0 To 1000000    Set C1 = Nothing
    Set C1 = New Collection
    
    For I = 0 To 9
        D(I) = Abs(A(I) - Test)
    Next I
    
    C1.Add D(0)
    
    For I = 1 To 9
        For J = C1.Count To 1 Step -1
            If D(I) > C1(J) Then
                C1.Add CStr(I), , , J
                ExitBool = True
                Exit For
            End If
        Next J
        If ExitBool = False Then
            C1.Add CStr(I), , J + 1
        Else
            ExitBool = False
        End If
    Next I
    
    For J = 0 To 4
        Num(J) = A(C1(J + 1))
    Next J
Next GG
For I = 0 To 4
   Me.Print Num(I)
Next
Me.Print timeGetTime - T
End Sub

Answer 24

可以参考 C++ STL 的 nth_element 算法：）

Answer 25

TO cxjddd(又是花开时) 
谢谢你的提醒，找了很多资料看，没有找到原代码，只有一些接口说明。
所以没有办法用VB实现。
看来只能用自己的办法了。

Answer 26

to jcyluck(VB 2005 QQ群：26096739)代码简单不等于速度快，用数据库的话，前面的任何一个算法都要比它快100倍以上。你可以自己测试一下。

Answer 27

Option ExplicitPrivate TARGET(0 To 5) As Long
Private SOURCE(0 To 999) As LongPrivate Sub Form_Load()
    On Error Resume Next
    Dim lNextLoop As Long
    For lNextLoop = 0 To 999
       SOURCE(lNextLoop) = lNextLoop
    Next lNextLoop
End SubPrivate Sub AnalyseVicinalNumber(ByVal Reference As Long)
    Dim TempTime As Single
    Dim lNext As Long, lLoop As Long
    
    TempTime = Timer
    For lLoop = 0 To 10000
        TARGET(0) = 0: TARGET(1) = 99995
        TARGET(2) = 99996: TARGET(3) = 99997
        TARGET(4) = 99998: TARGET(5) = 99999
        For lNext = 0 To ALL - 1
            Select Case Abs(SOURCE(lNext) - Reference)
                Case Is <= Abs(TARGET(0) - Reference)
                    TARGET(5) = TARGET(4)
                    TARGET(4) = TARGET(3)
                    TARGET(3) = TARGET(2)
                    TARGET(2) = TARGET(1)
                    TARGET(1) = TARGET(0)
                    TARGET(0) = SOURCE(lNext)
                    
                Case Is <= Abs(TARGET(1) - Reference)
                    TARGET(5) = TARGET(4)
                    TARGET(4) = TARGET(3)
                    TARGET(3) = TARGET(2)
                    TARGET(2) = TARGET(1)
                    TARGET(1) = SOURCE(lNext)
                    
                Case Is <= Abs(TARGET(2) - Reference)
                    TARGET(5) = TARGET(4)
                    TARGET(4) = TARGET(3)
                    TARGET(3) = TARGET(2)
                    TARGET(2) = SOURCE(lNext)
                
                Case Is <= Abs(TARGET(3) - Reference)
                    TARGET(5) = TARGET(4)
                    TARGET(4) = TARGET(3)
                    TARGET(3) = SOURCE(lNext)
                    
                Case Is <= Abs(TARGET(4) - Reference)
                    TARGET(5) = TARGET(4)
                    TARGET(4) = SOURCE(lNext)
                    
                Case Else
            End Select
        Next lNext
    Next lLoop
    Debug.Print "{"; TARGET(5); TARGET(4); TARGET(2); "[" & Reference & "]"; TARGET(1); TARGET(3); "}"
    Debug.Print "Timer:  " & CStr(Timer - TempTime)
End SubPrivate Sub Command1_Click()
    AnalyseVicinalNumber 50
End Sub
循环10000次的耗时结果：50:
{ 47  48  49 [50] 51  52 }
Timer:  1.625980:
{ 977  978  979 [980] 981  982 }
Timer:  3.46875我可以断定，在1000个数字内找5个靠近某个数字的代码，以上是比较快的了

Answer 28

1/Dunzip(路登软件,一路登先! / http://www.dunzip.com)
  算法测试结果：
  850      { 847  848  849  851  852 }   Timer:  5.671875
  10       { 7    8    9    11   12  }   Timer:  3.531252/WallesCai(沧海明月一度,西风残阳无悔.) 
  算法测试结果：
  850      { 847  849  851  848  852 }   Timer:  7.140625 
  10       { 7    9    11   8    12  }   Timer:  7.578125
3/测试平台C2.4,256M，ASUS Motherboard
4/经过测试发现：
  A:WallesCai算法速度平均
  B:Dunzip算法速度不平均，找前面的比找后面快.

Answer 29

看了Dunzip的算法，确实比较快，因为结构简单，循环少。
缺点是代码不够灵活，如果是1000个数中找100个最近值的话，代码量就很可观了。
呵呵，纯粹找茬，稍微改动一下，其实只要把中间的SELECT中的东西用一个循环代替就好了。
只是速度也会下降一些。好了，结贴了。谢谢大家的参与和建议。
希望还有更多的问题能这样大家一起讨论。