在文件"局部有序"或文件长度较小的情况下,最佳内部排序的方法

[单选题]

在文件"局部有序"或文件长度较小的情况下,最佳内部排序的方法是()

```
直接插入排序
```
```
冒泡排序
```
```
简单选择排序
```
```
快速排序
```

查看正确选项

酸奶芝士

当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需n-1趟排序，也即时间复杂度仍为O(n^2)。而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为O(n log2n)；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即n-1趟比较的时间复杂度由O(n^2)降至O(n)。

发表于 2019-08-29 10:49:56 回复(0)