考虑了很久,越考虑越糊涂,看完下面的解答就更糊涂了,说一下我自己的看法吧。不一定正确。
A.插入排序是一定可以排除的,因为在插入排序的内循环多了一个判断条件是arr[j] > arr[j+1]
也就是最好情况是一个数组已经有序,这时候一直不会进入内循环执行,时间复杂度是O(N)
最坏情况是数组是逆序,每插入一个元素都要去审查前N-1个元素,时间复杂度是O(N^2)
所以插入排序的时间复杂度是与初始序列有关的。
B D冒泡和直接选择排序,我一开始觉得这俩都是与初始序列无关的,选择排序是每一次一个元素与剩余无序的所有元素比较,将最小值赋值给这个元素,不管初始序列如何,都会进到内循环去做比较,所以直接选择排序是与初始序列无关的。
同理来说,冒泡排序也一样,不过看到大家在说优化版的冒泡排序是与初始序列有关的,即在循环内增加一个标志位:
function bubbleSort(arr) {
let length = arr.length;
let flag = 0;
for (let i = 0; i < length; i++) {
flag = 0;
for (let j = 0; j < length - i; j++) {
if (arr[j] > arr[j+1]) {
flag = 1;
swap(arr, j, j+1)
}
}
if (flag === 0) { //优化,如果一次都没发生交换,说明数组已经是有序的,直接提前结束循环
break;
}
console.log(arr)
}
}
这样也确实与初始序列有关,如果是一个已经排好序的数组,那么刚进入循环就结束了,所以时间复杂度是O(1),不过这个题并没有说是不是优化版的冒泡,所以我认为冒泡的时间复杂度还是与初始序列无关的。
C 快速排序 快排的性能取决于基准关键字的选取,如果选取的关键字刚好可以将当前无序区划分成左右区域大致相等,则可以得到最好的时间复杂度:O(N*logN),如果选取的关键字是当前无序区的最小值或者最大值,则会得到最差的时间复杂度:O(N^2),所以在快排中选择基准是非常重要的一步,最好的方式是随机选取,这样就可以避免出现最坏的情况,即每一种划分方式出现的概率都相等,所以也就不存在运气问题了。
所以结论就是随机快排是与初始序列无关的。
最后,分析了半天,居然分析出三个与初始序列无关的排序方式,好崩溃,哪位大神觉得我哪里思路不对还望多指教。
显然答案是D
1.直接插入排序
2.冒泡排序
3.快速排序
4.直接选择排序