Как делает вид JavaScript () работа?
>>> def unique(list):
... y = []
... for x in list:
... if x not in y:
... y.append(x)
... return y
5 ответов
Вызывается ли функция обратного вызова сортировки массива много раз в ходе сортировки?
Да
Если да, то я хотел бы знать, какие два числа передаются в функцию каждый раз
Вы могли узнать себя с помощью:
array.sort((a,b) => {
console.log(`comparing ${a},${b}`);
return a > b ? 1
: a === b ? 0
: -1;
});
EDIT
Это результат, который у меня есть:
25,8
25,7
8,7
25,41
Интерпретатор JavaScript имеет встроенную реализацию алгоритма сортировки . Он вызывает функцию сравнения несколько раз во время операции сортировки. Количество вызовов функции сравнения зависит от конкретного алгоритма, данных, которые нужно отсортировать, и порядка, в котором они находятся до сортировки.
Некоторые алгоритмы сортировки плохо работают с уже отсортированными списками, потому что это заставляет их делать гораздо больше сравнений, чем в обычном случае. Другие хорошо справляются с предварительно отсортированными списками, но бывают и другие случаи, когда их можно «обманом» заставить работать плохо.
Существует множество широко используемых алгоритмов сортировки, потому что ни один алгоритм не идеален для всех целей. Два наиболее часто используемых для общей сортировки - это Quicksort и merge sort . Быстрая сортировка часто является более быстрой из двух, но сортировка слиянием имеет несколько хороших свойств, которые могут сделать ее лучшим выбором в целом. Сортировка слиянием стабильна , а Quicksort - нет. Оба алгоритма можно распараллелить, но способ работы сортировки слиянием делает параллельную реализацию более эффективной при прочих равных.
Ваш конкретный интерпретатор JavaScript может использовать один из этих алгоритмов или что-то совсем другое. Стандарт ECMAScript не определяет, какой алгоритм должна использовать соответствующая реализация. Он даже явно отрицает необходимость стабильности.
но способ работы сортировки слиянием делает параллельную реализацию более эффективной при прочих равных.Ваш конкретный интерпретатор JavaScript может использовать один из этих алгоритмов или что-то совсем другое. Стандарт ECMAScript не определяет, какой алгоритм должна использовать соответствующая реализация. Он даже явно отрицает необходимость стабильности.
но способ работы сортировки слиянием делает параллельную реализацию более эффективной при прочих равных.Ваш конкретный интерпретатор JavaScript может использовать один из этих алгоритмов или что-то совсем другое. Стандарт ECMAScript не определяет, какой алгоритм должна использовать соответствующая реализация. Он даже явно отрицает необходимость стабильности.
Сравниваются пары значений, по одной паре за раз. Сравниваемые пары являются деталями реализации - не думайте, что они будут одинаковыми в каждом браузере. Обратный вызов может быть любым (так что вы можете сортировать строки, римские цифры или что-то еще, где вы можете придумать функцию, возвращающую 1,0, -1).
При сортировке JavaScript следует помнить о том, что она стабильность не гарантируется.
Вызывается ли функция обратного вызова сортировки массива много раз в ходе сортировки?
Да, именно так. Обратный вызов используется для сравнения пар элементов в массиве по мере необходимости, чтобы определить, в каком порядке они должны быть. Такая реализация функции сравнения не является нетипичной при работе с числовой сортировкой. Подробности в спецификации или на некоторых других более читаемых сайтах.
Вызывается ли функция обратного вызова сортировки массива много раз в ходе сортировки?
Поскольку это сортировка сравнения, для данных N элементов функция обратного вызова должна вызываться в среднем (N * Lg N) раз для быстрой сортировки, такой как Quicksort . Если используемый алгоритм похож на Bubble Sort , то функция обратного вызова будет вызываться в среднем (N * N) раз.
Минимальное количество вызовов для сортировки сравнения составляет (N-1) и это только для обнаружения уже отсортированного списка (т. е. на раннем этапе пузырьковой сортировки, если свопы не происходят).