下载掌阅APP，畅读海量书库
立即打开
冒泡排序是典型的交换类排序算法之一，按关键字的大小重复扫过待排序的序列，对元素两两比较，交换关键字顺序不正确的项，直至序列中所有元素都不再需要交换时排序完成。排序过程中，关键字小的元素会渐渐“浮”到顶端，关键字大的元素会“沉”到底端，“轻清者上浮而为天，重浊者下凝而为地”
，这正是冒泡排序名称的由来。
冒泡排序的基本思路如下。
（1）将序列分为无序区和有序区两个部分，无序区在前有序区在后，无序区存放尚未处理好的数据，有序区存放已经按关键字排序后的数据；
图2-1 常用排序算法分类
（2）在无序区中，从头至尾按关键字大小比较相邻的两个元素，将较大的元素向后交换，经过本轮排序之后无序区的最大元素就已经选出，将之放到有序区的首部，然后缩小无序区、扩大有序区；
（3）重复执行（2），直至无序区只有一个元素或某轮排序中没有任何交换为止。若某一轮排序过程中，无任何交换则说明数据已经有序，无须再继续进行排序。
从冒泡排序的思路中可以看出，每轮排序只能筛选出一个元素，因此有 N 个元素的序列，需要进行 N -1轮排序，效率还是比较低的。初始时，无序区包括所有待排序元素，有序区为空；排序过程中，每轮排序都会从无序区中选出一个元素放入有序区中，无序区逐渐缩小，有序区逐渐增大。
设待排序的无序序列存放于数组array中，长度为length，给出冒泡排序的伪代码如表2-1所示。
表2-1 冒泡排序的伪代码
假定待排序的数据为｛6， 2 ，7，3，5，2，1｝（加粗用于标示相同关键字的先后顺序），7个元素最多需要进行6趟排序。排序的原则是将无序区较大元素进行交换，将交换后的无序区最大元素置于有序区的头部。
初始时，无序区 r =｛6， 2 ，7，3，5，2，1｝，有序区 d =｛｝。
第一趟排序过程如下。
从无序区第［1］个元素6开始，与第［2］个元素2进行比较，6>2，交换顺序，然后移动到第［2］个位置；
第［2］个元素6与第［3］个元素7比较，6小于7，保持不变，移动到第［3］个位置；
第［3］个元素7与第［4］个元素3比较，交换位置，7移动到第［4］个位置；
第［4］个元素7与第［5］个元素5比较，交换位置，7移动到第［5］个位置；
第［5］个元素7与第［6］个元素2比较，交换位置，7移动到第［6］个位置；
第［6］个元素7与最后一个元素1比较，交换位置，7移动到第［7］个位置。
将无序区最大元素7移入有序区头部后，无序区 r =｛ 2 ，6，3，5，2，1｝，有序区 d =｛7｝。第一趟排序结束，排序结果为［ 2 ，6，3，5，2，1，7］，过程如图2-2（a）的各列所示。
图2-2 冒泡排序的过程
第二趟排序：排序过程与第一趟排序交换规则相同，交换后无序区 r =｛ 2 ，3，5，2，1，6｝，排序处理过程如图2-2（b）所示。将无序区最大元素6移入有序区头部后，无序区 r =｛ 2 ，3，5，2，1｝，有序区 d =｛6，7｝。
第三趟排序：交换后无序区 r =｛ 2 ，3，2，1，5｝，排序处理过程如图2-2（c）所示。将无序区最大元素5移入有序区头部后，无序区 r =｛ 2 ，3，2，1｝，有序区 d =｛5，6，7｝。
第四趟排序：交换后无序区 r =｛ 2 ，2，1，3｝，排序处理过程如图2-2（d）所示。将无序区最大元素3移入有序区头部后，无序区 r =｛ 2 ，2，1｝，有序区 d =｛3，5，6，7｝。
第五趟排序：交换后无序区 r =｛ 2 ，1，2｝，排序处理过程如图2-2（e）所示。将无序区最大元素2移入有序区头部后，无序区 r =｛ 2 ，1｝，有序区 d =｛2，3，5，6，7｝。
第六趟排序：交换后无序区 r =｛1， 2 ｝，排序处理过程如图2-2（f）所示。将无序区最大元素 2 移入有序区头部后，无序区 r =｛1｝，有序区 d =｛ 2 ，2，3，5，6，7｝。
至此，无序区仅余1个元素｛1｝，也成为有序状态。合并两个有序区 r =｛1｝和 d =｛ 2 ，2，3，5，6，7｝，排序结果为｛1， 2 ，2，3，5，6，7｝。
实现冒泡排序主体功能的是bubble_sort（）函数，main（）函数为驱动函数用于测试冒泡排序的效果。bubble_sort（）函数实现对部分序列进行冒泡排序，且为原地排序算法。与全序列冒泡排序相比，部分序列排序的复杂之处在于排序算法中内循环的上下限确定。
bubble_sort（）函数包括有3个参数，data［］为待排序数组，start为排序区间的起始下标，len为待排序区间的长度。例如，对无序序列｛10，1，35，61，89，36，55｝，从第0个位置开始的5个元素进行冒泡排序，结果应该为｛ 1 ， 10 ， 35 ， 61 ， 89 ，36，55｝。
外循环主要用于确定循环的次数， N 个数据需要至多进行 N -1趟排序。因此，当外循环变量i的起始值为start、元素个数为len时，循环变量的终止值为start+len-2，即外循环条件表示为for（i=start;i<start+len-1;i++）。
每趟排序时，内循环从无序区首元素start开始，循环次数为无序区元素个数-1且为递减等差数列。定义一个整型变量k=0，内循环处理完成后执行k++，将k加入到内循环上限的表达式中构成递减等差数列。因为循环内部比较当前元素data［j］与其下一个元素data［j+1］，所以内循环的上限为start+len-k-2，即内循环控制结构可以表述为for（j=start;j<start+len-k-1;j++）。
当某一趟排序过程中未进行任何交换时，说明数据已经全部有序，无须再进行下一趟排序过程。为此，函数中定义标志量flag，每趟循环设置其初值为1，若排序过程中发生交换则置其值为0。
实现代码如下。
测试数据及运行结果如下。
①数据总数及各数据：
7
10 1 35 61 89 36 55
②待排序的起始位置及排序长度：
0 5
③运行结果：
1 10 35 61 89 36 55
