Придумал вот такой устойчивый алгоритм сортировки, сложность O(n^2).
Идея вот в чём: допустим, нам нужно отсортировать массив по возрастанию. Для этого мы находим его минимальный элемент, добавляем его в массив-результат, а самому минимальному элементу из исходного массива присваиваем плюс бесконечность либо удаляем его. Если необходимо сортировать по возрастанию, находим максимальный элемент и присваиваем минус бесконечность.
Псевдокод:
Код:
|
sort(arr) {
result = [];
цикл по arr по итератору i:
j = индексМинЭлемента;
result[i] = arr[j];
arr[j] = Infinity;
возврат result;
} |
Пример реализации на javascript
:
Код:
|
function sort(array) {
var result = [];
for (var i = 0; i < array.length; i++) {
var min = array[0], n = 0;
for (var j = 0; j < array.length; j++)
if (array[j] < min)
min = array[j], n = j;
result.push(min);
array[n] = Infinity;
}
return result;
} |
Баян или нет?