Javascript Array: Алгоритм сортировки и выбора

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

Сортировка

Если важна скорость (что, как вам кажется, она и есть), то рассматривали ли вы сети сортировки?Я обнаружил, что это невероятно быстро при сортировке небольших наборов чисел.

Для сортировки с сеткой сортировки:

Сеть для N = 4 с использованием алгоритма Бозе-Нельсона.

CreationDate: Tue 15 Feb 04:44:06 2011 Создатель: модуль perl Algorithm :: Networksort version 1.05.Сеть для N = 4, используя алгоритм Бозе-Нельсона.Строка ввода.Размер компаратора 1. Размер компаратора 2. В этой сети 5 компараторов, сгруппированных в 3 параллельные операции.

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

Это отображается в 4 столбцах.

Псевдо:

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

Вы должны пойти по алгоритму, который имеет наиболее смысловой смысл и который проще всего поддерживать, вероятно, при чем-либо еще, если только скорость не имеет решающего значения.

Answer 2

Это вернет случайный индекс равных значений:

var myNums = new Array(211, 211, 211,211,214, 255);
myNums = myNums.sort();
if(myNums.length == 0)
    alert("Array is zero sized");
else
{
   var smallest = myNums[0];
   var last=0;
   var start = 0;
   while(smallest == myNums[last])
       last++;
   last = last-1;
   var randIndex = Math.floor(Math.random() *(last - start + 1)+ start);
   alert(randIndex);
}

Посмотрите, как это работает здесь: http://jsfiddle.net/rAbh3/

Answer 3

Выполнение цикла for справа налево для выбора элементов сделает свое дело, и если это будет сделано после процесса сортировки, это только добавит N к сложности

Изменение с nlogn на nlogn + nне так уж и дорого.

Редактировать: Самые верхние равные значения в вашем примере, не должно ли это быть:

[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 1 or 2 
[0, 1, 1, 4] // results in 1 or 2;

??