关于冒泡算法的那些事儿

杨利霞

' \# ^0 q; \" }关于冒泡算法的那些事儿排序算法的复杂度
/ k* G7 ^! B% N# P+ p! F& P5 R. G
& {1 F5 s2 ]$ l: ^

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

9 ]( D" J, w8 H( b在对数组进行冒泡排序的前提下，首先求出数组是否为空
. H; x4 E+ B9 E8 p: u. G方法一：
如果数组是用vector定义的,即：
  ]+ Y. _6 B3 K! W) R4 Q' Wvector nums;
: I5 z7 }) B0 K6 |+ c0 K/ l//或
/ S2 k) S, b- k" ~9 k" \vector& nums;
+ \' U' E9 n3 c& v) z' l0 |，则这样写：
if nums.size() == 0:
return false
方法二：
. T# J: |* g  `3 o0 ~  c如果数组是这样定义的，即：
int nums[] = {1,2,3};
, P. |/ c+ b% a4 @1 B1 j4 R$ C先算下数组长度：
nums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
4 o6 h7 k6 p) \) kif nums_length == 0:
0 M1 G- `- Y1 oreturn false
/ P) c5 w4 [( R0 X; y4 v- C原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

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

#include <iostream>
3 E: s+ K' v# Y1 _' p8 T#include <string>
, V9 W4 p7 v; A, @7 s1 \& husing namespace std;
  t( k0 q6 i* }' uvoid BubbleSort(int a[], int n)
* x) l( Y+ f, ^7 x; I9 o8 r0 u3 g{
0 K4 e0 A+ F2 a) k$ \" U% S4 ^        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
, z* R: n1 q* Q, _% y" \        for (i = 0; i < n; i++)
        {
& h" u" c5 m  d+ y2 T                for (j = 0; j < n - 1; j++)
                {
! B7 {2 Y1 `/ l  \% O! |' E2 d& X! B                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                        }
" L' _; s! J2 D& U* h( N                }
        }
        for (i = 0; i < n; i++)
$ c0 H# u, W; j- L6 c" o6 w                cout << a << " ";
}
$ i9 R0 C/ ~. X2 ?/ e; ?$ aint main()
{
& C$ i. k4 a' e% E- k        int a[8] = { 5,8,6,3,9,1,1,7 };
        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! l0 u2 T  R}

  L6 V" |# K* L( J/ y: F, W9 \上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
! |+ r9 n, J3 u* h7 t4 }那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下

#include <iostream>
4 X/ a( w) P6 X4 `1 Q& e0 T9 M! O#include <string>
( I; ]/ o9 S4 {5 R/ _using namespace std;
2 ^, E: t1 u( Evoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
* K. U, _7 ?& Y) A& n. F        for (i = 0; i < n; i++)
( }' D, p' O- M        {
0 s  Q* Y! k$ s* W) g2 |( r$ a/ c3 C                int flag=1;
2 [: C( N9 R2 ~/ e  m! k  n                for (j = 0; j < n - 1; j++)
' v5 m7 S& g4 @" ^                {
% h6 y9 t/ O7 g9 C4 `# C. A# ^6 X3 {) ~                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
+ f+ O2 N, y& m                                a[j + 1] = temp;
                                flag=0;
                        }
                }
% F% d- Q% s  e$ c5 H3 ]5 J                if(flag)
                        break;
        }
        for (i = 0; i < n; i++)
