关于冒泡算法的那些事儿

杨利霞

关于冒泡算法的那些事儿排序算法的复杂度
) g6 r  w1 n' w7 `( s- n7 r# ~! O( w

2 ]0 B7 u( @$ [" B9 |% s
关于冒泡算法你了解多少：
  Q  i) h4 g- ?/ f, K: W' A3 G首先我们规定数据如下
2 K6 L* {3 ~- l: g5 W( J1 R5 8 6 3 9 1 1 7
  K7 u% o, z2 F8 \
在对数组进行冒泡排序的前提下，首先求出数组是否为空
8 G* o% U; E  B方法一：
  d6 B; L) x1 m9 v8 u, T# Q* ]5 g: q如果数组是用vector定义的,即：
vector nums;
- W! [' s4 {  J/ l3 o//或
! S  |* Q4 N* ~+ _! R9 Jvector& nums;
" i  _$ O. O3 N( F! @/ B) T，则这样写：
6 \: N4 t, H/ U/ ]1 e' [if nums.size() == 0:
return false
方法二：
如果数组是这样定义的，即：
" o+ h" j2 {* S0 T' f: Hint nums[] = {1,2,3};
/ E0 U9 @- }) N' i: Y+ m# l& Q先算下数组长度：
+ J- N' y1 C) S9 o5 Bnums_length = sizeof(nums)/sizeof(nums[0])
1 [' ^! C) x' K* R然后判断数组为空：
$ d3 V9 x+ S; m' {8 Q3 X5 }6 kif nums_length == 0:
! M5 v8 x8 v- Z0 C& sreturn false
6 i" c  \3 u3 ~) E. Q原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

0 W$ g  {# K' P! \) ]  Z  I1 B, O解决了上述问题以后，最原始的冒泡排序如下

#include <iostream>
5 p, c% f0 _! {9 h- Q! L#include <string>
$ d% d5 \; S' Z; s% G+ E4 iusing namespace std;
void BubbleSort(int a[], int n)
{
9 ?, y( n' y" m        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n - 1; j++)
8 J0 H7 X' f; o+ b2 l2 j                {
! K* e/ T* s" u, l/ j2 q  L                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
1 V6 u2 D9 _1 Z' h" P9 q- d+ v                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                        }
                }
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
2 O2 d4 J7 u6 ]7 h- k  f7 fint main()
{
8 l5 l- U- p! R1 Q1 e        int a[8] = { 5,8,6,3,9,1,1,7 };
- |7 M6 ?4 U  @/ F$ j5 ~        int b[4] = { 0,2,3,4 };
- E; [1 i6 n+ Z! Z0 Z  |        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}

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

) S2 A5 Q' d) h4 a) B) n#include <iostream>
. b7 g9 x) m% Y4 a5 ]) C- p) S#include <string>
using namespace std;
9 ]9 p" N% W, {! j1 yvoid BubbleSort(int a[], int n)
{
* j; l9 |: m" t+ P$ Y        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
/ t7 ~; c" {! O        for (i = 0; i < n; i++)
! x( [" k  x8 c7 z! O. A- N+ E        {
                int flag=1;
. R. C- e$ c2 h5 A6 h                for (j = 0; j < n - 1; j++)
                {
3 J# `6 C$ X! v- _5 j+ J; `% _; q                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
! P7 h' |- ^/ v) k8 Z, Z# h                                a[j] = a[j + 1];
4 L0 e0 _- q0 O" M" ?: t2 c                                a[j + 1] = temp;
                                flag=0;
. y8 q! z; E3 q" ^% E( U4 N                        }
                }
. ~2 z" ~4 U/ \& s/ U                if(flag)
                        break;
- Y8 v+ V* t  d; |  Q! }( U0 k        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
) Y6 i$ v0 q1 Vint main()
{
) Y. ~) N4 j( r5 B  A0 q        int a[8] = { 5,8,6,3,9,1,1,7 };
/ q6 O( B2 `/ ~        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
$ \0 X" @. j! q" G' B        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
- o0 A; `+ {  a/ O; y! X}
( w6 G$ o" G$ g/ R
* n/ }6 x+ [9 x! ~( w5 f那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

#include <iostream>
" c# i& I* ?4 z' a" s+ }; _4 E#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
2 u! H( }2 o" o# G- Q        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
0 s6 u/ w( o  `; f$ C; n                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
$ O! o( F: o( m4 r                {
                        if (a[j] > a[j + 1])
                        {
2 h% z% d6 z' a9 d/ x  a6 V                                temp = a[j];
* L6 U+ n8 D3 |- \! I% ~" |& _8 g5 @                                a[j] = a[j + 1];
3 W' N( ^* b2 Y* O5 U                                a[j + 1] = temp;
+ |+ T1 h, r! Y! e# ?4 V/ E                                flag=0;
                last_exchange=j;
                        }
7 v5 O. R  G$ U8 ?1 q                }
5 A" L$ X$ q5 O4 u" W( C                Bubble_Sort_border=last_exchange;
1 [' s3 [  ]" Y! Q) `3 F                if(flag)
                        break;
% ?1 A3 ~$ \2 P        }
: `4 c( X: l8 n0 R        for (i = 0; i < n; i++)
8 Q" H  u) l" W- s% t                cout << a << " ";
- w( ]# I0 w. R* v' T9 Y  H0 Q}
% V5 f0 r' E9 B4 w& Z. k7 Z4 D5 F9 U) tint main()
{
! a3 `7 ^( C) c, s; t) [% ~$ k* n        int a[8] = { 3,4,2,1,5,6,7,8 };
2 v9 s& \8 m5 N6 z" e6 A* Q' f        int b[4] = { 0,2,3,4 };
# U9 `9 d( ?* L8 T        int count = 0, i = 0;
4 L% O2 J1 K* l! v; Z        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
, Y  C7 }3 T5 }  k5 W        return 0;
}


3 a/ u/ C! P! {0 E7 s到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
4 B' I4 @! X; o4 ^, H基于冒泡算法，延伸出一种算法叫做
! P2 g  l! K  ?# C8 F
$ w' u: Y' g% O& |0 j: W% u$ y$ R& i鸡尾酒排序
# ~* ]  x  L% h* n鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
+ V  l4 G$ p; d  ^. c9 G2 p. o第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下

1 F1 I0 B- m! A) h
#include <iostream>
4 \% l$ g8 [  A  |#include <string>
* o, _5 v- b7 h" zusing namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
: y; C/ o# k9 K9 X        for (i = 0; i < n/2; i++)//奇数轮
& Q2 e0 X, z0 r& X$ |6 i        {
                int flag=1;
                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
6 M( Q* p( q* Y5 o' F! p7 w# }4 E, w% `                {
$ B- \% j. w/ S, O1 j                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
5 P/ d& K" [7 q) k. [                                a[j] = a[j + 1];
' h6 o( n1 X% O. o                                a[j + 1] = temp;
                                flag=0;               
                        }
/ M' n9 K3 `8 g- H7 C8 Q                }
8 x! j( `  k: c                if(flag)
                        break;
  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
1 Z1 @9 n4 L/ m+ C  ~5 @4 f                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
7 P# H6 m3 g* I                        if (a[j] < a[j -1])
' L9 l0 v* h$ z0 \4 s9 x0 F2 Y" W                        {
8 N3 ^# `  `# H) v' O                                temp = a[j];
                                a[j] = a[j - 1];
                                a[j +-1] = temp;
9 t' Q% q3 o  d( J                                flag=0;               
2 `. [3 X' {, Y/ `                        }
                }
- c2 A6 }2 w# i! f- v                if(flag)
                        break;
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
4 s8 h. X: K, D}
) U$ }- j& Y9 xint main()
{
7 y9 S% [* m; r/ e        int a[8] = { 3,4,2,1,5,6,7,8 };
- r* j- y8 r2 D/ d3 ^+ E        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
4 r" Z" `! V* Q& [) R- y* @7 d                BubbleSort(a,count);
1 ^2 z  V6 l# b4 @/ l        return 0;
) q/ E- K/ q) E' Z' M}
" k0 D" ]9 ~- W( w& U; o

以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序

————————————————
$ u: g; B+ {) ~  M7 `- @0 ^7 I版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
( y  S' E# B; l* X7 Y! J( f: n原文链接：https://blog.csdn.net/delete_bug/article/details/105928524


/ y! E6 T9 e- Y# Y4 }