关于冒泡算法的那些事儿

杨利霞

关于冒泡算法的那些事儿排序算法的复杂度
0 G: M4 {" N; I, |/ B. U
# X# K; w0 i1 v: U) f6 m; r( W

关于冒泡算法你了解多少：
/ ?7 g4 d- n3 v' ?5 x首先我们规定数据如下
5 8 6 3 9 1 1 7
1 N  ]2 ^, w* }# b3 g4 i
0 F. l5 c6 k4 |% x在对数组进行冒泡排序的前提下，首先求出数组是否为空
* x: J0 Q: ~" s方法一：
2 k4 h0 ]$ C/ O1 M0 z+ K如果数组是用vector定义的,即：
2 k7 s  x$ y! d0 D  Wvector nums;
//或
vector& nums;
，则这样写：
) I; `( }; f0 a5 \$ hif nums.size() == 0:
3 o' H  W. A' ]' e8 c; y7 _return false
方法二：
/ b" M# z* d1 }5 J如果数组是这样定义的，即：
int nums[] = {1,2,3};
. Z$ W/ d) f0 z8 K# q8 j$ m8 \先算下数组长度：
nums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
" X' b) F) T! @! cif nums_length == 0:
return false
6 e6 F9 i5 v4 U# g原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544
; d  _/ m8 U( c4 ~8 Q4 p
  m# X% q+ L/ y4 u7 o* O解决了上述问题以后，最原始的冒泡排序如下

, z% n; g) q: t$ ?  {: d1 L/ f2 z6 B#include <iostream>
#include <string>
using namespace std;
/ u" V6 G4 v/ ~4 w3 P  p4 @void BubbleSort(int a[], int n)
  L9 k7 d$ |& w/ t4 A{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
, i5 m  M2 F* W% R( q+ @        for (i = 0; i < n; i++)
( `1 E1 o5 S, N( X# q( m        {
( v1 ?3 b9 s* {. J: M. l- T                for (j = 0; j < n - 1; j++)
: p- L7 s; ~' ]5 a  \: _4 w  G                {
                        if (a[j] > a[j + 1])
5 C, E9 u" a/ }                        {
                                temp = a[j];
                                a[j] = a[j + 1];
2 P/ s/ D) b3 s) X3 K                                a[j + 1] = temp;
                        }
                }
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
' O& R+ t  C( p+ A' i$ S{
        int a[8] = { 5,8,6,3,9,1,1,7 };
0 y& ]1 q6 K; y, H8 v7 {4 e        int b[4] = { 0,2,3,4 };
6 q. e: a* U" o) \; e        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
; g; P% m* C- E. R" k" d        return 0;
}
" o3 x7 t3 `# i1 _( b. Z5 i2 ^. E# ^
- `( x/ S" H/ B9 Z) S上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
2 f0 q- C1 }# S2 K' U
#include <iostream>
#include <string>
7 p) g- W( a8 husing namespace std;
$ e7 l! I' K1 avoid BubbleSort(int a[], int n)
4 l( n! s5 R$ d- |" ^4 u+ X7 Z6 y- `{
0 B- g) t' `  l        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
- d7 J/ T% j9 Q" _        for (i = 0; i < n; i++)
$ M6 M! |$ C# ^" j+ z1 ?        {
                int flag=1;
                for (j = 0; j < n - 1; j++)
