2011-02-17

主要排序算法的比较(精炼)

Views: 11296 | Add Comments

来自: Wikipedia

Heapsort primarily competes with quicksort, another very efficient general purpose nearly-in-place comparison-based sort algorithm.

Quicksort is typically somewhat faster, due to better cache behavior and other factors, but the worst-case running time for quicksort is O(n2), which is unacceptable for large data sets and can be deliberately triggered given enough knowledge of the implementation, creating a security risk. See quicksort for a detailed discussion of this problem, and possible solutions.

Thus, because of the O(n log n) upper bound on heapsort's running time and constant upper bound on its auxiliary storage, embedded systems with real-time constraints or systems concerned with security often use heapsort.

Heapsort also competes with merge sort, which has the same time bounds, but requires Ω(n) auxiliary space, whereas heapsort requires only a constant amount. Heapsort also typically runs more quickly in practice on machines with small or slow data caches. On the other hand, merge sort has several advantages over heapsort:

  • Like quicksort, merge sort on arrays has considerably better data cache performance, often outperforming heapsort on a modern desktop PC, because it accesses the elements in order.
  • Merge sort is a stable sort.
  • Merge sort parallelizes better; the most trivial way of parallelizing merge sort achieves close to linear speedup, while there is no obvious way to parallelize heapsort at all.
  • Merge sort can be easily adapted to operate on linked lists (with O(1) extra space[7]) and very large lists stored on slow-to-access media such as disk storage or network attached storage. Heapsort relies strongly on random access, and its poor locality of reference makes it very slow on media with long access times. (Note: Heapsort can also be applied to doubly linked lists with only O(1) extra space overhead)

Introsort is an interesting alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.

Related posts:

  1. 用TAB缩进, 用SPACE对齐
  2. 不用 git rebase 合并 commit 历史
  3. C#环形缓冲
  4. SSH 信任限制只能执行 rsync 命令
  5. 写自己的 http_build_query
Posted by ideawu at 2011-02-17 16:57:21

Leave a Comment