关于冒泡算法的那些事儿

杨利霞

. M. P% j5 j* Q' W6 e: G关于冒泡算法的那些事儿排序算法的复杂度
/ D4 a/ V  [, r  A! d% s% @
; n  V  i2 S& u1 L+ V

关于冒泡算法你了解多少：
首先我们规定数据如下
5 8 6 3 9 1 1 7

在对数组进行冒泡排序的前提下，首先求出数组是否为空
! h' d. Y$ I2 `5 S方法一：
4 y0 V- x. g; r$ O  m如果数组是用vector定义的,即：
vector nums;
. e0 j, Z) H- m) A$ K0 `* N; J//或
" J! C) p4 b7 v! yvector& nums;
，则这样写：
5 t' Z% ^& Y) B+ Y/ ~if nums.size() == 0:
/ [! ~2 z& b7 Y; L4 u! A" j! a8 treturn false
方法二：
( ?6 A% Q' n/ B如果数组是这样定义的，即：
int nums[] = {1,2,3};
先算下数组长度：
nums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
if nums_length == 0:
1 @2 n; P' q9 n3 C/ d: wreturn false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

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

#include <iostream>
. K; F, Q: o( I+ \) I#include <string>
using namespace std;
; q0 m( O6 H* C! |# Z/ jvoid BubbleSort(int a[], int n)
{
$ C& l: h7 E" e, e) f4 j        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
9 j- t( i7 s& U$ \% ?- O1 ^1 Q        for (i = 0; i < n; i++)
! G3 |! Z: e: u1 ]$ d7 p        {
                for (j = 0; j < n - 1; j++)
                {
                        if (a[j] > a[j + 1])
                        {
  G  N  A& }; \6 x2 [1 D                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
( F2 b1 i( _# r* n' {                        }
% E: ]6 G7 u  N& O; }4 h                }
        }
        for (i = 0; i < n; i++)
3 k  u6 ^% K; }& a; {' x/ Q% n                cout << a << " ";
}
- w7 i: A. b" ]0 @1 C1 Xint main()
{
        int a[8] = { 5,8,6,3,9,1,1,7 };
' K( `0 X& a4 i5 @- n0 [        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
( _( _$ P- r7 h0 Z7 D5 t3 x2 g7 d) Z        return 0;
; l# W: ~( q1 J+ P}

上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
5 R/ I1 a' t1 T  t' r
#include <iostream>
0 r! B3 g+ R4 u9 S4 L$ E#include <string>
using namespace std;
0 k  v' n; [2 Q- l3 w  X* A! l9 q: Ivoid BubbleSort(int a[], int n)
{
% p# Y! p' M, q8 P  p* P3 o        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
" p: h; c& @; a9 r' \        for (i = 0; i < n; i++)
- V. v" u5 ]/ l        {
                int flag=1;
# r; ^. i7 v8 D, g4 f$ x) a                for (j = 0; j < n - 1; j++)
0 C- r( c1 G; P                {
                        if (a[j] > a[j + 1])
4 Y0 {0 {6 b8 e  G9 [                        {
                                temp = a[j];
+ u( D4 {  r, ^% @                                a[j] = a[j + 1];
9 I/ ^/ A% R0 Z4 s  k/ O0 ?                                a[j + 1] = temp;
- v% C6 k# h( p+ ~                                flag=0;
                        }
                }
3 V. k4 K( q8 r$ p5 ^                if(flag)
                        break;
$ D) L6 m: Y# r" p$ `% v        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
" ~. a  j/ t- v0 p: d' o/ i' yint main()
$ H# d4 i! o2 H- O" S{
4 R8 o8 t4 `7 p3 u: }  u3 k( m. X        int a[8] = { 5,8,6,3,9,1,1,7 };
+ Y  B4 v% B* K2 w6 F) e/ c        int b[4] = { 0,2,3,4 };
; f7 o6 S4 q% t# Y" O        int count = 0, i = 0;
, F( ^- ]. D5 h' ]4 G        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
/ @7 a) C5 n! r$ e                BubbleSort(a,count);
  ]6 E5 [- f: W3 n8 P2 {' B! l. [        return 0;
, g: M* W- L- W- E}

$ V6 y+ W9 J$ M( O) Z那么再以一个新的数列来判断上述冒泡算法 的优越性
7 c  b$ i! s* _2 G1 c; m: K3 4 2 1 5 6 7 8
- z7 p/ A6 K' D3 v这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

#include <iostream>
#include <string>
6 m9 T' `. s# Z5 N3 r6 Busing namespace std;
void BubbleSort(int a[], int n)
2 ?: Z9 q$ j9 s& ]+ p' k5 M4 N{
& P5 e7 I1 ]3 S+ L' s: F9 s1 `        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
) a' Z8 F/ S6 f% I. R' m! K2 N        int last_exchange=0;
4 d, X- f) v0 J) K: y" A, k        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
: |) Q, l3 _+ j3 k3 {) o" Y                int flag=1;
4 }$ H) Z/ S4 G0 z( m8 I) P/ d                for (j = 0; j<Bubble_Sort_border; j++)
                {
3 }0 n; i& ^5 i& y8 h                        if (a[j] > a[j + 1])
3 i( i" d7 x) E8 Y: ]( Q0 |  t                        {
                                temp = a[j];
) x; G/ c) N/ t, p1 i                                a[j] = a[j + 1];
                                a[j + 1] = temp;
