如果有人能对我的逻辑给出一些意见，我会非常感激 .
对于所有键相同，选择排序或插入排序的数组，哪种方法运行得更快？
我认为这与数组已经排序时类似，因此插入排序将是线性的，选择排序是二次的 .
对于数组，哪种方法以相反的顺序，选择排序或插入排序运行得更快？
我认为它们的运行方式类似，因为每个位置的值都必须改变 . 插入排序的最坏情况是逆序，因此这意味着它是二次的，然后选择排序也已经是二次的 .
假设我们在随机排序的数组上使用插入排序，其中元素只有三个值中的一个 . 运行时间是线性的，二次的还是介于两者之间的？
由于它是随机排序的，我认为这意味着插入排序必须执行多少次操作数量的值 . 如果是这种情况，则它不是线性的 . 因此，它可能是二次的，或者可能略低于二次方 .
对于长度为N的数组，执行Quick.sort（）期间可以交换最大项目的最大次数是多少？
最大数量不能超过可用空间的次数，因为它应该始终接近正确的位置 . 因此，从第一个值到最后一个值点，它将被交换N次 .
关于quick.sort（）在排序N个项目的数组时会有多少比较？
在绘制快速排序时，可以在每个阶段的比较对象周围绘制一个三角形，即N高和N宽，其面积等于执行的比较数，即（N ^ 2）/ 2
1 回答
以下是我对您的意见的评论：
对，那是正确的 . 插入排序将为每个元素执行O（1）工作，并访问O（n）元素以获得O（n）的总运行时间 . 无论输入结构如何，选择排序始终在时间Θ（n2）中运行，因此其运行时间将是二次的 .
你是对的，两种算法都有二次运行时 . 算法实际上应具有相对可比的性能，因为它们将进行相同的比较总数 .
这应该采用二次时间（时间Θ（n2）） . 只取数组后三分之一的元素 . 这些元素中约有三分之一将需要移动到阵列下方的2/3以上 . 因此，完成的工作将至少为（n / 3）（2n / 3）= 2n2 / 9，这是二次的 .
这里有一个off-by-one错误 . 当数组的大小为1时，最大的元素不能再移动，因此最大移动次数为N-1 .
这实际上取决于
Quick.sort()的实施 . 具有三元分区的Quicksort将仅执行O（n）总工作，因为在递归调用中排除了等于枢轴的所有值 . 如果没有这样做，那么你的分析是正确的 .希望这可以帮助！