在下列排序算法中,哪一个算法的时间复杂度与初始序列无关（）_

显然答案是D

1.直接插入排序

需要和前面都有序序列对比插入的位置，如果本身有序，则每次对比一个即可。

最坏情况，则需要一直对比到第一个元素

最好时间复杂度O(n),最坏时间复杂度O(n^2)

2.冒泡排序

假设递增冒泡，需要每次把无序部分最大的移动到无序部分的最右边，如果本身就是递增，则无序移动，遍历一遍就完成了。

最好时间复杂度为O(n),最坏时间复杂度为O(n^2);

3.快速排序

大家都知道，最差为O(n^2)，平均为O(nlogn)

4.直接选择排序

每次需要遍历一遍选择无序部分最大的，无论是否有序，都要遍历才能找到，所以其时间复杂度与初始序列无关。

编辑于 2019-05-07 14:09:25 回复(0)

牛客7983023号

选B D

B :冒泡排序，比较次数始终为n(n-1)/2，交换次数不同 0 或者 3n(n-1)/2，时间复杂度不变

D 选择排序：比较次数始终为 n(n-1)/2，交换次数不同 0 或者 3(n-1)，时间复杂度不变

发表于 2017-11-12 02:18:42 回复(0)

元崽

B冒泡

发表于 2017-11-11 14:30:45 回复(0)

白驹之过隙

选D。

A选项，直接插入排序是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。最好情况下,排序前对象已经按照要求的有序。比较次数n−1 ; 移动次数0。则对应的时间复杂度为O(n)。最坏情况下,排序前对象为要求的顺序的反序。第i趟时第i个对象必须与前面i个对象都做排序码比较,并且每做1次比较就要做1次数据移动，移动次数和比较次数为n²/2，时间复杂度为O(n²)。所以和初始序列有关。
B选项，冒泡排序是对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。数据正序，只需要走一趟即可完成排序。所需的比较次数n-1和记录移动次数均达到最小值0，所以，冒泡排序最好的时间复杂度为O(n)。如果数据是反序的，则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值,最坏的时间复杂度为O(n2)_。所以和初始序列有关。
C选项，快速排序是选择一个元素，将比它小的放在它的左边，比它大的放右边，递归完所有未完成排序的数组即可完成最后的目标。当分区选取的基准元素为待排序元素中的最大或最小值时，为最坏的情况O(n²)，当分区选取的基准元素为待排序元素中的"中值"，为最好的情况，时间复杂度为O(nlog₂n)。
D选项，直接选择排序是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。因为选出待排序数组的最大值或最小值需要扫描全部的元素所以和元素初始序列无关。

发表于 2019-05-05 21:24:13 回复(0)

小白同学

考虑了很久，越考虑越糊涂，看完下面的解答就更糊涂了，说一下我自己的看法吧。不一定正确。
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)，所以在快排中选择基准是非常重要的一步，最好的方式是随机选取，这样就可以避免出现最坏的情况，即每一种划分方式出现的概率都相等，所以也就不存在运气问题了。
所以结论就是随机快排是与初始序列无关的。

最后，分析了半天，居然分析出三个与初始序列无关的排序方式，好崩溃，哪位大神觉得我哪里思路不对还望多指教。

发表于 2017-11-16 12:25:43 回复(1)