Question

冒泡排序

Answer 1

冒泡排序的原理是：从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。

冒泡排序：有两种，一种是小泡向上冒，一种是大泡向下沉。

首先，设待排序长为n，从后往前（从前向后）两两比较相邻元素的值，若为逆序， (a[i-1]>a[i])，则交换他们，直到序列比较结束。

交换过程中，会将较大的元素一直向后移动，故，会将最大的元素移动到最终的位置上，这样就称为一次冒泡过程。

为啥是n-1呢？因为排到最后，只剩两个数了，我们只需要比较一次，即可得到这两个数的有序序列。

9个数第一次需要比较8次，因为当只有两个数的时候，比较一次即可排出顺序。且每次比较都会少比较一次，因为每次比较都会使得一个数归位。所以一共比较8+7+6+5+4+3+2+1次。
冒泡排序是死的次数，最坏最好的情况冒泡排序都会进行相邻的比较。区别在于最好的情况每次比较不交换元素，最坏的情况每次都会交换相邻元素而已。

通过设计flag来减少冒泡的次数。