use*_*951 2 algorithm time-complexity selection-sort
当插入排序和冒泡排序为O(n)时,为什么选择排序O(n ^ 2)的最佳情况时间复杂度？他们的平均时间是一样的.我不明白为什么最好的案例时间是不同的.会感激一些帮助.
对于选择排序,您必须搜索最小值并将其放在第一次迭代中的第一个位置.在第二次迭代中,您必须在数组的未排序部分中搜索最小值并将其放在第二位,依此类推......
您只知道在迭代之后哪个元素是最小的,直到未排序的部分结束.即使数组已排序(!),您也必须迭代直到结束.然后你肯定知道你找到了把它放在正确位置的最小值(在已经排序的部分的末尾)
因此,第一次迭代需要n步才能找到最小值.第二次迭代需要n-1步才能找到未排序部分中的最小值...最后一次迭代需要1步才能找到未排序部分中的最小值.
在这些步骤之后,您有一个已排序的数组(即使之前已经排序).选择排序不会检查数组是否已按线性时间算法排序.选择排序重复搜索最小值.这就是选择排序的工作方式.
当您重复搜索最小值时,它需要n +(n-1)+ ... + 1,因此得到(n(n + 1))/ 2 =(n²+ n)/ 2,其中为O(n²)