Превосходство Quicksort над Пирамидальной сортировкой
Формат CSV звучит достаточно легким для StringTokenizer, но это может стать более сложным. Здесь в Германии точка с запятой используется в качестве разделителя, и ячеек, содержащих разделители, нужно оставить. Вы не собираетесь обрабатывать это легко с StringTokenizer.
я пошел бы для http://sourceforge.net/projects/javacsv
4 ответа
Одним из основных факторов является то, что быстрая сортировка имеет лучшую локальность ссылки - следующая вещь, к которой нужно обратиться, обычно находится в памяти близко к тому, на что вы только что посмотрели. В отличие от этого, heapsort прыгает значительно больше. Поскольку вещи, которые расположены близко друг к другу, скорее всего, будут кэшироваться вместе, быстрая сортировка имеет тенденцию быть быстрее.
Однако производительность быстрой сортировки в худшем случае значительно хуже, чем у heapsort. Поскольку для некоторых критически важных приложений требуются гарантии быстродействия, heapsort - правильный путь для таких случаев.
Вот пара объяснений:
http://www.cs.auckland.ac.nz/software/AlgAnim/qsort3.html
http: //users.aims. ac.za/~mackay/sorting/sorting.html
По сути, даже если наихудший случай быстрой сортировки - O (n ^ 2), в среднем она будет работать лучше. : -)
Сложность в среднем случае и тот факт, что вы можете предпринять простые шаги, чтобы минимизировать риск наихудшей сложности в Quicksort (например, выберите опорную точку в качестве медианы трех элементов, а не одного выбранное положение).
Нотация большого O означает, что время, необходимое для сортировки n элементов, ограничено выше функцией c * n * log (n) , где c - некоторое неуказанное постоянный коэффициент. Нет причин, по которым константа c должна быть одинаковой для быстрой сортировки и heapsort . Итак, реальный вопрос: почему вы ожидаете, что они будут одинаково быстрыми?
Quicksort всегда был несколько быстрее, чем heapsort на практике, но с тех пор разница стала больше, как уже упоминалось. Раньше локальность доступа к памяти становилась настолько важной для скорости выполнения.