Этот метод работает только с массивом чисел, который удовлетворяет некоторым условиям. Поскольку я не пришелец из какой-то другой галактики, чтобы доказывать, что законы математики неверны 👽 !
Предисловие Мы знаем, что самый быстрый алгоритм сортировки массива занимает O(n *log(n)) времени, что также подтверждается математически. Но в стремлении сделать что-то в пятницу вечером, вместо того, чтобы переосмысливать, почему мои друзья не пригласили меня на свою вечеринку 😑 , я выбрал это.
Этот алгоритм основан на одном условии, что числа разбросаны по MSB, что означает, что должно быть только одно число из каждой категории диапазона. т.е. Чтобы получить этот диапазон, мы рассмотрим наиболее значимый 1 бит элемента (первое столкновение 1 слева). Что на самом деле говорит о самом высоком числе, которое он может сделать. Мы можем обнаружить это с помощью битовых манипуляций а затем мы определим позицию (индекс) числа в массиве на основе его позиции MSB.
Давайте закодируем Никаких Друзей Вроде ! Поскольку я нахожусь дома в пятницу вечером, и все числа, которые он сортирует, далеки друг от друга!
public void noFriendSort(){
int[] arr= {45, 1, 5, 150, 100, 3, 24, 11, 460};
int[] newarr=new int[9];
for(int v : arr) {
int temp=v;
int count=0;
for(int i=1; i<=9; i++) {
temp=temp>>1;
if(temp==0)
break;
count++;
}
newarr[count]=v;
}
}
Этот код может сортировать значения до 511, хотя он может доходить до диапазона int, но чем больше число, тем меньше смысла в коде. Поскольку входные данные должны быть более разбросанными. Таким образом, временная сложность этого кода будет составлять O(n* 9) который равен O(n) . Но поскольку он учитывает только одно число в диапазоне, теперь я могу сказать, что успешно потратил впустую свой вечер пятницы..
Но он выдает то, что говорит сортировка массива в O (n) ! Google Я буду ждать вашего звонка.
Оригинал: “https://dev.to/prateekbud/sort-array-in-o-n-time-1f8g”