关于冒泡算法的那些事儿

杨利霞

关于冒泡算法的那些事儿排序算法的复杂度

0 S" A6 s) C& f

关于冒泡算法你了解多少：
首先我们规定数据如下
9 C4 J- g( X+ B2 X. w) v7 G' d# ^5 8 6 3 9 1 1 7

# k2 @' c1 Z, R) C3 f! `在对数组进行冒泡排序的前提下，首先求出数组是否为空
+ K9 f8 ]) o# P方法一：
如果数组是用vector定义的,即：
vector nums;
, f* E. ^6 C% w9 M# ^//或
vector& nums;
. l: g! U; d  \5 O9 A4 }，则这样写：
9 u3 ~; x2 J! o; ?, fif nums.size() == 0:
( u+ r% s( v" i" r4 d  }( I# H: dreturn false
方法二：
" z5 f, Z  Q" g: ?/ y% K如果数组是这样定义的，即：
- [* ^) N8 c( F  a! @2 Iint nums[] = {1,2,3};
先算下数组长度：
. c! Q# a- B. j& t2 Inums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
" N% O1 K# I! e" F# a3 {" k) Uif nums_length == 0:
return false
% e- e5 D% b, ]原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

解决了上述问题以后，最原始的冒泡排序如下

- B/ T/ h% i! B. k& a6 f+ l#include <iostream>
/ F4 M3 H9 b% K' R. x; F9 f#include <string>
using namespace std;
% p6 S! f( V4 i4 @* N, z& lvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
" T) k5 Q! Q- ]" L        for (i = 0; i < n; i++)
8 h6 f5 ^) e7 M8 A6 o        {
                for (j = 0; j < n - 1; j++)
: a/ V  \3 _; f6 k' t: a. }' ^9 A                {
' Y0 `# v7 r* Y6 a5 d3 P                        if (a[j] > a[j + 1])
- m8 @! Y9 b) w9 T" W                        {
. N' S8 M( n8 ^7 i                                temp = a[j];
9 b, `, l3 t* M) L9 R# v0 _6 a                                a[j] = a[j + 1];
" e$ [8 f3 D; o                                a[j + 1] = temp;
                        }
                }
- r. R& W) t! ~        }
! A( _0 d2 Q4 l8 J2 i3 x        for (i = 0; i < n; i++)
% o: W" v" n+ q, K                cout << a << " ";
! U4 S4 L1 k7 @$ \}
0 i+ x, z) a" h4 Xint main()
1 R  [# S2 j; p; n& Z  P$ F3 b{
, A' q& _: U) S5 W! d! t0 y        int a[8] = { 5,8,6,3,9,1,1,7 };
# r2 E2 m* S6 G        int b[4] = { 0,2,3,4 };
7 P0 i9 |) U; l* |6 D- H        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
( c5 Z& T8 p+ Z" n8 C                BubbleSort(a,count);
        return 0;
& R1 [" ?% M5 F}

/ W/ m$ H0 {! b* u* W* d上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
! J4 a* m. w0 t# o那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
% R1 e  x5 t5 j+ O# l! a0 j. n/ V. E7 W
#include <iostream>
#include <string>
using namespace std;
3 d, B- M: D* k* T; H& f( S0 Lvoid BubbleSort(int a[], int n)
+ \' p! ~0 Q! r3 n/ l{
* _% A' I) z/ u# P0 O# X! m        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
0 x" V8 _1 e# |- x& T        for (i = 0; i < n; i++)
        {
                int flag=1;
                for (j = 0; j < n - 1; j++)
7 h0 ?& v& T% j6 _- B3 V                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
2 |; V* `. h9 j9 D                                a[j + 1] = temp;
8 a* |- r. O; B1 l3 _  t( U1 \                                flag=0;
                        }
                }
                if(flag)
4 O. g# [0 ]; K7 u) @) m  m' p5 k                        break;
        }
6 ~  _6 }! e, m) e5 ~. v6 [  ~        for (i = 0; i < n; i++)
                cout << a << " ";
}
5 ~9 B$ T5 Q' q7 H3 Bint main()
{
        int a[8] = { 5,8,6,3,9,1,1,7 };
" Z, l5 s2 ]7 I# P# K8 z2 a/ V  |        int b[4] = { 0,2,3,4 };
2 z/ Q: s# X) S  x( y; A        int count = 0, i = 0;
2 C! J9 u( o0 T        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
& ~' E! X, m5 A) l# v# ?: `4 i                BubbleSort(a,count);
        return 0;
  J! j9 j" U& Y}
3 P) |9 Y2 b$ u9 G- _% w
那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
8 u0 L, C+ F7 Q& S9 L这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
# S) Z) K7 T# y8 i; w2 Y此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下
3 X9 Z6 n4 v& `  a0 S5 n
$ j# V1 o8 F1 l#include <iostream>
#include <string>
  e" k& }, d" d; f) R) t/ J- Qusing namespace std;
1 u- a0 ^6 S& f" T+ _" R; _3 A, hvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
( a9 u, P% ~/ d9 w        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
! K2 p: y" N' a: h+ L1 U        {
                int flag=1;
+ J+ P6 _& [1 ]& ^* m! n                for (j = 0; j<Bubble_Sort_border; j++)
+ L- T+ ^) ~: U& ]6 M/ w( w                {
                        if (a[j] > a[j + 1])
                        {
: B) h/ d( [8 y: c                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;
                last_exchange=j;
1 v* z2 }. j" c6 i" U8 h3 t                        }
                }
5 c+ I0 K* ^& I% i                Bubble_Sort_border=last_exchange;
, S9 t6 f0 P$ o9 n                if(flag)
                        break;
        }
0 o1 m( B: |8 b2 w" [4 [! s, d) ^        for (i = 0; i < n; i++)
                cout << a << " ";
}
( e9 _' ]: n4 b3 _int main()
  T7 J' c! o: s{
3 |! j6 A- Y1 ?$ B% u. @        int a[8] = { 3,4,2,1,5,6,7,8 };
! i3 U" Q( Q2 l/ |8 ^        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
! J% p% M. p! k3 m) M4 R        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
2 M$ ], O0 q2 ?}
* a: Z& d: a2 _& n* c4 ]3 E
$ o6 E# G- s1 k8 a3 o9 V
4 R  ^5 R( a' j9 J$ G/ R到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
1 i9 u  ?; ~" L; w4 e  r上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
' X3 @. C4 r2 {# {基于冒泡算法，延伸出一种算法叫做

2 ]) f9 H3 @8 s' g鸡尾酒排序
0 e; U  n1 R% ~) u鸡尾酒的排序过程是双向的具体怎么实现了
  ?" L) \  ~1 I) x( ?9 H首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下


: o: c( C. a( M2 s3 B' t#include <iostream>
#include <string>
using namespace std;
% g) P# F8 U! dvoid BubbleSort(int a[], int n)
0 j3 Y' S+ y& `3 c{
* M, E* N* q( d9 q( `        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
* h& Y* G( K6 Z: x4 H) M        for (i = 0; i < n/2; i++)//奇数轮
  t, s  C, H& S- t% Z3 v        {
- F8 K" J/ R# D$ w# c; }- t  e                int flag=1;
                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
2 W  S0 k4 {5 A* U6 P                {
( e( o, J" S: ~+ Y                        if (a[j] > a[j + 1])
                        {
+ \& D1 b" B# l& t, K                                temp = a[j];
                                a[j] = a[j + 1];
3 c" }! W9 K2 D- L$ s- ?                                a[j + 1] = temp;
                                flag=0;               
                        }
                }
! @9 y' e* H1 r6 k) X: d. y                if(flag)
                        break;
8 T9 P# i$ s7 d' {7 m$ B  // 偶数轮开始之前  flag 重新置为1
3 h9 [: T5 m6 @; K+ F                 flag=1;
                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
  a' ~3 o( ^) l# a2 ^- D# B, _                {
' c. J& ]# E8 W                        if (a[j] < a[j -1])
                        {
! ^6 r1 ?# z3 ]# A: y  H6 b                                temp = a[j];
# ]5 c9 M) D" b; I4 `# W9 H                                a[j] = a[j - 1];
                                a[j +-1] = temp;
, u7 D! J% r& L5 m2 C7 D6 v                                flag=0;               
) f& L/ H( D7 x" K                        }
5 {0 X+ B. H1 D( V$ n' e# ^                }
7 b9 j' j+ M0 E7 S8 E& Q2 U" f                if(flag)
) m. x: w2 p) U5 x7 m6 L                        break;
        }
* g4 B5 D" O, U' i        for (i = 0; i < n; i++)
" x- y- S# @# E- |- \                cout << a << " ";
4 q2 _9 r6 G- q}
int main()
; [+ D% {5 n9 {) [7 f2 y{
        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
. ]& t; z" R- s5 o9 P3 X: G        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
. d) E9 M# b) `% H$ c                BubbleSort(a,count);
        return 0;
: u* o- G- J1 ~9 W3 b$ c6 M" ]}


5 s! b# m1 t# o/ M1 a) g以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序

3 ~6 T0 x' ~& k/ {: [' C————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. n) R; y" _, P; l$ P0 o原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
$ F- S$ X! j% |