first publish:August 8, 2019 -Thursday
冒泡排序是常见的一个排序法，经过一轮轮相邻两两比较，每次将当前轮的最大值排到排序队伍的最后面，最后实现数据完全排序。冒牌排序的复杂度是O(N^2)，那冒泡排序比较了多少次呢？是不是N^2呢？其实不是。
冒泡排序的PHP实现如下示例： a.php：
#待排序数组
$a = array(10,5,3,98,45,23,66,111,12,8,19,30);
#排序方法order
function order($a)
{
#对排序中的比较次数进行统计
$k = 0;
echo count($a),":all numbers.\n";
for($i=0; $i <count($a)-1; $i++)
{
for($j=0; $j< count($a) - $i -1; $j++)
{
$k++;
if($a[$j] > $a[$j+1])
{
$temp = $a[$j];
$a[$j]= $a[$j+1];
$a[$j+1]=$temp;
}
}
}
echo "$k --\n";
return $a;
}
print(order($a));冒泡排序的python实现代码如下示例： a.py
#!/usr/bin/python
a=[10,5,3,98,45,23,66,111,12,8,19,30]
def sort(a):
num=0
for i in range(0, len(a)):
for j in range(0, len(a) - i -1):
num+=1
if(a[j] >a[j+1]):
temp = a[j]
a[j]=a[j+1]
a[j+1]=temp
print num
return a
print a
print sort(a)我写了另一种带有选择排序思想的类冒泡排序：冒泡排序每次比较的是相邻的元素，这个排序每次将第一个位置的元素和其它位置的元素相互比较，实现每次第一个位置都是最小的值，从而实现整个数据实现从小到大排列。
$a = array(10,5,3,98,45,23,66,111,12,8,19,30);
for($i=0; $i<count($a); $i++)
{
for($j=$i+1; $j<count($a); $j++)
{
if($a[$j] < $a[$i])
{
$temp = $a[$i];
$a[$i]= $a[$j];
$a[$j]= $temp;
}
}
}
print_r($a);执行结果12个数据的数据，比较次数$k的值为66，怎么来的，也很好理解，设总比较数据个数为N，第一次比较N-1次，第二次为N-2次，以此类推，为一个从1到N-1的等差数列，根据求和公式公差d=1时：Sn=(a1+an)n/2，代入公式计算得N*(N-1)/2，所以12个数据需要比较66次。可以比较次数最多就是N*(N-1)/2，为什么其复杂度是O(N^2)呢？其实O(N^2)表示的只是复杂度的数量级，在N极大时，其公司基本可以认为=0.5 * N^2。忽略前面系数0.5，从而用O(N^2)就表示其复杂度的数量级而已。
这就是我们接触的冒泡排序方法了，那这个冒泡排序还有没有优化的可能呢？还是有的！如果给一个已经排好的数组给上面这些方法，你会发现它还是会进行各次比较，合计66次。所以这就不够优化了，可以想你在冒泡排序中如果在每一轮的比较中，如果从最前面两次到最后面两个数据的比较中都没有发生数据交换，说明什么呢？说明整个数据已经进入了一个有序状态，此时其实可以不用再排序，直接退出计算，从而减少排序次数实现优化，Python实现如下：
#!/usr/bin/python
a=[10,5,3,98,45,23,66,111,12,8,19,30]
def sort(a):
num=0
for i in range(0, len(a)-1):
flag=False
for j in range(0, len(a) - i -1):
num+=1
if(a[j] >a[j+1]):
temp = a[j]
a[j]=a[j+1]
a[j+1]=temp
flag=True
if not flag:
break
print num
return a
print a
print sort(a)此次数据排序比较次数就比之前的66次要少，说明什么？说明提前三轮判断出了数据已经进入了有序排列，提前结束了排序计算，从而减少比较次数。数据有序性越强，比较次数越少。最佳情况下就是一个带有N个数据的有序数组进行排序，比较次数即是第一轮N-1次。
#对上述数据进行排序，只比较60次，而原来需要比较66次。 [hello@04007 ~]# python a.py [10, 5, 3, 98, 45, 23, 66, 111, 12, 8, 19, 30] 60 [3, 5, 8, 10, 12, 19, 23, 30, 45, 66, 98, 111] #对已经排好序的数据数组进行排序，只需比较N-1次即可。 [hello@04007 ~]# python a.py [3, 5, 8, 10, 12, 19, 23, 30, 45, 66, 98, 111] 11 [3, 5, 8, 10, 12, 19, 23, 30, 45, 66, 98, 111]
