判断下列说法是否正确：对n个关键字进行排序，简单选择排序在最

[单选题]

判断下列说法是否正确：对n个关键字进行排序，简单选择排序在最好情况下的时间复杂度是O(n)。

```
正确
```
```
错误
```

查看答案及解析

推荐

白驹之过隙

选B。考察的是简单选择排序的原理。

简单选择排序原理：在待排序数组中选出最小的(或最大)的与第一个位置的数据交换然后在剩下的待排序数组中找出最小(或最大)的与第二个位置的数据交换，以此类推，直到第n-1个元素

最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。第一次内循环比较N - 1次，然后是N-2次，N-3次，……，最后一次内循环比较1次。(N - 1) + (N - 2) + ... + 1，求等差数列和，得 (N - 1 + 1)* N / 2 = N^2 / 2。舍去最高项系数，其时间复杂度为 O(N²)。

编辑于 2019-10-29 14:45:43 回复(2)

鸣蜩铃兰香

发表于 2022-02-25 15:00:24 回复(0)

求中个奖——狗头

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。

直接选择排序的时间复杂度是固定的O(n^2)

发表于 2019-10-29 11:58:48 回复(1)

小苏大哥

答案选择B 错误，直接选择排序代码为：

void SelectSort(int a[],int n)
{
	int i,j,min;
	for (i = 0; i < n-1;++i)
    {
        for (j = i + 1; j < n; ++j)
        {
            min = i;
            if (a[min] > a[j])
            {
                swap(&a[min], &a[j]);
            }
        }
    }

}

从代码可以知道：直接选择排序的时间复杂度是固定的O(n^2)

发表于 2019-10-28 15:55:24 回复(0)