一、基本冒泡排序原始算法
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趟中共进行
le
n
g
t
h
−
1
−
0
length-1-0
l
e
n
g
t
h
−
1
−
0
次比较，从第0个位置的元素开始判断与其相邻的后一个元素是否满足
if
if
i
f
条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中数值最小（或者最大）的元素已经沉底。本趟排序前：5，4，6，3，1
本趟排序后：5，6，4，3，1 -
第2趟：在第2趟中共进行
le
n
g
t
h
−
1
−
1
length-1-1
l
e
n
g
t
h
−
1
−
1
次比较，从第0个位置的元素开始判断（每趟都从第0个元素开始判断）与其相邻的后一个元素是否满足
if
if
i
f
条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中数值最小和次小（或者最大和次大）的元素已经有序排列到末尾。本趟排序前：5，6，4，3，1
本趟排序后：6，5，4，3，1 -
第3趟：在第3趟中共进行
le
n
g
t
h
−
1
−
2
length-1-2
l
e
n
g
t
h
−
1
−
2
次比较，从第0个位置的元素开始判断与其相邻的后一个元素是否满足
if
if
i
f
条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中值较小的前3位元素（或者值较大的前3位元素）已经有序排列到末尾。本趟排序前：6，5，4，3，1
本趟排序后：6，5，4，3，1 -
第4趟：在第4趟中共进行
le
n
g
t
h
−
1
−
3
length-1-3
l
e
n
g
t
h
−
1
−
3
次比较，从第0个位置的元素开始判断与其相邻的后一个元素是否满足
if
if
i
f
条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中全部元素已经按照从大到小（或者值从小到大）的顺序有序排列，至此，排序结束。本趟排序前：6，5，4，3，1
本趟排序后：6，5，4，3，1
性能分析：
-
时间复杂度：
n(
n
−
1
)
2
=
O
(
n
2
)
\frac{n(n-1)}{2} = O(n^2)
2
n
(
n
−
1
)
=
O
(
n
2
)
-
在上述排序中共进行了
4+
3
+
2
+
1
4+3+2+1
4
+
3
+
2
+
1
共
1010
1
0
次比较，而实际上在第2趟的第1次比较结束后，该序列已经是一个有序序列，因此实际有效的比较次数为
4+
1
4+1
4
+
1
共
55
5
次比较，其余的
55
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趟：因为初始化
ex
c
h
a
n
g
e
=
t
r
u
e
exchange=true
e
x
c
h
a
n
g
e
=
t
r
u
e
，因此第1趟比较是必要的，在第1趟中共进行
le
n
g
t
h
−
1
−
0
length-1-0
l
e
n
g
t
h
−
1
−
0
次比较，从第0个位置的元素开始判断与其相邻的后一个元素是否满足
if
if
i
f
条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中数值最小（或者最大）的元素已经沉底。本趟排序前：5，4，6，3，1
本趟排序后：5，6，4，3，1 -
第2趟：因为在第1趟比较中发生了交换，所以
ex
c
h
a
n
g
e
=
t
r
u
e
exchange=true
e
x
c
h
a
n
g
e
=
t
r
u
e
依然成立，因此需要进行第2趟比较。在第2趟中共进行
le
n
g
t
h
−
1
−
1
length-1-1
l
e
n
g
t
h
−
1
−
1
次比较，从第0个位置的元素开始判断（每趟都从第0个元素开始判断）与其相邻的后一个元素是否满足
if
if
i
f
条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中数值最小和次小（或者最大和次大）的元素已经有序排列到末尾。本趟排序前：5，6，4，3，1
本趟排序后：6，5，4，3，1 -
第3趟：因为在第2趟比较中发生了交换，所以
ex
c
h
a
n
g
e
=
t
r
u
e
exchange=true
e
x
c
h
a
n
g
e
=
t
r
u
e
依然成立，因此还需要进行第3趟比较。在第3趟中共进行
le
n
g
t
h
−
1
−
2
length-1-2
l
e
n
g
t
h
−
1
−
2
次比较，从第0个位置的元素开始判断与其相邻的后一个元素是否满足
if
if
i
f
条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中值较小的前3位元素（或者值较大的前3位元素）已经有序排列到末尾。同时，因为本趟中未发生交换，所以
ex
c
h
a
n
g
e
=
f
a
l
s
e
exchange=false
e
x
c
h
a
n
g
e
=
f
a
l
s
e
成立，此时不在进行下一趟排序，直接结束循环，至此，排序结束。本趟排序前：6，5，4，3，1
本趟排序后：6，5，4，3，1
性能分析：
-
最坏时间复杂度：
n(
n
−
1
)
2
=
O
(
n
2
)
\frac{n(n-1)}{2} = O(n^2)
2
n
(
n
−
1
)
=
O
(
n
2
)
-
虽然最坏时间复杂度依然是
O(
n
2
)
O(n^2)
O
(
n
2
)
，但实际上在上述排序中共进行了 3趟比较，比改进前少1趟，执行了
4+
3
+
2
4+3+2
4
+
3
+
2
共
99
9
次比较，而实际有效的比较次数为
4+
1
4+1
4
+
1
共
55
5
次，其余的
44
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趟：此时无序序列的截至位置是
ne
x
t
P
o
s
i
t
i
o
n
=
l
e
n
g
t
h
−
1
nextPosition=length-1
n
e
x
t
P
o
s
i
t
i
o
n
=
l
e
n
g
t
h
−
1
，在第1趟中共进行
ne
x
t
P
o
s
i
t
i
o
n
+
1
nextPosition+1
n
e
x
t
P
o
s
i
t
i
o
n
+
1
次比较，从第0个位置的元素开始判断与其相邻的后一个元素是否满足
if
if
i
f
条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则该序列中数值最小（或者最大）的元素已经沉底。同时
po
s
i
t
i
o
n
position
p
o
s
i
t
i
o
n
记录了本趟中发生交换的最后位置为1。本趟排序前：5，4，6，3，1
本趟排序后：5，6，4，3，1 -
第2趟：
ne
x
t
P
o
s
i
t
i
o
n
nextPosition
n
e
x
t
P
o
s
i
t
i
o
n
记录了本次比较时无序序列的截至位置为1，在第2趟中共进行
ne
x
t
P
o
s
i
t
i
o
n
+
1
nextPosition+1
n
e
x
t
P
o
s
i
t
i
o
n
+
1
次比较，从第0个位置的元素开始判断（每趟都从第0个元素开始判断）与其相邻的后一个元素是否满足
if
if
i
f
条件，如果满足则交换两元素的值。依次向后迭代，直到本趟循环次数结束，则此时序列已经有序，至此，排序结束。本趟排序前：5，6，4，3，1
本趟排序后：6，5，4，3，1
性能分析：
-
最坏时间复杂度：
n(
n
−
1
)
2
=
O
(
n
2
)
\frac{n(n-1)}{2} = O(n^2)
2
n
(
n
−
1
)
=
O
(
n
2
)
-
最坏时间复杂度依然是
O(
n
2
)
O(n^2)
O
(
n
2
)
，事实上，无论怎么改进，冒泡排序算法最坏的时间复杂度一直都会是
O(
n
2
)
O(n^2)
O
(
n
2
)
，在上述排序中共进行了 2趟比较，比该进前少2趟，比第一次改进少1趟，实际执行了
4+
2
4+2
4
+
2
共
66
6
次比较，实际有效的比较次数为
4+
1
4+1
4
+
1
共
55
5
次，只有
11
1
次属于无效比较，相比以上两种算法，执行时间大大减少。
四、总结
- 第一次改进实际上是对遍历的趟数做了精简
- 第二次改进实际上是对每趟中比较的次数做了精简
- 上述测试数据不具有普遍性，不足以证明第二次改进的算法在任何情况下都优于第一次改进。事实上，改进的两种算法的性能会受到不同数据序列原始排布的影响，各有优劣，具体情况暂不做分析，后续会持续更新
- 总体上看，相较于原始冒泡排序算法，这两种改进都带来了较大的性能提高，这一点是可以肯定的！
