关于冒泡算法的那些事儿

杨利霞

关于冒泡算法的那些事儿排序算法的复杂度
0 y% S" n4 A3 ~# F& d* u3 X3 p

" I+ L$ K7 p) W) E7 Z, y
关于冒泡算法你了解多少：
首先我们规定数据如下
% w9 }3 d/ o6 H7 k5 8 6 3 9 1 1 7
1 `0 B& h! e! ~6 }3 _
9 V8 A1 U; X$ Q2 ^在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
如果数组是用vector定义的,即：
0 |' X* [7 t. l: J* r9 s$ w4 v7 Evector nums;
//或
vector& nums;
0 F( G& ]7 D  t/ g/ M# ^  _，则这样写：
& V- Z( W; L  q0 @) V% ]if nums.size() == 0:
% w' r- B) G4 G; o+ Ureturn false
方法二：
8 S# L' x2 s; J0 Y* z+ \* O如果数组是这样定义的，即：
! O! h3 ]: v, M, f5 J/ V3 o* jint nums[] = {1,2,3};
$ N* j* b+ W6 U, G先算下数组长度：
nums_length = sizeof(nums)/sizeof(nums[0])
0 V$ ^5 y3 F" E. t然后判断数组为空：
if nums_length == 0:
, k" B4 d( U" c1 dreturn false
( Z4 p# O" y/ v$ i  v# Y' X# m原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544
) f8 r* W6 k0 n; N& w/ ~2 h
解决了上述问题以后，最原始的冒泡排序如下

#include <iostream>
% j* M6 A" N6 X0 n  {#include <string>
using namespace std;
: m6 S1 V" \3 J3 Rvoid BubbleSort(int a[], int n)
{
' k! l: T7 m) ^9 F: {        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
$ _' B: ~4 c5 X# `9 H& u: B        for (i = 0; i < n; i++)
        {
# O# ]+ ^& y! a1 i                for (j = 0; j < n - 1; j++)
                {
                        if (a[j] > a[j + 1])
/ T$ ?# W& @2 g5 V! b3 p                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
/ G- h' M- r9 x8 P. {2 ^: K                        }
                }
; r& n; x% x, H7 q7 c        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
) l3 [; @, {( P: ?7 Kint main()
+ V: d, c+ p7 v- c: @; N. Y{
$ h1 S) i+ X8 k        int a[8] = { 5,8,6,3,9,1,1,7 };
$ H6 h* t6 S8 k        int b[4] = { 0,2,3,4 };
  K3 X+ J& L6 s( Y6 X        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}

上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下

" D* n: e' h& j' u* _#include <iostream>
7 r" O! D' ~+ L5 @% B+ M#include <string>
# s1 \+ _4 {# r9 Uusing namespace std;
void BubbleSort(int a[], int n)
{
) i7 ?* P$ J3 B* V' ^* P( C( u4 ^        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
/ M% K# T% Z$ x6 e* T( U; ]2 l        {
                int flag=1;
1 C  T; I* m- t                for (j = 0; j < n - 1; j++)
                {
4 B, a* F/ L0 R4 |6 W9 N                        if (a[j] > a[j + 1])
5 [( Z* U+ G, @: a) t" Q                        {
" T  C, w- r% `- e) v                                temp = a[j];
                                a[j] = a[j + 1];
, Z+ h% C' {  S2 C! ?                                a[j + 1] = temp;
* b$ f# K5 D* p$ W                                flag=0;
                        }
( s( ?: _$ B  B, Q- V* f  j                }
  m* }- x6 P9 ^% n: y                if(flag)
1 N. S; U# o! a; N8 y                        break;
# {! }1 _2 h) A, m& b- D        }
7 D$ M0 w' ^3 Z        for (i = 0; i < n; i++)
* j( D0 P3 c2 i* u                cout << a << " ";
" k( R3 [% p0 M; A6 b. p}
& R; v5 F9 \% O! b" Mint main()
{
        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
1 s0 Z( K- T) T; C        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
( u; ]" u& i2 L2 o0 T) i" h                BubbleSort(a,count);
- k: d; o2 W8 \# v. z# c8 W        return 0;
}

那么再以一个新的数列来判断上述冒泡算法 的优越性
! Q! T3 [2 S- C3 4 2 1 5 6 7 8
1 k( Q( d4 I& R; W; Y7 D. Z1 A# Q* k这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下
  H4 Z$ x+ S, }
8 w; r- ~, Z2 G! x2 n#include <iostream>
, S- }1 u% W$ r; ^1 T#include <string>
. h: X0 J* n9 J: ^- uusing namespace std;
3 z! |6 `  q% z% d5 gvoid BubbleSort(int a[], int n)
7 b1 {1 S% e5 [( {' c* K; F4 B{
6 j5 R" p7 G0 u4 ~! o9 |( q        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
" }$ J2 N) ~) d% `/ M        int last_exchange=0;
( i( u, f* Z: ^7 S0 U        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
                int flag=1;
1 x# [' }2 d' t0 {; K                for (j = 0; j<Bubble_Sort_border; j++)
6 j3 m( v* Z- l; p9 \7 ]/ ?                {
                        if (a[j] > a[j + 1])
* U( {+ k$ S( f- f0 [3 O                        {
1 U2 O* C+ W4 N+ `3 ^5 I, L                                temp = a[j];
% W, q, x8 p# k) x- W: Q                                a[j] = a[j + 1];
                                a[j + 1] = temp;
1 u) A5 M+ k' @' [  e$ k, X' a                                flag=0;
                last_exchange=j;
                        }
- E& p' e) }1 ~3 {                }
                Bubble_Sort_border=last_exchange;
4 F7 H. X* V, c/ h* t' c6 p                if(flag)
                        break;
        }
+ z. m- G/ O) X0 L, w  \        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
{
7 r8 k8 n0 P6 A# h0 a) b0 r        int a[8] = { 3,4,2,1,5,6,7,8 };
# D3 H+ t; `5 G; p" r# `, Y% }        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
* G4 T4 i0 R& P6 S3 {3 B        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
1 v! z% e* c5 Q. |' y, D                BubbleSort(a,count);
0 }# X5 p9 s* O. f/ ~# Y        return 0;
}
& O: y3 |. [( r, u' N; g$ _1 `1 P9 o
! Y: i9 w# o7 O- p
到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做
5 q7 P' t$ Q. m, F9 d; Z
鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
/ Q; i- g! d( ?6 n, f首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
1 z( K& Y3 P- F6 T/ s第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下

* Q) R7 O& d; f9 s3 M1 N4 v
#include <iostream>
#include <string>
) v1 u4 g- X+ h/ d5 H0 y- Pusing namespace std;
3 y1 P; o( D+ pvoid BubbleSort(int a[], int n)
{
8 i8 F1 l8 U  D0 S        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
9 j9 E! y2 N0 |/ c; Z3 j6 j        {
                int flag=1;
$ |' Z5 w" X  r# j6 Y                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
/ Z7 V0 B* X' B6 ?- y                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
# W: r: S' u2 e8 O( A0 m/ D                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;               
                        }
4 X% {& w  q& \# `                }
                if(flag)
2 [4 z2 X6 I  U8 ~: o9 r                        break;
  // 偶数轮开始之前  flag 重新置为1
6 r0 y# o( m: f: u( U                 flag=1;
                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
* K8 \& V( j: Z  I                        if (a[j] < a[j -1])
7 H; C1 B1 d# n! f; w7 ?. o9 o                        {
2 M8 @" L+ b( W) I) d7 ~$ W                                temp = a[j];
+ T7 T$ a1 V2 `; o4 h; E" N                                a[j] = a[j - 1];
0 ]+ z/ B" Q9 r6 ]                                a[j +-1] = temp;
/ ~* i1 j# V8 {) h/ C* q                                flag=0;               
8 u5 F. V9 Q3 i, z- w1 q& r( U                        }
                }
$ ^. l2 t) T1 ?% C                if(flag)
+ q6 N, F* P- a  I                        break;
; C. w$ Q4 i8 y6 T9 r        }
# @( n7 `7 a$ _0 n: h7 E        for (i = 0; i < n; i++)
7 d1 J2 R  Z3 G4 o                cout << a << " ";
}
int main()
{
' m4 g, B) x/ |# h! e        int a[8] = { 3,4,2,1,5,6,7,8 };
' Q: f3 G- N% N, h* Q        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
+ X- \/ e, r' B3 g        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
8 z- w. h; d0 N: @$ K! g; c: k1 q                BubbleSort(a,count);
, D' m( {" U+ @: d3 \! o* r        return 0;
}

0 A: g  t& M' Z; K9 ?2 _
! z3 g; N4 e# `6 u以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
) R# ^& i* Y3 ]! t
————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
- i+ j* W- R6 j$ B2 _: n4 Y- b原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
0 ]$ J$ }, H7 X. _* ~; L. z* c
  s8 [2 \: G% z$ Y4 R