6 `% [1 L! ~+ r7 _4 ]0 d% T3 F  R3 }                                flag=0;
                last_exchange=j;
                        }
                }
                Bubble_Sort_border=last_exchange;
* l4 s( Z  i: q                if(flag)
                        break;
3 J$ _. d& o6 l7 U( j, M; M0 r        }
        for (i = 0; i < n; i++)
                cout << a << " ";
3 A# C' z) \+ F  S7 N6 L$ ^}
# O( n) w* l$ ^! u8 B& f; _: [0 eint main()
: A; i0 S% c. o" ]- X{
8 j, k, i) l4 @$ z6 R4 a        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
. ?. \: k' p' F, O. b. o2 t        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}
, {/ ^: q* q" t  E" L5 @' s* q

到这冒泡算法就结束了吗，不可能，你在看看这一串
% ^% S7 E! H. C- C& D2 3 4 5 6 7 8 1
4 n+ m2 I& X5 Q6 g4 o) {上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
5 I$ E# q# b  W, X( X/ C基于冒泡算法，延伸出一种算法叫做

  {) r3 k& G4 v3 o1 R" \/ Z, \* }鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
6 Y7 g0 Z; Y+ P6 S6 \. P首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下
* R7 W2 V& }: ?4 D3 p7 \% C

2 ~+ m# d7 a0 H3 b#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
( G- v6 q  V+ ]1 m        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
  I3 S* w2 g" H, [, i9 a  H+ g        for (i = 0; i < n/2; i++)//奇数轮
0 x2 D' a- W) _2 R9 u- ?        {
: o& [7 u8 I; K( ^0 P0 s                int flag=1;
& b4 I' L: m) A6 S# _. D: W# J# A                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
8 m& B9 G1 I$ B# Q9 X: k; a                {
9 Z- j, e/ Z" B7 q+ h% K0 L                        if (a[j] > a[j + 1])
6 o- T- i- o- i                        {
1 q( i9 p* x: Y; y                                temp = a[j];
                                a[j] = a[j + 1];
- Z2 Z8 K3 J& K  M                                a[j + 1] = temp;
                                flag=0;               
                        }
  a; I% r6 D2 f' ]3 k7 c                }
' V9 b* L5 H4 R) C9 J8 J6 }1 W- J1 @. k                if(flag)
                        break;
  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
) B. J% H3 D9 A$ z2 ^                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
) W6 c% M  f5 O  D. k                {
5 G: S$ y  }: C* {                        if (a[j] < a[j -1])
                        {
: x) a5 S( f% O$ |: u                                temp = a[j];
                                a[j] = a[j - 1];
- L  b8 y3 l% w' V! q2 m                                a[j +-1] = temp;
1 ]* q4 ?9 _# y- s7 s, m! B+ g; Q                                flag=0;               
1 q8 l, L2 r! P+ K0 Q8 u                        }
                }
1 w9 T1 X: f5 n  V                if(flag)
                        break;
        }
        for (i = 0; i < n; i++)
1 v; m: S) C) q" v* ?1 G                cout << a << " ";
}
int main()
{
        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
. e# a6 K+ u5 y2 ^        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
5 D; ~8 a" h- V- \                BubbleSort(a,count);
7 G" Z, c" z; \# V5 o) g% L1 J  n        return 0;
: P% n3 p( ]( R/ m' `}

+ S4 o5 I4 S# J0 g
# i: a7 C4 C. T, D以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
! z% s# ?' s% Y
————————————————
0 m2 g2 i6 C3 ~% W* i/ ]版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524

4 _$ e3 x1 W" @& s
# [! l( j6 ?) l0 g