java - 排序——是否可以很好地使用子数组进行排序？

Question

我遇到了一个看起来不错的数组排序算法，但是它使用子数组递归。我听说制作子数组的时间复杂度是 O(n)，这或多或少会阻止任何有效排序使用子数组。

算法:

采取一个支点。为了演示的目的，我们每次都将其称为数组中的最后一个数字。
将枢轴放在正确的位置。在这里，你会看2和6，如果6比较大，就放在2之后。然后看1和2，如果比较小，就放在左边。如果两个数相等，我选择把轴放在左边。
获取枢轴左侧和右侧的子数组并在这些子数组上重复。
当子数组大小为一时停止。

一个有效的例子:

 6 1 7 8 6 9 1 2        Pivot would be 2
 1 1 2 6 6 7 8 9        Put 2 in it's place, time to take sub-arrays
[1 1] 2 [6 7 8 9]       Recur.
 1 1  2 [6 7 8] 9       Recur more. 
 1 1 2  [6 7] 8 9       Recur.
 1 1 2  6 7 8 9         Done!

时间复杂度是多少？此外，如果采用子数组只需要 O(1) 时间，我很想知道时间复杂度。

我认为这个算法的最坏情况是 O(n^2)，但平均情况是多少？

另外请不要链接更好的排序，我正在尝试自己找出一个好的排序。

Answer 1

您已经描述了 Quick Sort算法，其平均时间复杂度为 O(n log n)，最坏情况时间复杂度为 O(n^2)(奇怪的是，当数组已经排序时) .