В O (n) псевдокод:
def sort (src):
# Create an empty array, and set pointer to its start.
def dest as array[sizeof src]
pto = 0
# For every possible value.
for val in 0, 1, 2:
# Check every position in the source.
for pfrom ranges from 0 to sizeof(src):
# And transfer if matching (includes update of dest pointer).
if src[pfrom] is val:
dest[pto] = val
pto = pto + 1
# Return the new array (or transfer it back to the source if desired).
return dest
Это в основном итерация по списку источников три раза, добавление элементов, если они соответствуют значению, требуемому на этом проходе.Но это все равно O (n).
Эквивалентный код Java будет:
class Test {
public static int [] mySort (int [] src) {
int [] dest = new int[src.length];
int pto = 0;
for (int val = 0; val < 3; val++)
for (int pfrom = 0; pfrom < src.length; pfrom++)
if (src[pfrom] == val)
dest[pto++] = val;
return dest;
}
public static void main(String args[]) {
int [] arr1 = {2, 0, 1, 2, 1, 2, 1, 0, 2, 0};
int [] arr2 = mySort (arr1);
for (int i = 0; i < arr2.length; i++)
System.out.println ("Array[" + i + "] = " + arr2[i]);
}
}
, который выдает:
Array[0] = 0
Array[1] = 0
Array[2] = 0
Array[3] = 1
Array[4] = 1
Array[5] = 1
Array[6] = 2
Array[7] = 2
Array[8] = 2
Array[9] = 2
А если серьезно, еслипотенциальный работодатель задал мне этот вопрос, я бы прямо заявил, что могу ответить на вопрос, если они того пожелают, но что правильный ответ - просто использовать Array.sort.Тогда если и только , если есть проблема с производительностью этого метода и конкретных наборов данных, вы можете исследовать более быстрый способ.
И этот более быстрый способ почти наверняка будет включать подсчет,несмотря на то, что требования были.Вы не ограничиваете своих разработчиков произвольными ограничениями.В требованиях должно быть указано что требуется , а не как.
Если вы ответите мне на этот вопрос таким образом, я найму вас на месте.