稳定选择排序算法的时间复杂度是多少

Question

static void stableSelectionSort(int[] a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
if (a[min] > a[j])
min = j;
// Move minimum element at current i.
int key = a[min];
while (min > i)
{
a[min] = a[min - 1];
min--;
}

a[i] = key;
}
}

稳定选择排序算法的时间复杂度是多少？它会和选择排序一样吗？

Answer 1

所以外循环运行n-1次。从i到n的第一个内环，也就是说，它第一次运行n-1次，然后n-2，然后n-3。。。1.现在对于第二个循环，假设所有元素都相同，那么每次循环都会从i运行到0，加上第一个和第二个，内部循环将运行n次，因此最糟糕的时间复杂度将达到n^2