关于冒泡算法的那些事儿

杨利霞

关于冒泡算法的那些事儿排序算法的复杂度
% E" w+ a1 F, A( |


关于冒泡算法你了解多少：
, ?2 N( {9 ~! ]8 b! E$ w首先我们规定数据如下
5 8 6 3 9 1 1 7
% i0 K0 v$ }4 A- f
在对数组进行冒泡排序的前提下，首先求出数组是否为空
6 W( t7 h9 Y% E% f: ?/ c方法一：
6 P" g# ~. O. O如果数组是用vector定义的,即：
+ R# N+ n- }9 x; j8 S6 Dvector nums;
//或
1 w& ]1 T: G9 W. y) Y1 Dvector& nums;
9 M) ?1 \% I" j" q，则这样写：
if nums.size() == 0:
7 T( u+ l8 B9 E2 `$ T% ], areturn false
- Z, Q; r$ e5 o2 S5 `* g0 N方法二：
如果数组是这样定义的，即：
# F) h4 i4 N$ P0 P) Q# s7 zint nums[] = {1,2,3};
: {2 F7 x* a2 x先算下数组长度：
& h+ x: s# \; @+ }nums_length = sizeof(nums)/sizeof(nums[0])
) s; n4 d# i; @* N% @然后判断数组为空：
1 B' B9 z& y$ n5 Yif nums_length == 0:
return false
+ L6 c7 v+ m0 L1 n/ n原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

解决了上述问题以后，最原始的冒泡排序如下
" Q9 T! a3 r6 {( T  O' H" [
#include <iostream>
#include <string>
8 ?  z9 r6 x+ U1 V& z7 fusing namespace std;
) ?; ^! \" i/ G8 F' y6 k; C( xvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
) a, c; A7 f7 L0 C; i& n( x        {
                for (j = 0; j < n - 1; j++)
  {6 N* J: u7 V. p2 i                {
                        if (a[j] > a[j + 1])
  t/ i) ?: G. U/ N. d1 z& g/ [                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                        }
                }
' k! f' ?2 p5 Y4 p        }
- y* \9 Q0 R, ]4 s3 J: ?: ]% I7 L" E% o" K        for (i = 0; i < n; i++)
( [( J: a0 B: A  G, K# ]                cout << a << " ";
}
4 T8 H4 y* f, Bint main()
4 ^' L/ {! U9 z8 b/ Q' @! N{
        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++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
& ^3 {& w, o/ o, l/ Y                BubbleSort(a,count);
& L& c7 O& r, Y2 ]9 z6 {        return 0;
2 m1 P+ z7 o) S8 n5 r/ a9 l}
- d' G! \( l- E
( y3 c3 q& [/ v! D上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
0 d! r$ Z8 h$ _) |那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
( x3 r  _9 ]' [6 N: P  w: x
# ~: l1 F6 e& U4 S$ Z0 n#include <iostream>
/ t: [( y" j% f#include <string>
using namespace std;
void BubbleSort(int a[], int n)
( f. `! I2 J1 m4 F{
+ l/ m* e/ V# H$ a5 v, a1 J        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
1 H3 G2 o) b. Y+ k% y2 ~9 s/ X& y        for (i = 0; i < n; i++)
( F8 N' V8 P) f        {
                int flag=1;
! Y* t! c( W3 \, I                for (j = 0; j < n - 1; j++)
0 w! b5 f1 I" T6 i6 g: N; n                {
+ o2 [9 G- _2 F& E                        if (a[j] > a[j + 1])
                        {
0 H% k* a  ]2 B# h7 w0 h                                temp = a[j];
+ e3 P* O8 ?7 B* `; Z                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;
) n# G3 l0 m: ], i+ O                        }
6 w3 `2 r7 n$ |! T  F" G: ~9 A                }
                if(flag)
6 g0 m: q1 q3 g6 ^# x' D                        break;
        }
8 x  m, F! L; t* S        for (i = 0; i < n; i++)
                cout << a << " ";
: D( N; ?* ?4 ~: {) Y* J) @0 r}
int main()
{
9 |  m0 W  p1 n& i' f        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
2 n# _: V! u; h* B" u        int count = 0, i = 0;
$ [5 ?, \1 J0 {9 q  I        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
. F' ]" Z* P  h$ W" C: J+ m+ q                BubbleSort(a,count);
- \' t0 \9 F- a. Z- }' G' t4 O        return 0;
) u( C' Q; Y  Y$ g! v( ^1 v5 K}

那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
  ]- U/ N  X# q8 F4 A# E% C! V3 v这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
. f  P( }, Z# s; O* G' V& K1 i此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下
; C3 C' R8 _) @" b- [" d
5 d2 w! ~" ?9 f4 Z4 \/ Q4 A#include <iostream>
8 L* n+ z+ c( l1 e6 [5 P. {#include <string>
using namespace std;
& ^* x+ o* l  Svoid BubbleSort(int a[], int n)
& d3 _- V6 j- `* [, \7 _8 ~1 B{
" C9 M0 S' d8 c- u, x        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
( d* _' B7 K6 e3 h: T        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
# V) t7 Z: d; t: k: S                int flag=1;
3 P/ y" B' A* J9 A6 Y- P: G                for (j = 0; j<Bubble_Sort_border; j++)
                {
                        if (a[j] > a[j + 1])
9 b$ W3 |% u' B6 Q                        {
' F, [0 h* T9 t6 q3 ~& A                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
; _4 H& Y; @- t% Z6 t                                flag=0;
                last_exchange=j;
# F. a- X+ ^! G$ R- \                        }
                }
                Bubble_Sort_border=last_exchange;
, a1 `$ f7 z% z: C/ O; c& K                if(flag)
                        break;
        }
4 V! U9 a8 t+ E$ k- P, c  K* n6 {  v6 }9 D        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
2 Q  e) d" c# u5 g! O" ^{
        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
0 C5 K. e' f/ x3 S) n        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
) V: Y' ^- ^! f- D        return 0;
2 N7 T5 x5 P3 k}


到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做
" x" M, e2 N' K1 E2 r3 c6 Y* {0 ]& T1 }
鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下

/ l8 v6 }3 ]. ^7 S' j
#include <iostream>
& P& X: q/ s- m; W. S#include <string>
. t% h, L8 N3 k5 q* iusing namespace std;
void BubbleSort(int a[], int n)
& ?( h4 _+ k! m" N; O{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
2 E3 u( k( W. Q; Z) e/ K1 v8 H  V        for (i = 0; i < n/2; i++)//奇数轮
! ]: z( k2 @" D  U4 V7 E1 @5 i        {
- i2 Y1 o0 m( e5 y6 ?                int flag=1;
1 y% Z3 \5 l1 {3 @3 t3 X5 I                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
1 J* i* Y( P3 L  p( X2 b( p                {
                        if (a[j] > a[j + 1])
4 Z1 J% ^2 W0 E& _: d* n% |                        {
, ]! [: a1 V3 t" s) i                                temp = a[j];
                                a[j] = a[j + 1];
0 R! w9 _, n3 V                                a[j + 1] = temp;
                                flag=0;               
. t! _0 {6 h! S- N  R1 a! B                        }
                }
                if(flag)
                        break;
  // 偶数轮开始之前  flag 重新置为1
+ m& s' V* e" v; k) M" `' @1 `                 flag=1;
2 n5 E6 a1 B$ `* I+ J                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
8 V, g2 Y! x! O0 [2 ]% q                        if (a[j] < a[j -1])
                        {
: ^$ l# O& h: {9 @# p                                temp = a[j];
6 w; l! D' ]) t# \% Q                                a[j] = a[j - 1];
                                a[j +-1] = temp;
! a+ T" B+ N  w- T                                flag=0;               
: n6 R! F; B8 F                        }
                }
                if(flag)
$ T! [- W7 a$ S3 n! J/ B7 f                        break;
        }
        for (i = 0; i < n; i++)
$ ^# i% B! B9 P) b- T5 o: J- F& t) [                cout << a << " ";
}
. ]; L9 F/ b0 a) B7 n5 T' `0 z+ Iint main()
{
" A) i( ^5 n# V% n5 S        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
: ~( y9 o. `0 Q2 J1 |                BubbleSort(a,count);
        return 0;
}


以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
) Y5 C) a, W) i/ |+ ~
————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
; Q  j; h" R2 ?' g2 D7 x: |
/ l& D8 Q1 y5 W: N4 H7 i