algorithm - 排列一个数组，使 2 个数字的平均值不在它们之间

Question

如题所说，找一个算法来排列数组。这是一个 Facebook 面试问题。

平均值需要准确。我们不对平均值进行四舍五入、下限或上限。

编辑:举个例子，如果数字是 1,2,5,9，那么排列 {1,9,2,5} 是有效的，但 {1,5,9,2} 不是因为平均1 和 9 的值为 5，位于它们之间。

Answer 1

被 Skyhawk 船长打败了，但是......

Module Module1

    Sub Main()
        Dim a() As Integer = {9, 4, 7, 6, 4, 4, 3, 4, 1}
        Dim n = a.Length

        'TODO: check that sanity has a reasonable vale
        Dim sanity As Integer = n
        Dim ok As Boolean = False
        Dim temp As Integer

        While Not ok And sanity > 0
            ok = True
            For i = 0 To n - 3
                If ((a(i) + a(i + 2)) / 2) = a(i + 1) Then
                    temp = a(i)
                    a(i) = a(i + 1)
                    a(i + 1) = temp
                    ok = False
                End If

            Next

            sanity -= 1
        End While
        Console.WriteLine("OK: " & ok.ToString())

        Console.WriteLine(String.Join(" ", a))

        Console.ReadLine()

    End Sub

End Module