关于冒泡算法的那些事儿

杨利霞

- t( z- H3 x( j. b, |5 ^, P关于冒泡算法的那些事儿排序算法的复杂度

" J2 Q) A2 L" h; r* F
' T' t5 X) W. [/ A
2 S" [3 h: B2 H; O7 W, o4 F关于冒泡算法你了解多少：
. J3 |& b& w. c2 \) Q' C首先我们规定数据如下
# \6 S$ Q/ _2 r: l8 p, @7 H3 J5 8 6 3 9 1 1 7

% u# }8 N4 W7 ~: }- `在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
如果数组是用vector定义的,即：
vector nums;
//或
vector& nums;
，则这样写：
& M# {3 b4 V. q1 P$ eif nums.size() == 0:
9 L. |9 \7 X" b! j0 x7 @# g4 Sreturn false
' `- f$ ~. _- g: G方法二：
( G) R9 C& V/ e" Z8 ?如果数组是这样定义的，即：
int nums[] = {1,2,3};
先算下数组长度：
5 Q* ~' }: C; Inums_length = sizeof(nums)/sizeof(nums[0])
5 _/ U+ W$ B2 p3 E  o* t4 X" \然后判断数组为空：
if nums_length == 0:
return false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

. J  W& P* r+ W7 }0 ^解决了上述问题以后，最原始的冒泡排序如下
# I4 e$ p  j: o% c5 a! P
- B( g, I0 N; m# x: X# h5 }#include <iostream>
#include <string>
7 N/ T* I3 V7 e- ]# G% c9 r& t4 P4 Gusing namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
; z; d3 V+ D! ^# o        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n - 1; j++)
8 B9 ]2 V5 @* \4 R9 o                {
3 v* ]# T4 k, P( F6 r. f                        if (a[j] > a[j + 1])
& q/ a, W$ M; ?& v' Q5 \; r                        {
2 m6 `1 |% y& E& Z                                temp = a[j];
                                a[j] = a[j + 1];
0 J1 J  r( q1 w4 e- i9 \5 ?7 ^) C                                a[j + 1] = temp;
* n" J& d" L# |# i& `' T                        }
- t1 F. {  s" K# i2 [  I                }
: Q8 F2 d# I7 Q8 R3 G        }
        for (i = 0; i < n; i++)
! r5 b$ w9 N, o3 h0 A; ~) v- L! m                cout << a << " ";
}
int main()
{
/ s( y3 r) ^4 h3 A4 o        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
2 v9 g1 I/ \# B+ O( Z1 q        return 0;
7 Y& j% Q, @5 `/ X}

6 r4 T7 Y* x, @- R( M" K上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
2 s5 {0 Q6 B; M7 |5 a
1 ^$ A" c: n; Z" x$ R#include <iostream>
#include <string>
& V8 y7 C" w% c" {+ d8 G  e1 Z- y% fusing namespace std;
void BubbleSort(int a[], int n)
{
6 f" b6 Z, a" F% L        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
8 x. A4 C1 m2 P7 e# Z+ g* W        for (i = 0; i < n; i++)
        {
                int flag=1;
                for (j = 0; j < n - 1; j++)
                {
2 ]9 c; |( a* G                        if (a[j] > a[j + 1])
& K( k. n% z0 L2 M7 ]4 V3 m                        {
; {/ Z, n9 s- g                                temp = a[j];
6 d) B; D4 E9 I+ c8 E1 f; e                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;
                        }
% Q  k% Z4 B( ~- S; e& v                }
                if(flag)
( u6 H0 v1 N8 R+ b5 o- \- l                        break;
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
8 u& P8 n0 i# m8 s- q# M, @{
2 O1 N1 i! b0 b, ?' d, a' t        int a[8] = { 5,8,6,3,9,1,1,7 };
7 `; z6 v  o- D! e4 s        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
+ S; S* }, J  v! ^  }" x' Q                BubbleSort(a,count);
        return 0;
}
9 R6 d' i. t. F
那么再以一个新的数列来判断上述冒泡算法 的优越性
0 l: G" j8 f4 ?: E9 U( V/ v3 4 2 1 5 6 7 8
这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下
3 r0 A! w# T2 ~! N/ M! I( u- u
#include <iostream>
3 ?( k( z2 `* g0 k- O8 d% ^#include <string>
* Z" D0 M+ ]9 C% ausing namespace std;
void BubbleSort(int a[], int n)
{
, E* k" v4 @: T, L1 i& ?; {2 C        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
) S7 B: v8 y7 M/ d        int Bubble_Sort_border=n-1;//无序数组比较的边界
7 k2 D/ i9 \: e8 \        for (i = 0; i < n; i++)
        {
                int flag=1;
7 E9 Z; U: r+ g! K( e/ M                for (j = 0; j<Bubble_Sort_border; j++)
                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
( o7 K+ B8 D( r+ P/ Q( J5 e                                a[j] = a[j + 1];
5 W9 ?- N/ i' A1 D& _  k1 D                                a[j + 1] = temp;
- K- }) J9 E5 E* H                                flag=0;
$ Z7 z5 _% f; a* s- m; J7 v                last_exchange=j;
: t) j+ ~. P- }; \                        }
/ J4 X, w0 Y( w6 k) B4 T                }
                Bubble_Sort_border=last_exchange;
5 P' r/ x6 o3 g- w, l! [: p+ v                if(flag)
                        break;
        }
7 m7 }/ i7 y& a: {; r# \        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
{
        int a[8] = { 3,4,2,1,5,6,7,8 };
9 a: [9 `+ C$ s+ F1 T/ Q        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
: {% G5 H+ \6 n& b' f5 }        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}

- N0 G& D# t4 O7 T+ W1 z
- x. N' i" X2 [3 J+ t, W" R到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
9 y$ `' X. f# n2 O基于冒泡算法，延伸出一种算法叫做
2 r% G1 D% \; T! P8 h+ j
鸡尾酒排序
( q8 `% c) X1 Y9 U0 H. D鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
  z$ |8 U* T  G3 z. L( X第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下


#include <iostream>
#include <string>
) ?. R) j8 c8 Q( N( z: |( cusing namespace std;
/ U: _: ^' r2 S; h7 s3 F' _void BubbleSort(int a[], int n)
$ I3 g- ]; ~. w: f6 r# s# n{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
- X7 ?# c4 ^1 q7 v9 R% o        {
                int flag=1;
                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
, C: @: S4 ], k# |) j2 U; t                {
1 V- X8 M) k% O7 e5 M; X* O                        if (a[j] > a[j + 1])
                        {
& R1 F& @' s. T+ D3 J3 Q. O                                temp = a[j];
5 i# u: N! {5 O                                a[j] = a[j + 1];
                                a[j + 1] = temp;
4 N9 f: d( u% c- h                                flag=0;               
                        }
                }
  T- Q% ~9 R- b1 S                if(flag)
+ N1 {$ x) U: y" F) f                        break;
9 u. d8 ?! I, L: |) ~  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
/ l' Q( ~/ ^- J( e/ ?! D                {
' }4 W; z4 F* e0 }% ]* P                        if (a[j] < a[j -1])
                        {
9 B$ g" m# ?1 u3 j3 n5 V                                temp = a[j];
                                a[j] = a[j - 1];
/ |% ~0 b- W/ B  y6 Q                                a[j +-1] = temp;
1 f8 T0 H4 E1 P+ k3 X0 V. n                                flag=0;               
1 {2 R# L! ?; ?0 [# U: L                        }
! W' D# Y8 H6 F- J                }
1 K5 }* B" p3 F. B9 l. u                if(flag)
                        break;
% u; Z0 R2 ]* ?; c) S+ e" ]7 S        }
+ o9 @/ I" _/ W. T0 f" x' @4 `        for (i = 0; i < n; i++)
                cout << a << " ";
}
/ o5 t: Y0 I5 a& Y' K" I/ Aint main()
{
, ]4 l9 A7 n6 f        int a[8] = { 3,4,2,1,5,6,7,8 };
( P) ~  L( k7 o7 a& N# o+ X        int b[4] = { 0,2,3,4 };
. f7 ?" d* _2 q( C. v        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
: D4 N( o" q6 S  k% P* J                BubbleSort(a,count);
        return 0;
}

8 Z1 H  W: ~( o& G* v2 F8 ~
! p! X& {8 i, W6 [以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
# _& A: |, P# C% u
( z, z! f' s) {5 ?& x————————————————
% C: P1 a) S4 Z9 i6 u版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524

! l9 D, V" J+ p$ N8 R( d2 e