( X2 ^  ]% T8 U# U7 w* _% `. s                cout << a << " ";
}
6 Q, Y0 c0 {$ q9 r( E' k: e& oint main()
1 }  I9 I" i. Z{
        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
7 Z0 _( g5 F7 M( i  O4 W/ w' Q        int count = 0, i = 0;
5 N3 ^" h7 b  H6 ~' c* m& N8 n        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
9 X# Q) Q- @  w: v! Q  Y. H        return 0;
}

. {8 }3 P2 C1 R7 P8 F那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
1 Y9 R! ?6 q* m( a这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
  p! E9 V4 F( |  P此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下
& F' C9 U# F5 E+ j0 Z
#include <iostream>
#include <string>
4 s1 {  ^- y5 x4 g% q0 Fusing namespace std;
: o! N0 [1 H" Z7 Q( ]( j7 [void BubbleSort(int a[], int n)
# u1 J: @  X5 S1 W+ O{
( v8 f6 P, r. L# ]        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
% j$ u8 W1 i5 u# W        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
/ p$ W7 j4 y- Q1 E3 X' z% |                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
6 _! p! N4 [( o, P0 {7 Q$ ?/ w4 ~                {
                        if (a[j] > a[j + 1])
                        {
, ?( C0 A: L. H% h2 u* s8 b                                temp = a[j];
# k* d3 P; R; Q: t2 Z7 P                                a[j] = a[j + 1];
( D4 G  ]- F/ Y3 O0 M% h  F                                a[j + 1] = temp;
; G* e7 f* f. Y( X                                flag=0;
                last_exchange=j;
                        }
                }
                Bubble_Sort_border=last_exchange;
1 L1 D3 b3 t9 V) y$ z                if(flag)
                        break;
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
7 d, |, t2 C. g& I. {8 u, i- h0 v}
int main()
' Y  t  U% E' L8 w' w0 _" y{
        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
7 J- G" b2 `) d( a8 x, j0 }" B        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
2 C6 e; U* I, W' A- [# I                BubbleSort(a,count);
        return 0;
}
" \) U1 I- d) j
3 a& m- s$ Q2 W2 F
8 G% D% P1 z: o. b到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做
% Y, m0 w  {* O4 ^
1 a& E- M- h; P& q7 d8 k鸡尾酒排序
6 y5 ~7 R  I) c) ^鸡尾酒的排序过程是双向的具体怎么实现了
, g1 C, k* p$ K" C1 l$ h5 b. e- w, H首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下
( V( k; g0 i( N. _/ X: C. n! Z* N& B

#include <iostream>
* S+ A' P, ~- Z) U# {% U; R#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
% v+ X; v9 |$ ]- G$ e) Y        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
& u, N1 ~, m  E/ Y9 j: P( C3 l) z  ~        for (i = 0; i < n/2; i++)//奇数轮
# G- y/ D/ s2 X+ T4 s        {
0 j2 E! K! d4 Z7 a; T5 v                int flag=1;
2 }1 M: Z4 K! ]( C7 g                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
( d$ h# P) v4 L# g7 V8 }                {
                        if (a[j] > a[j + 1])
  u( r6 s# z2 f' D0 j$ c. |, w                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
. o5 `2 w" X; O9 O                                flag=0;               
5 K+ n: L, d5 c# @1 ?                        }
( b! a" A+ a/ D! _5 O/ k* c                }
                if(flag)
" u9 d: n/ |8 }- V9 K# ~                        break;
8 w  i! O+ ]" C" x/ i& I  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
- z' T- h/ N2 c) O  r$ g) B. T! E+ a                        if (a[j] < a[j -1])
7 u) g0 q- A/ S+ v7 N                        {
; m. M2 s' j9 O* H                                temp = a[j];
                                a[j] = a[j - 1];
                                a[j +-1] = temp;
7 p, _. E# a; h7 q2 g# u                                flag=0;               
                        }
                }
                if(flag)
3 @6 L9 s- [* b7 N# p, V1 c                        break;
        }
2 @2 h; |8 d+ N0 {8 R        for (i = 0; i < n; i++)
                cout << a << " ";
% ~, I# N: m% i; V- T# ^}
1 j6 x2 \6 z  t7 A' Kint main()
{
        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
6 _: i, h% c; f- O2 X1 B( G        int count = 0, i = 0;
2 `* W( t% N+ L2 K1 p        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
6 h' }% f) m- P+ T3 m; X        return 0;
}

' K& [# ?% _) \) l
7 v: B! g( o/ V' w以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序

————————————————
  }6 f) P, v6 `- Y) ?# s  P版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
' P% O8 u) @9 k4 G: e原文链接：https://blog.csdn.net/delete_bug/article/details/105928524

) c3 J  t3 e) F1 y, \) B9 |