如何创建一个比O(nlogn)时间复杂度更快的原位排序算法

Question

我最近在一次采访中被要求创建一个就地排序算法。接下来是对其进行编码，使其比O(n-logn(更快，讨论每个循环的时间复杂性。

我知道插入排序、冒泡排序、堆排序、快速排序和shell排序都已经到位，但其中哪些可以修改以具有更好的时间复杂性？

Answer 1

基于比较的排序不能比O(nlogn(快。由于你提到的所有算法都是基于比较的，所以没有一个算法的时间复杂度更好。有一些算法，如桶排序和基数排序，可以在某些情况下实现O(n(，即如果输入是均匀分布的。