分类： C/C++
2015-09-05 23:23:00
原始待排序数组| 8 | 3 | 4 | 7 | 1 | 9 |
===================================================================
-------------------------------------------------------------------
第一趟排序(外循环1次，内循环5次） 外循环 for(i=0,i<6;i++)
第一次两两比较，8 > 3交换(内循环) j=0
交换前状态| 8 | 3 | 4 | 7 | 1 | 9 |
交换后状态| 3 | 8 | 4 | 7 | 1 | 9 |
第二次两两比较，8 > 4交换 j=1
交换前状态| 3 | 8 | 4 | 7 | 1 | 9 |
交换后状态| 3 | 4 | 8 | 7 | 1 | 9 |
第三次两两比较，8 > 7交换 j=2
交换前状态| 3 | 8 | 4 | 7 | 1 | 9 |
交换后状态| 3 | 4 | 7 | 8 | 1 | 9 |
第四次两两比较，8 > 1交换 j=3
交换前状态| 3 | 4 | 7 | 8 | 1 | 9 |
交换后状态| 3 | 4 | 7 | 1 | 8 | 9 |
第五次两两比较，8 < 9不交换 j=4
交换前状态| 3 | 4 | 7 | 1 | 8 | 9 |
交换后状态| 3 | 4 | 7 | 1 | 8 | 9 |
-------------------------------------------------------------------
第二趟排序(外循环1次，内循环4次)
第一次两两比较3 < 4不交换
交换前状态| 3 | 4 | 7 | 1 | 8 | 9 |
交换后状态| 3 | 4 | 7 | 1 | 8 | 9 |
第二次两两比较,4 < 7不交换
交换前状态| 3 | 4 | 7 | 1 | 8 | 9 |
交换后状态| 3 | 4 | 7 | 1 | 8 | 9 |
第三次两两比较,7 > 1交换
交换前状态| 3 | 4 | 7 | 1 | 8 | 9 |
交换后状态| 3 | 4 | 1 | 7 | 8 | 9 |
第四次两两比较,7 < 8不交换
交换前状态| 3 | 4 | 1 | 7 | 8 | 9 |
交换后状态| 3 | 4 | 1 | 7 | 8 | 9 |
-------------------------------------------------------------------
第三趟排序(外循环1次，内循环3次)
第一次两两比较3 < 4 不交换
交换后状态| 3 | 4 | 1 | 7 | 8 | 9 |
交换后状态| 3 | 4 | 1 | 7 | 8 | 9 |
第二次两两比较, 4 >1 交换
交换后状态| 3 | 4 | 1 | 7 | 8 | 9 |
交换后状态| 3 | 1 | 4 | 7 | 8 | 9 |
第三次两两比较,4 < 7 不交换
交换前状态| 3 | 1 | 4 | 7 | 8 | 9 |
交换后状态| 3 | 1 | 4 | 7 | 8 | 9 |
-------------------------------------------------------------------
第四趟排序(外循环1次，内循环2次)
第一次两两比较3 > 1 交换
交换后状态| 3 | 1 | 4 | 7 | 8 | 9 |
交换后状态| 1 | 3 | 4 | 7 | 8 | 9 |
第二次两两比较, 3 < 4 不交换
交换后状态| 1 | 3 | 4 | 7 | 8 | 9 |
交换后状态| 1 | 3 | 4 | 7 | 8 | 9 |
-------------------------------------------------------------------
第五趟排序(外循环)无交换
====================================================================
排序完毕,输出最终结果| 1 | 3 | 4 | 7 | 8 | 9 |
循环规律： 当有N个数时，外循环总共需要循环N-1次，即第一层循环含义为：需要遍历N-1次数组，才能将数组排好序。
第i次外循环时，内循环需要循环 N-i次，在第二层遍历中，我们只需对未排好序的那些待排位置进行遍历即可，因此，我们第二层循环要解决的问题便是：待排序区域的起始和结尾位置。
即：
===================================================================================
正向的比较：在第i次循环时，a[n-1]，a[n-2]，a[n-3] ,……，a[n-i]已经排好序，a[0]，a[1],……，a[n-i-1] 待排序
---------------------------------------------------------------------------------------------------------------------------------------------------------
void BubbleSortStoB(int A[],int num) // 从数组开始向数组末尾遍历，正向比较
{
int temp=0;
for (int i=0;i<num-1;i++)
{
for (int j=0;j<num-i-1;j++) // 待排的数据为0,1,2,...,n-i-1 ，此处判断条件为j<num-i-1
{
if (A[j]>A[j+1])
{
temp=A[j];
A[j]=A[j+1];
A[j+1]=temp;
}
}
}
===================================================================================
逆向的比较：在第i次循环时，a[0]，a[1],……，a[n-i-1]已经排好序，a[n-1]，a[n-2]，a[n-3] ,……，a[n-i] 待排序
-----------------------------------------------------------------------------------------------------------------------------------------------------
void BubbleSortBtoS(int A[],int num) // 从数组末尾向数组开始遍历，逆向遍历比较
{
int temp=0;
for (int i=0;i<num-1;i++)
{
for (int j=num-1;j>i;j--) // 待排的数据为i,i+1,...num-1 此处判断条件为j>i
{
if (A[j]<A[j-1])
{
temp=A[j];
A[j]=A[j-1];
A[j-1]=temp;
}
}
}
}
============================================
冒泡排序的时间复杂度：
冒泡排序最好的时间复杂度为 
；
；
