几种排序的比较
|
排序算法 |
平均性能 |
最坏性能 |
空间复杂度 |
稳定性 |
|
冒泡排序 |
O(n2) |
O(n2) |
O(1) |
稳定 |
|
选择排序 |
O(n2) |
O(n2) |
O(1) |
不稳定 |
|
插入排序 |
O(n2) |
O(n2) |
O(1) |
稳定 |
|
快速排序 |
O(nLog(n)) |
O(n2) |
O(Log(n)) |
不稳定 |
|
堆排序 |
O(nLog(n)) |
O(nLog(n)) |
O(1) |
不稳定 |
|
归并排序 |
O(nLog(n)) |
O(nLog(n)) |
O(n) |
稳定 |
从实际的性能来看，快速排序是最快的。
我们看到了这些排序的性能最好的平均也就是O(nLog(n))，有没有办法突破呢？比如到O(n)，理论证明这不可能，理论下限就是O(nLog(n))。
不过有特定情况可以提高到O(n)，比如计数排序、基数排序和桶排序。
排序算法没有绝对的优劣，只是不同的场景的合适程度不同。最好是做成可替换的，这就要求我们对外的接口统一，我们可以写一个排序工具类，内部使用这些算法，对外提供统一的服务。
class Collections():
sorter = mergesort.MergeSorter()
def sort(list):
Collections.sorter.sort(list)
我们在类Collections里面定义了一个类变量sorter和一个类方法sort(list)，不是实例级的，所以客户程序不需要创建Collections的实例，而是直接访问即可。类里面把排序算法默认为归并排序。注意sort()里的写法Collections.sorter.sort(list)，直接用的类里面的变量。
客户程序先选择一个算法，传给类，然后调用sort()实现排序。
如：
import mergesort
import quicksort
import collections
if __name__=='__main__':
a=[38, 27, 43, 3, 9, 82, 10]
print("before sort:",a)
#sorter=mergesort.MergeSorter()
sorter=quicksort.QuickSorter()
Collections.sorter=sorter
Collections.sort(a)
print("after sort:",a)
排序算法是外部传进去的，需要的时候可以替换算法，这是一种策略模式。
自然，要这么写程序，就要求排序算法提供同样的接口，sort(list)，统一都是接受一个列表作为参数，统一把排序方法叫做sort()。事实上，我们可以定义这么一个公共的基础类Sorter，然后别的排序算法继承他就可以了。
class Sorter(): #定义基础类
def sort(self,list):
Pass
class MergeSorter(sorter.Sorter): #继承