关于冒泡算法的那些事儿

杨利霞

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

- l7 l4 P4 y9 ]
( F8 D! u" G8 H% w+ ]2 L2 ^- p9 V( R
4 v" V+ q3 k# v( m) ~6 y& V关于冒泡算法你了解多少：
首先我们规定数据如下
5 8 6 3 9 1 1 7

, ?# M3 B& @1 \/ Z" ]在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
9 t* n6 {( p& T9 ?1 N9 g7 c' v如果数组是用vector定义的,即：
vector nums;
//或
( }' t/ V7 `: Z1 @$ [vector& nums;
，则这样写：
if nums.size() == 0:
# n# a# @$ ~: N9 k% j9 zreturn false
方法二：
如果数组是这样定义的，即：
int nums[] = {1,2,3};
先算下数组长度：
& H; U! M; }+ Q  C5 V2 h0 T( q  _nums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
0 i8 `  b; c# ?$ @7 n/ }if nums_length == 0:
8 S* x4 V8 |/ z) ~4 Greturn false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544
8 U2 o  I& `- \, p( [
解决了上述问题以后，最原始的冒泡排序如下
3 u: f$ B* F9 A1 [: B
#include <iostream>
#include <string>
8 }5 D- N& K& h1 X- W/ g6 zusing namespace std;
, U4 K8 T6 Y$ N: G* L8 ~; q" }void BubbleSort(int a[], int n)
9 z8 [( o6 E% P{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
  `9 V; A+ ^- q( I        for (i = 0; i < n; i++)
/ ~  a! C0 b8 ~; o& f# _        {
4 q- }) f# x' n3 }' s8 @3 l( j                for (j = 0; j < n - 1; j++)
) H' O7 v. M% I                {
                        if (a[j] > a[j + 1])
# J# R' M; L) z& u. m$ W- n. U) v                        {
                                temp = a[j];
& C+ @7 d1 T' ~                                a[j] = a[j + 1];
                                a[j + 1] = temp;
( N/ @; E) r. C1 O" G4 m3 s, k% h                        }
                }
# Q$ M" i: j$ q7 l, e* m        }
        for (i = 0; i < n; i++)
                cout << a << " ";
0 X9 W& N: G) w: s0 m- N0 T4 w  q! o! `}
; }: }7 H5 x$ r( P$ M  \int main()
{
        int a[8] = { 5,8,6,3,9,1,1,7 };
" @0 C! @1 y0 |% Z        int b[4] = { 0,2,3,4 };
$ `& }( l+ u0 r6 e        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}
% {& X, `' R4 S5 h  C
上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
1 H, U( ^. t& l2 M3 R0 R那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下

#include <iostream>
" F: N9 F5 \/ J, |: m2 L#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
0 I( {& n* C3 }7 a; m4 F        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
# V0 Y9 W5 g; ]        for (i = 0; i < n; i++)
        {
0 a4 u4 C- o8 A4 n                int flag=1;
                for (j = 0; j < n - 1; j++)
                {
                        if (a[j] > a[j + 1])
  p1 E8 X1 v' U3 T% `& V! W                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;
                        }
                }
                if(flag)
                        break;
        }
- _- p* U9 }# g! h) \        for (i = 0; i < n; i++)
. t8 L) Q' v: e4 {                cout << a << " ";
}
int main()
{
# S9 f0 w( f/ `/ M. R7 x        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
- F# f& M& L- q% [        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
% n% |; n0 K6 C        return 0;
}

那么再以一个新的数列来判断上述冒泡算法 的优越性
5 B  F% h) N' z. b! c6 ?9 B! Y7 ?3 4 2 1 5 6 7 8
这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

#include <iostream>
#include <string>
8 {7 x1 v- `8 ousing namespace std;
  V1 e% E4 m$ G' x* j' x$ Kvoid BubbleSort(int a[], int n)
{
% j0 B9 X7 _# e9 I        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
1 _" k* B3 n% C) |        int Bubble_Sort_border=n-1;//无序数组比较的边界
  Q$ g4 P  m/ f, d0 t, r5 _2 G        for (i = 0; i < n; i++)
        {
+ _! K! L  i5 M$ |                int flag=1;
; q: u2 ^2 p* [9 f                for (j = 0; j<Bubble_Sort_border; j++)
8 x' C2 O3 B3 j, _, i7 B/ J/ p                {
                        if (a[j] > a[j + 1])
1 D/ h8 v6 O1 e  ^1 x                        {
                                temp = a[j];
$ J8 [; z8 H( o3 r                                a[j] = a[j + 1];
9 U. K7 h- }# ?  v                                a[j + 1] = temp;
( z. b/ x) P; V2 e                                flag=0;
. U5 f, y; A- Z. T- o) B7 c                last_exchange=j;
                        }
                }
0 r3 ?. K! O1 [, q. b+ W                Bubble_Sort_border=last_exchange;
                if(flag)
' b0 S+ l( L9 }4 [$ H4 W% u) }, Y                        break;
. j" q5 E% H" @" S6 ~* x        }
# r' t  B$ J8 G) u" y% T        for (i = 0; i < n; i++)
                cout << a << " ";
}
( n* K  j! y1 C& \/ B5 Gint main()
3 D! {; A: D" G9 ?$ X# F2 W{
: w& F! n, m- T7 w3 ?        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
5 _3 ]- i$ A) K        int count = 0, i = 0;
3 m' X# M' g5 H: ?        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
* E  Z' C$ h  ?* |1 t1 Q/ A/ P# A                BubbleSort(a,count);
        return 0;
# a8 ~: O# }7 o) V/ }" G}

+ W2 ^1 z4 H. F2 }, r* l
% v1 A% Q+ K& C& k到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
5 s- a# p& }8 {6 w5 b基于冒泡算法，延伸出一种算法叫做

鸡尾酒排序
! b2 P6 o, B( M1 X' p. x3 i鸡尾酒的排序过程是双向的具体怎么实现了
' x) B( J& |( A: i& Y6 z) _$ s首先正向还是向冒泡算法一样的排序，
. F, u$ p0 V8 H% k) }4 n第一轮，1和8交换，
/ P& c- i# a6 F3 l: O) V7 s) h第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下


#include <iostream>
#include <string>
' Q. a; ]) f  f" v$ q' Ausing namespace std;
void BubbleSort(int a[], int n)
{
3 _; ^6 W; H4 }        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
  K; Z0 |5 c# o3 |# X3 k* y        {
                int flag=1;
, J# H2 x% p6 y  E                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
2 _; W& H3 ~% C+ n$ K. B* x                {
) u2 n4 w- m0 s% Z) l1 l  I                        if (a[j] > a[j + 1])
7 Y! s: z' ?9 T                        {
                                temp = a[j];
9 n* W& \! j& b, Y: d) }                                a[j] = a[j + 1];
                                a[j + 1] = temp;
% M% l6 E2 S" M8 {3 I                                flag=0;               
                        }
                }
5 o- P; M% H. ^  u  M. H                if(flag)
" b5 |9 s. L1 O; L* y/ i- G% A: c, ^                        break;
  // 偶数轮开始之前  flag 重新置为1
+ a2 Z9 O1 b0 k) b0 s1 O                 flag=1;
                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a[j] < a[j -1])
) d5 `5 r- _( v1 @1 q                        {
                                temp = a[j];
* U) n( J2 H# s                                a[j] = a[j - 1];
) _6 I2 U6 w: K6 h& V# Q6 z: N3 t) C                                a[j +-1] = temp;
                                flag=0;               
" `7 Y  C4 C* \5 ]% L! |  e3 }( s3 v                        }
( }$ B, [# t" l# x! e  t5 @- v                }
$ a/ Y% i+ T1 N( t6 w7 D( B                if(flag)
; ~# `( q' s$ ?2 `- b- s7 W3 o                        break;
+ }. I2 \1 `1 i+ @7 j        }
        for (i = 0; i < n; i++)
                cout << a << " ";
. X1 Y% n$ O% G* R. F}
$ q0 q! O$ s8 B* }int main()
8 m, m3 ?2 ~/ \6 L% J{
        int a[8] = { 3,4,2,1,5,6,7,8 };
0 ?9 Y& H: m9 A5 O        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
4 w- e$ C, ^! \' e                BubbleSort(a,count);
0 N7 o& ~0 ~4 J        return 0;
2 C3 z- u( S; M5 L0 V$ ^2 V9 m}
, i! F5 J% |! b" g

# }! D  u# `$ Z# I2 e9 J' o- b以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序

" _( r: X/ v! i4 p+ K————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524