算法与数据结构学习笔记(3)

1、归并排序(Merge Sort)

  • 时间复杂度:O(N log N)
  • 空间复杂度:O(N)
  • 比较次数比快速排序少,但移动次数比快速排序多

2、希尔排序(Shell Sort)

  • 时间复杂度:O(N log2 N)
  • 空间复杂度:O(1)
  • 选择好的间隔能极大提高性能,目前已知最好的间隔为:1, 4, 10, 23, 57, 132, 301, 701,(2.3hn-1)

3、快速排序(Quick Sort)

  • 时间复杂度:O(N log N)
  • 空间复杂度:O(1)
  • 通常情况下为最快的通用排序算法之一,但某些时候复杂度会提升到O(N2)
  • 预先排序第一个、中间及最后一个元素能减少复杂度为O(N2)的概率

Update 7.17:

4、基数排序(Radix Sort)

  • 时间复杂度:O(N)(?)
  • 空间复杂度:O(N)
  • 速度很快,但是只能排序数值类型

Leave a Reply

Your email address will not be published. Required fields are marked *