关于冒泡算法的那些事儿

杨利霞

关于冒泡算法的那些事儿排序算法的复杂度
2 V2 x- f$ b2 l$ N; \# o% _+ a
- o$ C) O5 k8 e5 E/ s' h. U

关于冒泡算法你了解多少：
8 _4 i7 {7 M2 [4 c9 j8 X首先我们规定数据如下
6 i2 J, r  ?4 y: C) j5 8 6 3 9 1 1 7
3 e# g( l6 V* p0 N+ j5 a6 K) e; `
在对数组进行冒泡排序的前提下，首先求出数组是否为空
& S, E, I' i' f2 M  [8 C, U4 s方法一：
- `& U1 t3 h& s# R+ f7 U6 Y+ V5 J; H如果数组是用vector定义的,即：
9 H6 w4 B) D$ ^vector nums;
: \7 s; b: m) |. ]) ]" D+ m//或
  t# _7 M- z: P0 ?vector& nums;
，则这样写：
! c9 R% P- W- F) s! K8 n* lif nums.size() == 0:
return false
* r) Y$ F2 u5 b% K# [方法二：
: f6 k8 `' f3 q2 u6 {8 ]如果数组是这样定义的，即：
int nums[] = {1,2,3};
2 h( u. J' f2 j先算下数组长度：
nums_length = sizeof(nums)/sizeof(nums[0])
/ G$ `. O+ v% b; K5 \4 A然后判断数组为空：
if nums_length == 0:
return false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544
, l9 K8 X0 I) |. H
( [5 }( ~& v, l1 e, A3 s解决了上述问题以后，最原始的冒泡排序如下
8 ]' L# k& c1 ]
3 ?) a* m5 R- J4 @8 q& \# A" L#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
7 ?$ R9 K; o. Y! [4 I& i        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
6 K3 s. n, U+ [" R* N                for (j = 0; j < n - 1; j++)
/ \7 U4 K6 W) l( ?$ |/ i, I3 F                {
                        if (a[j] > a[j + 1])
# Y- y) w5 h2 J+ G/ d( E                        {
# w- H1 m0 s6 K8 D! ^$ u                                temp = a[j];
                                a[j] = a[j + 1];
2 q# b) h, H9 t# ~                                a[j + 1] = temp;
5 d( I; \% G- W" q  a+ E8 f, m$ `2 `                        }
                }
* i% y' f1 s) _5 W. S        }
" w+ s, l/ h- |3 P: S9 w        for (i = 0; i < n; i++)
  s/ T% i2 m& h                cout << a << " ";
}
( A4 @8 t" R9 Xint main()
{
        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
# l/ r/ N/ y" f1 F        int count = 0, i = 0;
! n0 v& w6 B0 X  n% f+ c- q8 @* [        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
2 e3 O/ G$ g4 V+ h2 ?+ `        return 0;
. S$ u# `" q8 S9 R. E( R( G2 ?}
* u9 |; L0 t; T0 M
( f) M# N9 G4 d* F: u上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
! d7 Z, t/ J) I# k& d
#include <iostream>
, [! Z6 }5 F4 w# m: \1 m4 {#include <string>
' h( c+ R- Y1 ~4 e0 T, u7 Jusing namespace std;
9 V, ^2 P/ F3 {3 W1 K, Z  Yvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
8 l, H* ~! P' I8 L. `        {
) E3 s% G$ Z  y                int flag=1;
5 D: R+ [4 h. }- c2 o$ n8 K- G                for (j = 0; j < n - 1; j++)
% h, n- I" c( ]5 [                {
                        if (a[j] > a[j + 1])
                        {
  ]. d) z+ ?" z: |5 ^! }                                temp = a[j];
* z2 p; A4 |% S                                a[j] = a[j + 1];
$ b) E+ a1 e' K/ \7 C" ^                                a[j + 1] = temp;
2 z: K6 [1 x" g+ f" H9 _                                flag=0;
                        }
                }
                if(flag)
