数据结构各种排序比较

排序是计算机科学中最重要的程序设计算法之一。经典排序算法有插入排序、希尔排序、选择排序和交换排序等。近年来，人们又提出了快速排序、堆排序、归并排序和计数排序等新算法。

1. 时间复杂度

不同的排序算法需要不同的时间复杂度，即排序所需的时间与数据量的关系。按时间复杂度从小到大排列，快排、堆排、归并排、基数排、计数排、希尔排和冒泡排序等是常用排序方法。

2. 空间复杂度

排序算法的空间复杂度也是十分重要的，即排序所需的内存空间与数据量的关系。常用排序方法的空间复杂度从小到大排列为选择排序、插入排序、冒泡排序和快速排序等。

3. 算法稳定性

在排序过程中，如果值相同的元素在排序后相对位置仍保持不变，那么就是稳定排序算法。比如插入排序、冒泡排序和归并排序等都是稳定算法。而快排则不是，可能改变相同元素的相对位置。

4. 排序方式

按影响排序方式的因素来分类，可分为内部排序和外部排序。内部排序是指数据记录在内存中进行排序，外部排序则是针对大规模数据的排序，在磁盘中进行排序。内部排序方法有选择排序、快速排序和堆排序等，而外部排序在磁盘中进行排序，例如归并排序、置换-选择排序和多路平衡归并排序等。

除了经典的排序算法，计算机科学家们还在研究新的排序算法。例如，在电子元器件中使用的快速排序被重构为“flashsort”，可以在近乎线性的时间内完成排序。在大规模的分布式计算中，MapReduce 框架的布隆过滤器、哈希分割、快排求中位数等排序算法也被广泛应用。