Question

八大排序 时间复杂度

Answer 1

直接插入排序：

最好：待排序已经有序， 从前往后走都不用往里面 插入。 时间复杂度为o(n)

最坏：待排序列是逆序，每一次都要移位插入。 时间复杂度o(n^2)

是稳定排序
2：希尔排序：

最好：缩小增量的插入排序，待排序已经有序。时间复杂度o(n）

一般：平均时间复杂度o(n1.3)，最差也是时间复杂度o(n1.3)

不稳定排序
3：冒泡排序：

最好：待排序已经有序。时间复杂度o(n）

最坏：待排序是逆序。时间复杂度o(n^2）

稳定排序
4：快速排序：

最好：待排序无序。时间复杂度o(nlogn)

最坏: 待排序已经有序，基准定义在开始。 时间复杂度为o(n^2)

不稳定排序
5：直接选择排序：

无论好坏:o(n^2)

稳定排序
6：堆排序：

无论好坏：时间复杂度o(nlogn)

不稳定排序
7：归并排序：
稳定排序
8：基数排序：

无论好坏:o(d(n+r)) ，r为基数，d为位数.

稳定排序

Answer 2

大多认为这个是非常复杂，因为这应该有各种的一些排列方法，所以这应该是比较复杂的，应该是要找他。可以同时用。

Answer 3

这个时间排序复杂度的话，确实有很多种啊，那些西方的时间和我们这中国的时间排序度都可能不一样，或许那边是怎样的呢？