关于冒泡算法的那些事儿

杨利霞

6 ?- b' |& ~/ L4 S2 k5 J2 F关于冒泡算法的那些事儿排序算法的复杂度



关于冒泡算法你了解多少：
' P; g) w0 o- D) G首先我们规定数据如下
5 8 6 3 9 1 1 7
! i  w, }! |' \# [# s2 y% L( B
2 V' d  Z6 j, x6 \  {6 |* m在对数组进行冒泡排序的前提下，首先求出数组是否为空
: ^0 R( v0 d  t8 k方法一：
6 d3 R/ E0 P6 ~如果数组是用vector定义的,即：
1 ]/ w: `4 T$ z; U1 r3 ovector nums;
//或
; s5 m* C6 l, M9 a+ wvector& nums;
，则这样写：
if nums.size() == 0:
return false
; T5 e2 k+ G/ T  K3 O( x5 [4 e方法二：
6 ~5 l  }6 i5 I; b$ v& i1 Z如果数组是这样定义的，即：
int nums[] = {1,2,3};
先算下数组长度：
7 w+ U  z% S; S! y: z, Y% V* cnums_length = sizeof(nums)/sizeof(nums[0])
" o* |; }, D/ }: f0 @然后判断数组为空：
) T; I. ~# C  c1 R% N, Hif nums_length == 0:
7 @6 m2 ^6 p& _$ @return false
# |& G7 i0 n( [, k原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544
+ I, f6 ~$ D& _- h% S& c; q5 O
解决了上述问题以后，最原始的冒泡排序如下
& C3 D! J3 {" D. n; ?3 O: U
2 N1 i7 S/ `# s6 [* o#include <iostream>
#include <string>
2 S- m" ?, c" e7 }3 i& |9 {3 d. q3 qusing namespace std;
8 A- A) ^& r- evoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
7 `5 p7 U4 l) A. g$ j" ^        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n - 1; j++)
/ M- w% d2 O# z$ n                {
                        if (a[j] > a[j + 1])
$ s8 f4 @; J/ c' Y! I7 Q) y6 K5 c                        {
                                temp = a[j];
                                a[j] = a[j + 1];
  [1 x! k" v5 _# ~: m( f' `( |& H                                a[j + 1] = temp;
( s! R9 ]0 q6 k: E6 g8 d                        }
6 i2 k1 ?3 c" k3 n* r( q3 E: G9 Y                }
        }
        for (i = 0; i < n; i++)
