В чем смысл медианы (первого, среднего и последнего) элементов?

Question

Может ли кто-нибудь сказать мне, что является медианным для вышеупомянутой проблемы в Quick sort? Пожалуйста, помогите мне с примером.

Answer 1

Если сортировать эти значения, медиана будет находиться в центре отсортированного списка

Если a <= b <= c то Ь медиана а, Ь, с

12,5,8 - медиана 8

Answer 2

В QuickSort , медианная из трех - это один из способов выбрать стержень на каждой итерации. Стержень - это элемент в массиве, который используется для разбиения массива путем сравнения всех его значений с точкой поворота.

Идеальное значение поворота - медиана массива, но для вычисления требуется время. Таким образом, люди использовали самое левое значение массива как простое значение поворота. Но это происходит плохо, когда массив уже отсортирован.

Правило медианы трех, рекомендованное here, является одним из способов получить хорошую производительность в случае уже отсортированного массива.

Answer 3

Предыдущие ответы хороши, вот (понятнее) пример:

{ 9, 7, 4, 12, 3, 1, 6, 1, 7, 4, 13, 2, 4, 15, 8, 9 } 

Выберите три значения в случайном порядке, в три раза:

{ 9, 7, 4 } 
{ 2, 12, 15 } 
{ 4, 1, 8 } 

Найти медиану каждого: 7, 12 , 4. Найти медиану этого: 7

Используйте это как свою точку опоры.

Answer 4

Медиана трех чисел является вторым по величине числом.