一、基本冒泡排序原始算法

void sort() { const int length = 5; //定义数组长度 int num[length] = {5, 4, 6, 3, 1}; //定义原始待排序数组 for (int i = 0; i < length - 1; i++) //控制趟数 for (int j = 0; j < length - 1 - i; j++) //控制每趟比较的次数 { if (num[j] < num[j + 1]) { //采用异或位运算交换两个数的值 num[j] = num[j] ^ num[j + 1]; num[j + 1] = num[j] ^ num[j + 1]; num[j] = num[j] ^ num[j + 1]; } } }

过程说明：

第1趟：在第1趟中共进行 $length-1-0$ 次比较，从第0个位置的元素开始判断与其相邻的后一个元素是否满足$if$条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中数值最小（或者最大）的元素已经沉底。

本趟排序前：5，4，6，3，1 本趟排序后：5，6，4，3，1

第2趟：在第2趟中共进行 $length-1-1$ 次比较，从第0个位置的元素开始判断（每趟都从第0个元素开始判断）与其相邻的后一个元素是否满足$if$条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中数值最小和次小（或者最大和次大）的元素已经有序排列到末尾。

本趟排序前：5，6，4，3，1 本趟排序后：6，5，4，3，1

第3趟：在第3趟中共进行 $length-1-2$ 次比较，从第0个位置的元素开始判断与其相邻的后一个元素是否满足$if$条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中值较小的前3位元素（或者值较大的前3位元素）已经有序排列到末尾。

本趟排序前：6，5，4，3，1 本趟排序后：6，5，4，3，1

第4趟：在第4趟中共进行 $length-1-3$ 次比较，从第0个位置的元素开始判断与其相邻的后一个元素是否满足$if$条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中全部元素已经按照从大到小（或者值从小到大）的顺序有序排列，至此，排序结束。

本趟排序前：6，5，4，3，1 本趟排序后：6，5，4，3，1

性能分析：

时间复杂度：$$\frac{n(n-1)}{2}=O(n^2)$$在上述排序中共进行了 $4+3+2+1$ 共 $10$ 次比较，而实际上在第2趟的第1次比较结束后，该序列已经是一个有序序列，因此实际有效的比较次数为 $4+1$ 共 $5$ 次比较，其余的 $5$ 次比较属于无效比较，但却耗费了一定的时间，因此该算法有待改进。

 

 

二、基本冒泡排序算法第一次改进

通过分析可知，如果上一趟比较中没有发生交换，那么此时整个序列已经有序，后续的比较都属于无效比较，可以省略。

void sortPro1() { const int length = 5; //定义数组长度 int num[length] = {5, 4, 6, 3, 1}; //定义原始待排序数组 bool exchange = true; //记录在上一趟比较中是否发生了交换 for (int i = 0; i < length - 1; i++) //控制趟数 { if (exchange) { //如果上一趟中发生了交换，则需要执行下一趟 exchange = false; //进入某趟后，修改记录为为false for (int j = 0; j < length - 1 - i; j++) { //控制每趟比较的次数 if (num[j] < num[j + 1]) { //采用异或位运算交换两个数的值 num[j] = num[j] ^ num[j + 1]; num[j + 1] = num[j] ^ num[j + 1]; num[j] = num[j] ^ num[j + 1]; exchange = true; //记录本趟中发生了交换 } } } else //如果在上一趟比较中未发生交换，则排序结束，直接结束循环 break; } }

过程说明：

第1趟：因为初始化 $exchange=true$ ，因此第1趟比较是必要的，在第1趟中共进行 $length-1-0$ 次比较，从第0个位置的元素开始判断与其相邻的后一个元素是否满足$if$条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中数值最小（或者最大）的元素已经沉底。

本趟排序前：5，4，6，3，1 本趟排序后：5，6，4，3，1

第2趟：因为在第1趟比较中发生了交换，所以 $exchange=true$ 依然成立，因此需要进行第2趟比较。在第2趟中共进行 $length-1-1$ 次比较，从第0个位置的元素开始判断（每趟都从第0个元素开始判断）与其相邻的后一个元素是否满足$if$条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中数值最小和次小（或者最大和次大）的元素已经有序排列到末尾。

本趟排序前：5，6，4，3，1 本趟排序后：6，5，4，3，1

第3趟：因为在第2趟比较中发生了交换，所以 $exchange=true$ 依然成立，因此还需要进行第3趟比较。在第3趟中共进行 $length-1-2$ 次比较，从第0个位置的元素开始判断与其相邻的后一个元素是否满足$if$条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中值较小的前3位元素（或者值较大的前3位元素）已经有序排列到末尾。同时，因为本趟中未发生交换，所以 $exchange=false$ 成立，此时不在进行下一趟排序，直接结束循环，至此，排序结束。

本趟排序前：6，5，4，3，1 本趟排序后：6，5，4，3，1

性能分析：

最坏时间复杂度：$$\frac{n(n-1)}{2}=O(n^2)$$虽然最坏时间复杂度依然是 $O(n^2)$ ，但实际上在上述排序中共进行了 3趟比较，比改进前少1趟，执行了$4+3+2$ 共 $9$ 次比较，而实际有效的比较次数为 $4+1$ 共 $5$ 次，其余的 $4$ 次比较仍然属于无效比较，因此该算法依然有待改进。

 

 

三、基本冒泡排序算法第二次改进

通过分析可知，在每一趟比较之后，如果在该趟里从某个位置开始不再进行交换，则表明该位置之后的序列已经有序，后续其他趟的比较中无需再度遍历。

void sortPro2() { const int length = 5; //定义数组长度 int num[length] = {5, 4, 6, 3, 1}; //定义原始待排序数组 int nextPosition = length - 1; //记录下次比较时无序序列的截至位置 while (nextPosition != 0) { int position = 0; //记录本趟中发生交换的最后位置 for (int i = 0; i < nextPosition; i++) { if (num[i] < num[i + 1]) { //采用异或位运算实现两个数的交换 num[i] = num[i] ^ num[i + 1]; num[i + 1] = num[i] ^ num[i + 1]; num[i] = num[i] ^ num[i + 1]; position = i; } } //将本趟中发生交换的最后位置作为下次比较时无序序列的截至位置 nextPosition = position; } }

过程说明：

第1趟：此时无序序列的截至位置是 $nextPosition=length-1$，在第1趟中共进行 $nextPosition+1$ 次比较，从第0个位置的元素开始判断与其相邻的后一个元素是否满足$if$条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中数值最小（或者最大）的元素已经沉底。同时 $position$ 记录了本趟中发生交换的最后位置为1。

本趟排序前：5，4，6，3，1 本趟排序后：5，6，4，3，1

第2趟：$nextPosition$ 记录了本次比较时无序序列的截至位置为1，在第2趟中共进行 $nextPosition+1$ 次比较，从第0个位置的元素开始判断（每趟都从第0个元素开始判断）与其相邻的后一个元素是否满足$if$条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则此时序列已经有序，至此，排序结束。

本趟排序前：5，6，4，3，1 本趟排序后：6，5，4，3，1

性能分析：

最坏时间复杂度：$$\frac{n(n-1)}{2}=O(n^2)$$最坏时间复杂度依然是 $O(n^2)$ ，事实上，无论怎么改进，冒泡排序算法最坏的时间复杂度一直都会是 $O(n^2)$ ，在上述排序中共进行了 2趟比较，比该进前少2趟，比第一次改进少1趟，实际执行了$4+2$ 共 $6$ 次比较，实际有效的比较次数为 $4+1$ 共 $5$ 次，只有 $1$ 次属于无效比较，相比以上两种算法，执行时间大大减少。

 

 

四、总结

第一次改进实际上是对遍历的趟数做了精简第二次改进实际上是对每趟中比较的次数做了精简上述测试数据不具有普遍性，不足以证明第二次改进的算法在任何情况下都优于第一次改进。事实上，改进的两种算法的性能会受到不同数据序列原始排布的影响，各有优劣，具体情况暂不做分析，后续会持续更新总体上看，相较于原始冒泡排序算法，这两种改进都带来了较大的性能提高，这一点是可以肯定的！