排序算法基础篇交换排序之冒泡排序
2016-06-14
定义
冒泡排序算法和快速排序算法同是交换排序算法中的一员，这里我们先介绍冒泡排序。所谓的冒泡排序就是不断遍历需要进行排序的数据，每一次遍历取出两个未排序的数据按照既定规则（取大或者取小）进行比较并且取出符合条件的数据继续和剩余未经过排序的数据进行排序，直至每一个数据都遍历过所有未进行排序的数据为止。也就是说每一次排序都从第一个未进行主动排序的数据开始从剩余还没有进行排序的数据中选出临近的两两比较，选出最大或者最小的数据。
过程
将数组按照从小到大的循序排列，以{31,159,27,190,79}作为原始数组为例进行说明：
第一趟排序（外循环）
第一趟排序的内循环
第一次两两比较，比较31和159，因为31<159，所以不交换两者的位置（因为我们是要把最小的放到最前面，所以出现小于的情况就不必交换）：
交换前：
交换后：
第二次两两比较，把31和27进行比较，因为31>27，所以交换两者的位置
交换前：
交换后：
第三次两两比较，把31和190进行比较，因为31<190，所以不需要交换两者位置
交换前：
交换后：
第四次两两比较，把31和79进行比较，因为31<79，所以不需要交换两者的位置
交换前：
交换后：
第二趟排序（外循环）
第二趟排序的内循环
第一次两两进行比较，把159和31进行两两比较，因为159>31，所以交换两者的位置
交换前：
交换后：
第二次两两进行比较，把159和190尽心比较，因为159<190，所以不需要交换位置
交换前：
交换后：
第三次进行两两比较，把159和79进行比较，因为159>79，所以需要交换两者位置
交换前：
交换后：
第三趟排序（外循环）
第三趟排序的内循环
第一次两两进行比较，把79和190进行比较，因为79<190，所以不需要交换位置
交换前：
交换后：
第二次进行两两比较，把79和159进行比较，因为79<159，所以不需要交换位置
交换前：
交换后：
第四趟排序（外循环）
第四趟排序的内循环
第一次进行两两比较，把190和159进行比较，因为190>159，所以需要交换位置
交换前：
交换后：
排序结果
讲解：
1、每一趟外循环都从尚未经过排序处理的数开始和数组中剩余的数一一进行比较，例如第一趟外循环中的第一次两两比较中，31要和数组中的剩余元素159,27,190和79一一进行比较；
2、若发生交换位置的情况，则让交换位置后放在前面的数字再和剩余的元素进行比较，如31>27，需要交换位置，交换位置后27在前，故需要用27再继续和剩余的元素进行比较直至发生27被交换到后面的情况发生或者该趟外循环交换完毕。
程序实例
代码
声明：由于未知原因，在我的笔记本上进行10个无序数的排序，总是统计不了时间，即使使用Math函数的Round方法也是不能统计到十个数的排序时间，故下面代码是50个数的排序。。
<span style="font-family:KaiTi_GB2312;font-size:24px;">namespace Bubble_Sort
{
class Program
{
static void Main(string[] args)
{
int temp = 0;
int[] bubleSortAry = { 56, 211, 108, 19, 63, 168, 121, 148, 172, 6, 213, 12312, 2323, 342, 345, 4536, 5634634, 32423, 324244, 168, 121, 13, 187, 77, 148, 205, 123123, 12312, 123232, 43434 ,123,343432,786,567,45654,213,43253252,654654,32432,32}; //声明需要进行排序的数组
#region 排序之前的数组
foreach (int item in bubleSortAry ) //遍历未进行排序之前的数组
{
Console.WriteLine(item +"");
}
Console.WriteLine();
#endregion
#region 检测时间开始计时
long timeStart = DateTime.Now.Ticks; //1 ticks=100纳秒=0.1微妙
#endregion
#region 冒泡代码
for (int i = 0; i < bubleSortAry.Length; i++) //外循环
{
#region 将大的数字移到数组的bubleSortAry.Length-1-i
for (int j = 0; j < bubleSortAry.Length-1-i ; j++) //内循环循环，遍历
{
if (bubleSortAry[j ]>bubleSortAry[j+1]) //交换值
{
temp = bubleSortAry[j + 1];
bubleSortAry[j + 1] = bubleSortAry[j];
bubleSortAry[j] = temp;
}
}
#endregion
}
long timeEnd = DateTime.Now.Ticks; //排序计时结束
long timeCount = timeEnd - timeStart; //排序经过的时间
#endregion
#region 输出
Console.WriteLine();
foreach (int item in bubleSortAry ) //遍历输出排序结果
{
Console.Write(item +"///");
}
Console.WriteLine();
Console.WriteLine("排序计时"+timeCount/10+"微秒");
#endregion
Console.ReadKey(true);
}
}
}
</span>效果
动画演示
PS：只是觉得好看，但是没有感觉到哪里体现出了小泡泡上浮的概念。。。。仅供参考娱乐。。。。
感悟
冒泡就先到这里，感觉自己对Bublle Sort还是懵懵懂懂，继续努力吧。另外有两个遗留问题：
1、为什么数组中元素较少时，不能很好的检测排序用时呢？
2、为什么程序第二次排序用时有时会为0？
感谢您的宝贵时间，祝您生活愉快~
—joker