JavaScript 数组 : Algorithm sorting and picking

Question

在本例中，我有一个包含 4 个介于 0 和 256 之间的整数的数组，需要对其进行升序排序。例如:

[0, 12, 211, 4] 当我排序时，我得到(当然):[0, 4, 12, 211]

我只是通过请求Array[0](第一个索引)来获取整数值

现在，我的问题是；很多时候，数组中有相等的值。喜欢:

[0, 0, 0, 12] // already sorted

在这些情况下，我需要从最上面的相等值 (0,0,0) 中选择一个随机索引，其他可能性是(排序后):

[211, 211, 211, 255] // results in 0 OR 1 OR 2
[13, 13, 125, 256] // results in 0 OR 1
[4, 211, 211, 255] // results in 0 
[0, 1, 1, 4] // results in 0;

所以我需要从升序排序数组中最上面的值中选择一个随机索引。 这是在排序时完成的，还是比许多 if-elses 更简单的方式？

Answer 1

排序

如果速度很重要(您似乎暗示它很重要)，那么您是否研究过排序网络？我发现在对少量数字进行排序时，它们的速度非常快。

使用排序网络进行排序:

Network for N=4, using Bose-Nelson Algorithm.

CreationDate: Tue Feb 15 04:44:06 2011 Creator: perl module Algorithm::Networksort version 1.05. Network for N=4, using Bose-Nelson Algorithm. Input line. Comparator size 1. Comparator size 2. There are 5 comparators in this network, grouped into 3 parallel operations.

[[0,1],[2,3]] [[0,2],[1,3]] [[1,2]]

This is graphed in 4 columns.

伪:

if [0] > [1] {  swap(0, 1)  }
if [2] > [3] {  swap(2, 3)  }
if [0] > [2] {  swap(0, 2)  }
if [1] > [3] {  swap(1, 3)  }
if [1] > [2] {  swap(1, 2)  }

查找索引集

无论如何，这个问题可以通过一种分而治之(伪)来解决:

// First index is unique
if [0] != [1]
    return 0
// First 2 are equal
else if [1] != [2]
    return 0 or 1
// First 3 are equal
else if [2] != [3]
    return 0 or 1 or 2
// All are equal
else
    return 0 or 1 or 2 or 3
end

或者你可以用一个循环来做到这一点:

for i = 0 to 2

    if [i] != [i+1]
       return random(0 to i)
       break loop
    end if

loop

除非速度至关重要，否则您应该选择最具有语义意义且最容易维护的算法。