* I, f2 k- t* g                {
                        if (a[j] > a[j + 1])
                        {
/ [7 _: N9 u) k                                temp = a[j];
1 c+ ^) i0 ?3 Z                                a[j] = a[j + 1];
6 h1 C# F- ?, @$ }! o- w                                a[j + 1] = temp;
                                flag=0;
! r! u* f( ~0 w$ ?& ?) ]' j" j                        }
6 c; u7 t2 [& k. d/ O: H, m# a; g- n                }
& |/ d' O* n3 w% _( s# i                if(flag)
+ a$ o! `' `! `8 e8 k: ^                        break;
# h* y& g# R, r. C        }
        for (i = 0; i < n; i++)
                cout << a << " ";
2 K6 l& n1 X4 Z5 Y, }}
: S; @4 @5 Q" b" Uint main()
{
        int a[8] = { 5,8,6,3,9,1,1,7 };
" i. Y1 E0 S* t3 [, U) [4 \4 u        int b[4] = { 0,2,3,4 };
9 e) ^% ~4 v. _8 I2 L/ _        int count = 0, i = 0;
1 b! G# F( b- k1 q        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
$ t- ^& J' e% D- i4 V        return 0;
}

! |3 L  }8 R( c9 A8 {$ S/ }  p8 ^" m) ]那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
/ t, @% Q$ X- L* g2 q# s* f& x: Q! F这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下
" n8 C8 q9 r2 a* `- H
#include <iostream>
2 i% \' w0 i6 H. w2 z5 D#include <string>
! @0 X& u; p3 R9 n; xusing namespace std;
void BubbleSort(int a[], int n)
& E1 g7 x0 {7 C3 m5 W5 q2 A; b{
6 F+ ^' y  a& A* }* R  G; s( v        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
: p/ e0 d) N5 d' q; c        for (i = 0; i < n; i++)
1 f- @' ]3 @, k0 F5 L        {
+ m1 m5 j" M/ Z8 t' c) U1 E0 a+ S5 |                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
  a: C# ^' n7 B4 K5 I4 W3 @" @                                a[j] = a[j + 1];
3 p8 {. A" g+ @6 _. \                                a[j + 1] = temp;
6 c* w, \8 M7 S/ y' R9 N6 q                                flag=0;
9 w$ C/ ]: a  r9 k# D* a                last_exchange=j;
                        }
                }
                Bubble_Sort_border=last_exchange;
1 X& L' f# S1 E" N( |                if(flag)
                        break;
: u4 p+ Q! m: A3 [4 Y" W! k        }
        for (i = 0; i < n; i++)
                cout << a << " ";
3 c9 {  w0 c8 ]}
int main()
8 {; r0 ^( x9 b' R, z; Z{
, n. D  _# _) ?2 X' e        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
! _; I, L2 g: C% A# }        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
) D+ S3 m" Q& b* {  n6 ?                BubbleSort(a,count);
& E4 R0 t: ]% }4 b        return 0;
% z9 g# v/ e$ f1 F}
( O, W3 o2 r  [/ C" k9 P

9 m; ~5 J4 y% F" ~到这冒泡算法就结束了吗，不可能，你在看看这一串
5 u6 h* \+ o6 ~( l2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
) l4 n" E6 M4 ^% V0 T( ]基于冒泡算法，延伸出一种算法叫做
6 u4 w% F  ~$ K
/ x. {; i. M. Z! p2 _鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
1 o$ }( W+ y9 b$ A; I第一轮，1和8交换，
3 r9 E6 v' q2 @1 s0 I$ K第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下

2 Q; E" C( z) X! ~
  {  m6 K6 a* W% L4 ]#include <iostream>
#include <string>
using namespace std;
$ _9 X- H5 v+ M5 ^. }  S4 svoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
* \6 f' b/ h3 W3 E0 r* |        {
                int flag=1;
! J! P6 B" Z5 }/ r, O9 q& ?5 ]                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
# _3 r' h) h/ V* R: x6 t                {
" `7 [( v  W; ]% ]% B4 v                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
" {' L. X3 f- K; O' X                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;               
                        }
                }
                if(flag)
% S1 x! R, I% Q) w                        break;
  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
$ l& {  {, {8 \. X! `- ]                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
9 g- F4 n  s& P3 h; S" r3 N                        if (a[j] < a[j -1])
                        {
                                temp = a[j];
2 c- b! W% I8 Q0 v8 f# x( r' E                                a[j] = a[j - 1];
  U. r2 a; V: g) h) J9 f                                a[j +-1] = temp;
                                flag=0;               
6 A  {3 v8 T- ^1 V% @- n                        }
; T0 @  A% Y' {2 O# j                }
                if(flag)
                        break;
        }
        for (i = 0; i < n; i++)
3 a  V  w& K8 C5 f                cout << a << " ";
}
int main()
{
# C. p! p+ B. m) C0 o+ X        int a[8] = { 3,4,2,1,5,6,7,8 };
- H2 n, O- e) T0 d        int b[4] = { 0,2,3,4 };
9 U$ `( T( v5 J/ G) v        int count = 0, i = 0;
3 k, f, S) _3 I( ?        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
+ e# w* @) ?5 r1 X; n0 K. Z2 G" I}


, d5 r2 f+ N$ N' |! h: E以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
6 A5 B6 p; c' y% Z" ]9 ]/ l
+ ?% ~, [' ^) j8 c————————————————
% j) M/ ]/ D, @9 \0 v  X8 u0 K版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
. [3 s0 Y5 e$ E/ c8 M
. m- _4 g% o) e