9 b9 r- @* s3 m  M                        break;
; X" l) m( o1 y! g$ x. e) A' B7 y8 y: \- p        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
{
& y) {- z& {5 c$ ~        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
5 A% p* i$ Q4 S4 q) R/ {        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
: J* a1 ^( [. a5 e" A' W9 @                BubbleSort(a,count);
3 M" x# M0 @9 ?8 [9 F        return 0;
' C" v' w. V1 L" A1 a) R}

( h# w/ d+ |; z; a那么再以一个新的数列来判断上述冒泡算法 的优越性
" q( q5 i. W* Z( e7 s$ Q3 4 2 1 5 6 7 8
1 o' i/ L0 ]0 A. ?# m这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

, D2 o2 ]7 @0 b: U#include <iostream>
% s. K( u$ j: N- e# d' Q/ h9 W3 G#include <string>
using namespace std;
void BubbleSort(int a[], int n)
4 z+ i& h" M2 ~3 f; X% I- W{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
& k% n3 G* R) q$ @        int last_exchange=0;
; L0 y6 N# A& n! g        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
, _  p6 E) R7 Z8 n                {
' h) l' C3 l& Z& l: X% {. q/ y                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
& c9 d" q5 t* h$ q. C                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;
5 B) R% i4 C  I( N                last_exchange=j;
                        }
                }
                Bubble_Sort_border=last_exchange;
                if(flag)
                        break;
+ H; l9 {' O* i9 W0 A% ~        }
0 P$ H& ^9 S! u2 T        for (i = 0; i < n; i++)
- h9 k7 N7 W1 Z                cout << a << " ";
}
int main()
{
        int a[8] = { 3,4,2,1,5,6,7,8 };
  E7 h" h* o, |3 J, z        int b[4] = { 0,2,3,4 };
7 }9 \' g, ?, Y: a# ^) s' A        int count = 0, i = 0;
9 j, N3 s. B$ |/ O- u        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
: |) z5 D& v# T        return 0;
" s* h2 ^8 w4 S' W- t. T: G}

7 Q5 D1 z% u6 z4 K( i! Y. h
: _2 M) J2 y& s0 m5 G到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
& ?% n0 `3 E& p, \0 e2 e基于冒泡算法，延伸出一种算法叫做

鸡尾酒排序
, Q% R8 O+ E( f鸡尾酒的排序过程是双向的具体怎么实现了
- n/ h* V9 |0 ^5 o% I. b% Z5 ~首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
/ E# g8 {" I1 K7 G& _# _第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下

/ K' |, a" r2 e8 F- ]3 O
#include <iostream>
/ g4 F9 X! [, D( x4 Q/ C. c#include <string>
using namespace std;
void BubbleSort(int a[], int n)
- h' ]' M5 x1 w7 F- v) ^! \{
! m( }; g% e! R        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
( ~. |9 m# s& u0 a        for (i = 0; i < n/2; i++)//奇数轮
        {
                int flag=1;
                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
% G6 d- [( n! A0 r* K8 n) c                {
                        if (a[j] > a[j + 1])
! p; C. A* t. Y+ E                        {
                                temp = a[j];
% e9 t; u0 z' s$ f& n5 m                                a[j] = a[j + 1];
                                a[j + 1] = temp;
% c, I2 V2 O3 S+ m0 ~                                flag=0;               
                        }
4 L0 I3 ~7 {) {- v) @                }
                if(flag)
                        break;
  // 偶数轮开始之前  flag 重新置为1
4 d" y6 E% g5 c( Y% h0 p                 flag=1;
/ i) j+ ^2 @( P" D' h                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a[j] < a[j -1])
7 v- X# i7 O* ^' B$ P+ E! C                        {
, |$ i# w7 q: Y- ?* S+ {& T6 b+ `                                temp = a[j];
                                a[j] = a[j - 1];
                                a[j +-1] = temp;
                                flag=0;               
/ Z& L/ ?1 F( H: ~/ f; J6 l/ G                        }
                }
* y* w+ Q$ N( w( i0 S* ?0 V                if(flag)
                        break;
% V/ C: {- k) q! Q; ~1 `        }
( z% Z- p. ?. m5 [) B  r        for (i = 0; i < n; i++)
, x2 V2 u1 D2 F% ]' o; X                cout << a << " ";
; B# X& q9 |; a5 @}
$ y# _! h- S; eint main()
: _' \$ a! j+ l+ o" R{
        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++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
+ ?7 c" `# `7 t1 H0 e# @}
2 z  V7 @) [2 F5 O1 l) P
& s4 J) e+ j' |" x$ A
1 C" ?! q9 `  X5 B- ]" g以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序

————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
% i2 a0 ]4 H6 t# y/ ?. p

9 ~4 u" C& v4 A/ d4 E% |, x( W9 _