: R' d1 t# b8 r' H; a                cout << a << " ";
( p* n' i# ?- i# Q" z7 `}
% k) x: Y/ B, w# l* Gint main()
; N7 m% U  V: G- I, t{
        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
- W( g) L/ ~/ I2 I+ v- K' H( d1 h        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
9 Y4 l/ k) n+ O: L( v5 v) }4 {                BubbleSort(a,count);
- Z. ~# b1 W& e9 p  ?/ I        return 0;
& i0 L/ a0 J& {2 I}

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

/ z7 C8 f4 h) Q7 i0 j( S#include <iostream>
% r$ _% z# H& `1 Y" V' K( i& y#include <string>
using namespace std;
void BubbleSort(int a[], int n)
! m0 U  u% k+ ]# |{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
6 U5 u( s7 H/ M1 r        for (i = 0; i < n; i++)
0 r. M3 v2 b0 E. F; ^9 ~        {
5 u3 O; }/ \* ~! Z" t. y  K8 _" G                int flag=1;
                for (j = 0; j < n - 1; j++)
( |! C$ D' M( i  |- h2 i& ?) U& g6 ?: y                {
7 B' b4 I9 C& D                        if (a[j] > a[j + 1])
: X' P7 T! w$ q9 x$ s. B                        {
0 y3 r2 [8 b# @1 X0 ~, X# k                                temp = a[j];
$ w' b3 j4 J3 a- Y                                a[j] = a[j + 1];
# g" {, R: j; T* U7 y$ Y                                a[j + 1] = temp;
; ~* H/ R; Y4 s' [                                flag=0;
+ J- u! p* v% w8 O- i# ^( M                        }
6 V! |  F' F1 _( c! i- f& S                }
( L4 f, Y" t0 A0 O8 o! `7 ?7 C                if(flag)
                        break;
5 T# U( x: h. {* v* }6 p9 w        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
1 v+ O! y$ X4 E6 \2 _{
0 [- d7 h$ ?; M        int a[8] = { 5,8,6,3,9,1,1,7 };
5 ?8 K6 j) Q! O1 H( b; I# C        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}
& X$ g4 T! q* H# H  ]4 q
那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
( F! E( U, L/ S9 N% x这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
. I9 _4 b3 j) ?+ h# v* |% c  D7 E此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

8 r+ v" i6 Q; b: h% i! e#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
                int flag=1;
# k$ S3 V3 O1 H0 r                for (j = 0; j<Bubble_Sort_border; j++)
                {
6 x8 `' Z4 x# B8 j0 q                        if (a[j] > a[j + 1])
; w4 K/ |2 A0 b% w( w. @, [) x                        {
                                temp = a[j];
5 q8 Z7 q' a/ F) j. k                                a[j] = a[j + 1];
2 W+ [; l& X, t" ~6 p. ^9 @                                a[j + 1] = temp;
' j1 d! P( O. y3 `                                flag=0;
: B8 ^! t7 Z) g  W( P* i                last_exchange=j;
                        }
  E: d. U7 d; [" y                }
6 f4 K% x% E8 b) M  u                Bubble_Sort_border=last_exchange;
+ ]( X0 c* T6 q6 L. }# ?/ a6 L                if(flag)
% D9 p4 X# q/ y6 C                        break;
        }
        for (i = 0; i < n; i++)
. Q, g# P' T+ n8 \& W+ Q                cout << a << " ";
}
# }* N/ |4 e! C5 pint main()
7 A5 x2 x5 ?, j% v! q( u4 @+ R: c$ _{
        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++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
; n# i0 M; ?8 [. q                BubbleSort(a,count);
5 ]# M  Q! U( i9 I. K) ?( D# t        return 0;
( Q2 Q- V3 D( n' X1 a5 k9 j& h}


到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
; V7 o: _7 V2 p8 E上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做
& ~0 o8 g" M7 A5 {
鸡尾酒排序
4 J1 p# p% T* P1 y- t  |3 s鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
0 E* @* ^( Z9 S. a8 f第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下
* l0 ]7 S. q7 |" `2 ?# g
; v% H# `, X5 K+ c) q/ \3 U% A
#include <iostream>
$ v$ Z% G8 q& _$ Y#include <string>
using namespace std;
8 T5 t! a- o) M* T3 P1 w/ kvoid BubbleSort(int a[], int n)
{
* C. r& J8 l$ w: g3 ?5 l        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
        {
2 J7 f3 M4 D8 [9 I                int flag=1;
                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a[j] > a[j + 1])
% R! ~3 U$ u7 K5 U! t' r  G                        {
2 ^& }+ B( _8 Q8 a- m! z8 ~                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
' x1 R6 \4 g- l  Z. X                                flag=0;               
9 q1 y- m( W4 y# ]" g( I7 {$ v                        }
                }
                if(flag)
                        break;
2 T: d, U4 g& m$ n0 h0 x  // 偶数轮开始之前  flag 重新置为1
+ l, ~# W: }( N2 `  @0 H                 flag=1;
8 `2 v5 Y0 C  Z1 z% \- r                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
1 ^$ e6 d  n- W& G3 y, o- I4 z                {
7 E( ^; l. L2 N3 f3 L                        if (a[j] < a[j -1])
2 e/ T+ c  x  w                        {
% y2 w: K( x0 K; n; |6 `. j                                temp = a[j];
+ J8 ]: [1 v9 q$ h# E0 a                                a[j] = a[j - 1];
                                a[j +-1] = temp;
! X2 }5 m% K, j                                flag=0;               
                        }
                }
- c5 _5 J; h" P, _; v                if(flag)
, Q  ^( S" b# g* r3 f: w9 E                        break;
        }
$ C7 U5 O# V+ i: b; x' ?        for (i = 0; i < n; i++)
                cout << a << " ";
2 i6 K" h! |0 |9 ]! v7 m0 ]}
int main()
{
        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
7 y; p( w2 D3 M* o1 A        int count = 0, i = 0;
$ z: x2 u, c3 }# q5 s4 Y- Q" Z, |, E        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
0 f( ^* y; d1 d* j, w        return 0;
4 _, z5 ]4 @: P1 Y}
! }' e) v3 }$ m; j" N
* {+ P6 s$ e" Z" N) d3 o. H8 \
+ k( H' n: D( e9 \- R以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
$ `2 l  H8 |& ]+ Q+ Z
6 I; J6 }+ ]3 n. k+ l————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524