Question

冒泡排序问题。

我就不懂了，冒泡排序无论排序序列正序还是什么，都要进行n-1趟排序，因为都要双层循环的比较（虽然不真正移动数据），在最好的情况下，时间复杂度怎么回事O(n)

Answer 1

冒泡排序是一种用时间换空间的排序方法，最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序。在这种情况下，每一次比较都需要进行交换运算。举个例子来说，一个数列 5 4 3 2 1 进行冒泡升序排列，第一次大循环从第一个数（5）开始到倒数第二个数（2）结束，比较过程：先比较5和4，4比5小，交换位置变成4 5 3 2 1；比较5和3，3比5小，交换位置变成4 3 5 2 1……最后比较5和1，1比5小，交换位置变成4 3 2 1 5。这时候共进行了4次比较交换运算，最后1个数变成了数列最大数。
第二次大循环从第一个数（4）开始到倒数第三个数（2）结束。进行3次比较交换运算。
……
所以总的比较次数为 4 + 3 + 2 + 1 = 10次
对于n位的数列则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2，这就得到了最大的比较次数
而O(N^2)表示的是复杂度的数量级。举个例子来说，如果n = 10000，那么 n(n-1)/2 = (n^2 - n) / 2 = (100000000 - 10000) / 2，相对10^8来说，10000小的可以忽略不计了，所以总计算次数约为0.5 * N^2。用O(N^2)就表示了其数量级（忽略前面系数0.5）。

追问

我的题目是在正序的情况下为什么是O(n)，你答的我都知道

追答

1）算法的最好时间复杂度
　若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：
Cmin=n-1
Mmin=0。
　冒泡排序最好的时间复杂度为O(n)。
正序的情况下你还是要把每一个数扫描一遍啊，只不过不动它们的顺序，但是你还是扫描了，所以就是o（n），你看对不对

追问

既然还是要执行双层循环的比较不应当是O(n^2)吗

追答

但是你没有移动啊，这就相当于就一层比较的循环，而没有那个移动的循环

Answer 2

持续每次对越来越少的元素重复比较与交换，直到没有任何一对数字需要比较。什么是冒泡排序？视频演示冒泡排序的原理，人人都能看懂冒泡排序。

Answer 3

内层循环一遍程序直接结束了，外层只循环了一次

Answer 4

这个好理解，不如在第一次内循环就发现没有进行一次交换，那就说明已经排好了，就不用进行第二次了，那就是最好的情况了O（n），程序放一个flage标记就好了。

Answer 5

我们可以把冒泡进行一下优化，考虑以下特殊情况，若原数据已经有序，计算机此时并不知道已经排好序。所以，还需进行比较，如果没有发生任何数据交换，则知道已经排好序，可以不干了。因此第2趟比较还需进行，第3趟、第5趟比较则不必要。 我们设置一个布尔变量bo 来记录是否有进行交换。值为false表示本趟中进行了交换，true 则没有。代码如下: i:=1; repeat bo:=true; for j:=1 to n-i do if a[j]<a[j+1] then begin temp:=a[j]; a[j]:=a[j+1]; a[j+1]:=temp; bo:=false; end; 　inc(i); until bo; 这样他的复杂度就变成了O（n）了！看看，打了这么多了，给个满意答案吧！！！