Question

直接选择排序算法在最好情况下的时间复杂度为多少

求解

Answer 1

关键字比较次数永远是n(n-1)/2，记录移动次数最多为3(n-1)，最少0次，前者起主导作用，因此实际上时间复杂度还是O(n^2)。

在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行 n-i 次比较 (1<=i<=n-1),而每次交换最多需要3次移动，因此，总的比较次数C=(n*n - n)/2,总的移动次数 3(n-1).由此可知，直接选择排序的时间复杂度为 O(n2) 。

扩展资料：

直接选择排序的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，....，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值。

与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。当记录占用字节数较多时，通常比直接插入排序的执行速度快些。由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。

参考资料来源：百度百科-直接选择排序

Answer 2

关键字比较次数永远是n(n-1)/2
记录移动次数最多为3(n-1)，最少0次
前者起主导作用，因此实际上时间复杂度还是O(n^2)