关于冒泡算法的那些事儿

杨利霞

  k1 Q5 _. B) V+ t关于冒泡算法的那些事儿排序算法的复杂度
- D/ ~9 k  \8 a: S4 O$ s


, o: C0 y; {2 Z' t关于冒泡算法你了解多少：
% s# B" W# s- B首先我们规定数据如下
5 8 6 3 9 1 1 7
3 V3 {$ u# V7 C( c# `; y
在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
如果数组是用vector定义的,即：
# B( j$ h! Z, w3 |7 ?. lvector nums;
//或
2 }( q) I3 @* I, M) _vector& nums;
，则这样写：
if nums.size() == 0:
return false
方法二：
: s* k' _( B7 Y: v1 J5 _$ N" W$ l如果数组是这样定义的，即：
: G- f4 j2 {& |$ A" T% T: S$ T5 vint nums[] = {1,2,3};
3 y) S# b7 z% ~5 Y' ]- `$ w先算下数组长度：
3 Q: k6 K) U& @7 u! Nnums_length = sizeof(nums)/sizeof(nums[0])
, ~, b2 l( K5 y$ I. k然后判断数组为空：
if nums_length == 0:
return false
3 j" b4 L/ H, p原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

2 X5 x1 ~. q. g4 m( p& B# ^解决了上述问题以后，最原始的冒泡排序如下
: b4 j) d  @  d( V. l1 t" B5 ]4 U: @
#include <iostream>
' d8 e5 b5 F! \# Z: a" @#include <string>
using namespace std;
+ S! W- P/ I( Xvoid BubbleSort(int a[], int n)
3 u5 U" U$ T5 m' g( T{
2 O( v: f. u7 z6 K3 [/ c        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
# u1 Z6 U. p; m1 W4 @        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n - 1; j++)
/ l0 B! ]* b8 b* p                {
                        if (a[j] > a[j + 1])
/ p6 C3 ~3 V. x/ b& m; g( j                        {
" }% t6 t2 J& N" X0 J! ^. {                                temp = a[j];
# o) }/ l" X8 B- }; E0 D) j                                a[j] = a[j + 1];
! Y, R, b1 G& k/ ?# M( o                                a[j + 1] = temp;
) H2 T2 J" l) D5 n+ ]7 t% g( Y" e/ g                        }
3 u9 R2 m, [7 b0 g) \0 N' \                }
, c, O- y  `! v2 n# V        }
) d, A4 H5 Y6 b        for (i = 0; i < n; i++)
                cout << a << " ";
! O" i9 }9 t6 O" B4 R# `, t}
" [: s' t6 m2 F- f5 t2 e- Oint main()
1 x! y" O4 Y; U0 l. t  g{
0 ~% {8 d( t* `1 p# N        int a[8] = { 5,8,6,3,9,1,1,7 };
6 x% h4 J6 X8 ~- h5 [        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
0 U* }: {4 ]- p* ~2 y        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
; T: d9 \* a/ g; l5 r: P/ n* X}

上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
! s4 f8 y# v# x% w9 ], u, F那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
+ }2 S2 @: V/ p# K1 _' o) F
#include <iostream>
* A& H. y* p+ T; Q6 P#include <string>
using namespace std;
1 G( m! l5 D( |/ `void BubbleSort(int a[], int n)
{
- _) o1 }: d2 A* Y        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
                int flag=1;
                for (j = 0; j < n - 1; j++)
' i2 N" ?- R' v0 ~                {
                        if (a[j] > a[j + 1])
, [; z5 j" G" ^1 G7 [7 [                        {
                                temp = a[j];
$ A9 F3 L/ z, I" S3 v                                a[j] = a[j + 1];
7 n, e% ?5 ~' X& \& d* v                                a[j + 1] = temp;
                                flag=0;
                        }
                }
                if(flag)
. H( ?% b2 [2 v" L, u4 P0 M                        break;
2 L9 \8 d% `  Y% P        }
        for (i = 0; i < n; i++)
0 x, f; i! e+ e+ t! W5 ?                cout << a << " ";
* c) ?& u/ M, v8 B}
0 w$ [5 J& a: E5 n4 o+ N  o3 p5 cint main()
{
2 f5 W# G! H+ N) B& H        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++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
' Q  J, h7 d3 N* n                BubbleSort(a,count);
1 t/ p) O' [$ Y( p  g* ]1 L& e4 j* l        return 0;
" i$ J" h# i) S" v; j( |}

那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
5 W  }8 \- Q/ u6 a% H这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
2 B/ f+ Y$ i, |( W( _4 f( A8 X# ~此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下
9 j( _! f2 U, M7 T- Q0 `& {( k' ]/ k
/ I( K' q% l1 Z: m- X9 S#include <iostream>
( W  \5 J8 g& P' t% }#include <string>
8 W* S; h$ T% x8 j6 `4 Iusing namespace std;
/ w# B- Y5 ~% G& Zvoid BubbleSort(int a[], int n)
/ ]' d; @( R0 A7 i! K{
* Y- {- {4 b7 \7 J8 V) E        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
( I, W" O  \7 H1 {+ q  [& s5 T        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
0 n/ H  ]5 m9 o& h, l  O; k8 d- k                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
8 J' b  ~; c8 \                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;
$ I( O& I+ v* F, B, L/ o4 ^                last_exchange=j;
                        }
  O3 j) m! \# V& c                }
" h- U6 H2 q% E; q6 P                Bubble_Sort_border=last_exchange;
5 N4 ]6 @  P/ u/ w1 a3 A: ^. l                if(flag)
4 \& `: p* N$ o( I& J3 V/ M! r                        break;
        }
: Q" o8 _1 e# A9 P! \        for (i = 0; i < n; i++)
7 l0 x! n! b: p* p/ k6 L* u7 \" Y                cout << a << " ";
* o4 ~0 z8 T  e, F; g  _}
3 o5 D& C" [2 l5 w$ w1 U9 g8 cint main()
/ z7 }% [- p/ q/ s# B' e( u9 M3 L{
        int a[8] = { 3,4,2,1,5,6,7,8 };
: B* Y% N' J/ F  \& x  f2 L3 P  W8 T        int b[4] = { 0,2,3,4 };
. B  X1 A  y% L  [7 Q0 V        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
: w6 o9 `0 p; W- ~$ D/ ?                BubbleSort(a,count);
; F; \1 d" n: n9 c  M, f! n/ j, J        return 0;
8 p6 n, U& D5 R- L}

% F+ j/ B1 W, b6 M2 K* d
到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
* r' x# _8 b, Q0 H上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做
" r' _! ~" H! X0 y( f8 @
& u8 ?' c! I/ g* Y鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下
5 z6 d7 E  f: t

#include <iostream>
#include <string>
' |/ `  L' y1 nusing namespace std;
6 K- L- V% G+ b' Jvoid BubbleSort(int a[], int n)
{
# N# e, L# a# g4 }        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
        {
' b) [2 S' e, G* h. \: G2 a! u8 N0 J                int flag=1;
+ F; `( a( j+ s                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
/ o- v, a* }5 z, ~3 @' M  w9 [                {
, G8 N0 P6 ~6 ~& n8 i3 t                        if (a[j] > a[j + 1])
                        {
' h# |, s( U8 W% ?. c. i" C                                temp = a[j];
" o5 x4 A# W1 T$ i; y7 X& Y                                a[j] = a[j + 1];
( J6 ?6 H* _! }; ?: `4 N( _                                a[j + 1] = temp;
7 n& J" b- C1 z2 _) K8 ]4 e8 Q                                flag=0;               
7 x- h) U+ x" w$ p2 R# G                        }
                }
* p( i& C( c; }* {) Y, ~0 u                if(flag)
6 O0 _+ y+ ?7 C2 T0 c1 l5 ?                        break;
; m( k' w0 w# ~# ]1 H& c  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
2 A2 o, ~6 V9 t1 c( w! g. l  s                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
3 y. b2 Y4 g4 E/ X! _) y" J                {
1 I' e# j( ~1 S+ u! b8 j9 t7 z                        if (a[j] < a[j -1])
: ~, r+ r3 i! [1 e6 `                        {
8 W8 `0 f+ Z* C: U                                temp = a[j];
9 ~& s( E5 g1 s                                a[j] = a[j - 1];
5 e. \* g* Y; @, }                                a[j +-1] = temp;
8 h% {7 Y$ r0 a; N7 H0 `( E                                flag=0;               
2 B' _9 ^) i5 @& K+ Y$ W                        }
- Y  o% W1 y  d7 @- |* P3 [                }
                if(flag)
                        break;
        }
0 ^! w" h  \! N# J1 d        for (i = 0; i < n; i++)
0 o# D/ E1 F$ {* H" E! \) O* i                cout << a << " ";
}
int main()
5 X2 a) K7 H+ h3 b$ e{
, i4 i9 y1 o7 z8 b& S, K        int a[8] = { 3,4,2,1,5,6,7,8 };
& g4 u4 c# y  n- E1 y        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
2 c5 Q8 }6 T- w9 X+ m        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
7 M- \% l, ^  v1 l# }$ S                BubbleSort(a,count);
- j" c1 M6 e: w4 U& ^        return 0;
  \- ?4 m2 [: [4 ?! b: Q}
7 a8 Y" Y9 P6 |! z& \' x' |
0 h' \" K! c/ d# f/ Q( d# Z' o& `
8 `  f: }& _( J+ M& A9 ^# R以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
" Q, x, Z  \5 @0 |% _
1 G' p) ~, F( y2 ~- P+ Q8 R3 p————————————————
& O7 s3 I: h8 i; q3 g版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
$ k6 @6 ^$ ]& y2 C/ k1 R  F) W! k0 L8 v

& z) Z% z! T0 W7 p6 W8 j8 ~" t0 [