关于冒泡算法的那些事儿

杨利霞

+ ^6 B4 }% U& l: c9 F- J关于冒泡算法的那些事儿排序算法的复杂度
$ p3 p5 z& Z5 A+ ^# g% H
8 f9 {( J* J- z3 a

关于冒泡算法你了解多少：
) L+ T9 _) C) r首先我们规定数据如下
5 8 6 3 9 1 1 7
9 N" ~, U8 X1 h: q
( K9 B, f8 P* B( h+ ~" j; W- O: z  q2 S在对数组进行冒泡排序的前提下，首先求出数组是否为空
! `3 `) j' S6 f* _1 S1 Y" F方法一：
1 u. F" p7 o3 e! t5 R/ D- C1 @如果数组是用vector定义的,即：
/ t- s8 R# ]# F% H* Avector nums;
//或
vector& nums;
，则这样写：
if nums.size() == 0:
) V/ |8 T& r- Z7 Y: A" @9 xreturn false
3 F3 J5 g9 G) `5 o( |方法二：
7 a" m* k/ h) P3 x; Y; Z  S" m如果数组是这样定义的，即：
int nums[] = {1,2,3};
' W' f- b* H! d& Z* B先算下数组长度：
+ e8 F$ Q6 ^: Znums_length = sizeof(nums)/sizeof(nums[0])
2 ]" Z. Z: |7 l: r  K/ U然后判断数组为空：
if nums_length == 0:
return false
( F7 p: N5 n1 i2 L原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

解决了上述问题以后，最原始的冒泡排序如下
2 N2 a/ @/ E' k
) N0 j' _4 y. O#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
0 j) S2 r  A9 S/ [. ~{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
) f# x( y8 q' K/ p: M- P! ~. H                for (j = 0; j < n - 1; j++)
9 u; ^! H% s  f' p5 R+ A                {
                        if (a[j] > a[j + 1])
                        {
8 R$ R, D$ C1 Q, E                                temp = a[j];
  O( b9 J5 ~/ |" x) a; C7 C                                a[j] = a[j + 1];
8 z) a" T0 m2 C- W0 I                                a[j + 1] = temp;
# p( G9 r( D: s" w! T  E2 O                        }
                }
0 R/ ?5 _9 [2 {( |        }
        for (i = 0; i < n; i++)
+ b1 x5 K' k5 G+ o/ x: g6 n                cout << a << " ";
( t* x' \" ?1 Z- g) s0 ^0 s5 z}
' Z- d" q* Z& M1 fint main()
{
        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
' k1 z! D8 H9 G9 q! e1 ?6 x: J$ p        int count = 0, i = 0;
$ F( R' Z! j6 H1 c3 w        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
6 d. D; L2 O8 ]% p, }4 f                BubbleSort(a,count);
        return 0;
% w1 a0 i8 M" q, I}
1 i- ~. E; v% m0 K
# ^! w( L4 `0 \3 D) ?3 r上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
7 [# v- [$ ~, I- }那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下

#include <iostream>
#include <string>
using namespace std;
9 c3 Q, \: f( k" avoid BubbleSort(int a[], int n)
: D( }  V! g. n8 h. ^  p: n{
$ H! p! g$ M. k# D        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
                int flag=1;
                for (j = 0; j < n - 1; j++)
' |: F( x; t4 Y! T: _( C- e; r                {
8 I9 I9 r9 t: f# V, n9 D                        if (a[j] > a[j + 1])
5 v4 m4 M( R. N                        {
3 G! @3 x* K. p  m6 M! r$ J2 A8 u                                temp = a[j];
                                a[j] = a[j + 1];
# q' b4 |' t$ F! _                                a[j + 1] = temp;
; |" R0 n4 j+ Z8 z. Z1 j- m8 m                                flag=0;
7 A5 U- r( Y# l& I  g                        }
( N; _- o# j8 T6 J                }
                if(flag)
                        break;
        }
; z" _1 i, n9 q& s4 n0 m0 p& h# U        for (i = 0; i < n; i++)
4 @! N) j- b0 u9 Y5 }% k/ ^                cout << a << " ";
; r8 v/ ?5 k- x7 ^. I5 t7 o# O& R}
/ N. U' Y2 I+ S  u3 u0 m2 \5 o% kint main()
  j  }0 m8 v( W0 q4 f- z{
, K: G- j% t2 D% D        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
' u" `+ L' M, L: N) {! Q" V        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
$ i3 T9 N- t4 H                BubbleSort(a,count);
, w4 H( j8 f( Q2 I: C) |        return 0;
. z% t$ W% o0 D" E6 Q- }% z/ k( u}
5 }8 l) ]% q( G: [2 w
2 |  C% W8 V% B0 M4 u' k0 P那么再以一个新的数列来判断上述冒泡算法 的优越性
( s* T8 S6 C  \. @4 W3 4 2 1 5 6 7 8
这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下
) S7 A5 v& w! p  b4 E' l
#include <iostream>
4 k$ X( Y+ d7 V* s% u- g#include <string>
using namespace std;
$ Q! U0 a9 n$ h5 m& svoid BubbleSort(int a[], int n)
& [6 s3 x7 ^: ]6 a" Y3 P{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
) u4 E* u7 ~! s! S: j) X8 T4 x, ?        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
                int flag=1;
) L2 X+ l4 ]8 g                for (j = 0; j<Bubble_Sort_border; j++)
- q0 H2 V' x3 O+ t' d+ {* ~                {
                        if (a[j] > a[j + 1])
1 N( t- H# L- ^6 \2 l: Z1 E                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
. T$ |0 H" h5 Z8 K' f& i                                flag=0;
7 j; ?3 P+ r3 ^# j8 v3 q6 y                last_exchange=j;
, |* q6 D+ A% r8 y. R0 V                        }
                }
$ [+ z' |, v) d( N3 {; G' y2 T# |0 K+ {. N                Bubble_Sort_border=last_exchange;
: h" D/ M; w) E/ b8 C  d/ a3 ^                if(flag)
                        break;
& v8 c/ Y: n3 ^& |2 Q+ q$ A7 a        }
        for (i = 0; i < n; i++)
; k1 O5 h* x* q& Z% a' |                cout << a << " ";
}
5 x8 S4 G$ }3 C4 H- Cint main()
{
9 c+ `  w: ?0 }2 w- N        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
4 D4 \) E" y# C! F8 E        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
$ ]2 H' [' q1 i1 i        return 0;
( [6 ^4 I8 M, y) d}
  ^' p, z# p: ~

) g* A4 a& C( _4 m: @到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
) ^: x- [1 `6 g; C1 @- s7 ]上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做
9 z1 z8 c+ B6 e' Y: U0 @( a
鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
. j1 h, R* f$ Y4 H0 Q% U第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下
# x  P( C8 g! f3 C* r* U
/ q  U2 w$ y7 `' y
5 a( \8 d2 i6 d8 Q4 I! c#include <iostream>
: M) b# p+ N9 H- O( F  d#include <string>
( U" _9 o1 ~* {& F" Susing namespace std;
void BubbleSort(int a[], int n)
{
/ ?) L6 |4 b! ?, E        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
        {
                int flag=1;
; N$ Q6 d. N( T9 o$ ^, z( n8 P                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
1 o2 L6 E/ Y. j) _8 b( _                        if (a[j] > a[j + 1])
3 q3 s$ {) n/ ?2 ~3 [4 [7 h- L                        {
- g% C5 h; v- h  F2 l                                temp = a[j];
                                a[j] = a[j + 1];
" B% u  y( B2 c                                a[j + 1] = temp;
                                flag=0;               
+ x- l4 N* S& V% a# {) l. O, F$ o                        }
/ R/ x" ]6 f# n0 @) b/ Y8 D5 R                }
                if(flag)
: u$ `; i4 G4 v                        break;
  // 偶数轮开始之前  flag 重新置为1
/ a) t6 Y7 c+ r' r7 d' _; Z                 flag=1;
  f& D: k9 @) k                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
( U9 c, U4 W# ?                        if (a[j] < a[j -1])
5 p. b7 }' X0 O  b1 H% j                        {
                                temp = a[j];
                                a[j] = a[j - 1];
                                a[j +-1] = temp;
4 H  |9 Y/ y0 f4 U0 a/ X                                flag=0;               
                        }
                }
, S: h, d0 b6 k- v" e                if(flag)
                        break;
        }
4 B9 ]/ H4 v+ a' B; t        for (i = 0; i < n; i++)
1 n4 Z3 c! ]- a  q, M) T                cout << a << " ";
}
1 ~; m& U2 V! _8 E' {int main()
: u/ L  u% m  V" s{
        int a[8] = { 3,4,2,1,5,6,7,8 };
) _; U- i2 Y& T2 ^        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
$ j4 c9 x0 j* O5 K                BubbleSort(a,count);
        return 0;
, o/ Z0 L; b# U}

8 A1 ^0 z; a7 d" C" }$ N
以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
) _. p/ V6 s  s# S- s8 G% y! c* y
————————————————
- M- b$ `8 u+ A) I版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524