排序列表上的Python排序复杂度 [英] Python sorting complexity on sorted list

问题描述

Python中sort(already_sorted_list)的复杂性是什么? Python是否检查给定的iterable是否已排序，还是我必须自己做?我在文档的任何地方都找不到它.

What is the sort(already_sorted_list) complexity in Python? Does Python check if given iterable is sorted, or do I have to do it by myself? I could not find it anywhere in the docs.

推荐答案

这完全取决于实现. python保证的是，内置排序算法是 stable (比较相等的元素保留其相对顺序).如果要实现的话，甚至可以使用稳定的冒泡排序.

This is entirely implementation dependent. All that python guarantees is that the builtin sorting algorithm is stable (elements which compare equal retain their relative ordering). An implementation could even use a stable bubble sort if it wanted to ...

Cpython使用 TimSort (插入排序和合并排序的混合体)，如果输入已经排序-它获得插入排序的最佳情况性能和归并排序(O(NlogN))的最坏情况性能.

Cpython uses TimSort (a hybrid of insertion sort an mergesort) which I believe has O(N) complexity if the input is already sorted -- It picks up the best case performance of insertion sort and the worst case performance of mergesort (O(NlogN)).

如果您对实现感到好奇，则源代码包含一个非常好的描述.

And if you're curious about the implementation, the source code has a very nice description.

这篇关于排序列表上的Python排序复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！