Какой элемент массива был бы медианой, если бы размер массива был четным, а не нечетным?

Question

Я прочитал, что можно запустить быструю сортировку при O (nlogn)

алгоритм говорит, что на каждом шаге выбирайте медиану в качестве точки разворота

но предположим, что у нас есть этот массив:

10 8 39 2 9 20

какое значение будет медианой?

В математике, если я правильно помню, медиана равна (39 + 2) / 2 = 41/2 = 20,5

У меня нет 20,5 в моем массиве, хотя

заранее спасибо

Answer 1

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

Answer 2

Мы говорим о точной формулировке описания алгоритма здесь, и у меня нет текста, на который вы ссылаетесь. Но я думаю, что в контексте под «медианой» они, вероятно, подразумевали не математическую медиану значений в списке, а скорее среднюю точку в списке, то есть медианную ИНДЕКСУ, которая в этом кадре будет 3 или 4. Как и coffNjava говорит, вы можете взять любой.

Answer 3

Найти медиану несортированного набора чисел можно за O (N) время, но на самом деле нет необходимости находить истинную медиану для целей разворота быстрой сортировки.Вам просто нужно найти разумный стержень.

Как говорится в записи Википедии о быстрой сортировке :

В очень ранних версиях быстрой сортировки, самый левый элементраздел часто выбирается в качестве основного элемента.К сожалению, это вызывает поведение в худшем случае для уже отсортированных массивов, что является довольно распространенным вариантом использования.Проблема была легко решена путем выбора случайного индекса для оси, выбора среднего индекса раздела или (особенно для более длинных разделов) выбора медианы первого, среднего и последнего элемента раздела для центра (как рекомендованоР. Седжвик).

Найти медиану трех значений гораздо проще, чем найти ее для всей совокупности значений, а для коллекций, имеющих четное число элементов, это не имеет большого значениякакой из двух «средних» элементов вы выберете в качестве потенциального центра.

Answer 4

Медиана на самом деле определяется путем сортировки массива в первую очередь, поэтому в вашем примере медиана определяется путем расположения чисел как 2 8 9 10 20 39, а медиана будет средним двух средних элементов, (9+10) / 2 = 9,5, что вам совсем не поможет.Использование медианы - это своего рода идеальная ситуация, но я думаю, что сработало бы, если бы массив был хотя бы частично уже отсортирован.

С массивом с четными номерами вы не можете найти точную точку разворота, поэтому я считаю, что вы можете использовать любое из средних чисел.Это немного снизит эффективность, но не существенно, если вы не закончили сортировку даже массивов.