关于冒泡算法的那些事儿

杨利霞

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


$ A' v( r: r; I* k9 N
5 d$ [2 L* O2 }3 e, K& d! f关于冒泡算法你了解多少：
首先我们规定数据如下
9 V  C1 i9 ]$ s5 ]5 8 6 3 9 1 1 7

在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
9 k# o9 z  `. C+ v. f$ }  g5 g6 ^如果数组是用vector定义的,即：
# `( p: [) J/ @  `4 uvector nums;
//或
vector& nums;
" M& p& q* w. ~7 Y$ H，则这样写：
: L7 I# K$ [% Q+ y" T- u1 {: r* e6 fif nums.size() == 0:
return false
方法二：
7 _+ p* d$ A  T1 e. S9 O如果数组是这样定义的，即：
int nums[] = {1,2,3};
3 @# I7 N/ v/ i: r' n先算下数组长度：
nums_length = sizeof(nums)/sizeof(nums[0])
; j. b: P2 V# h7 p8 }/ w: W% S. W然后判断数组为空：
% |7 n! W5 @) r7 D; cif nums_length == 0:
" \/ ]9 l! ]' [; U' \return false
+ _" B  C+ S% e原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

4 j: h( {7 y7 v- X解决了上述问题以后，最原始的冒泡排序如下
& _6 R( f7 e; B; d, e
- ?% c9 K/ a  L& ?/ _7 d#include <iostream>
#include <string>
$ g$ D# r2 O8 N4 \% zusing namespace std;
1 b* k* V, n+ m1 ^) l* Lvoid BubbleSort(int a[], int n)
{
; T' f) H% x6 G0 f6 J        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
( d) `+ D) R: T9 J        for (i = 0; i < n; i++)
        {
. j- L) Y2 O( N1 v                for (j = 0; j < n - 1; j++)
* c; C1 ?3 ?5 L1 _! E5 T                {
                        if (a[j] > a[j + 1])
  v/ F4 E, I% y8 H                        {
                                temp = a[j];
' m' x  D4 W0 s4 n4 f% s+ L7 A                                a[j] = a[j + 1];
4 I$ Q* }0 A2 ?/ T6 Y8 H, J                                a[j + 1] = temp;
                        }
                }
7 |8 g& O; J  p- m0 n& T3 k        }
        for (i = 0; i < n; i++)
9 i" n1 z5 r# f( R8 \0 d9 _                cout << a << " ";
5 Y% o' W; W" _$ F/ i. E: @9 S' A}
int main()
, Q! v6 L+ ~7 P+ K# N0 c- {{
        int a[8] = { 5,8,6,3,9,1,1,7 };
* C4 e% w8 F* d/ V7 ^, B        int b[4] = { 0,2,3,4 };
. x! m% [" v! q) j1 j5 }% k        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
% X7 k) n2 V* V& ~+ C+ i                BubbleSort(a,count);
        return 0;
4 e3 V/ l( Y. r  [}
5 a9 d' ~6 E9 ]; t! }. I
上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下

#include <iostream>
; w- h  c4 Q* @! s, d! V#include <string>
using namespace std;
8 k% N2 z- T$ r# c$ \8 V  k  z0 rvoid BubbleSort(int a[], int n)
- ~# w! S6 F* k$ b5 v1 ]: Q& y{
- @2 {& p0 U' P6 B0 `        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
$ b) k) E; u& c4 W+ V) e5 }: ~$ o        {
& k' P1 [3 [- N$ v9 u$ s: i1 w! N6 `) u; \                int flag=1;
                for (j = 0; j < n - 1; j++)
                {
                        if (a[j] > a[j + 1])
                        {
4 r. R7 e9 \8 O8 C! Z3 l0 D                                temp = a[j];
                                a[j] = a[j + 1];
* `' r0 y8 Y0 u) B; V+ q; m                                a[j + 1] = temp;
                                flag=0;
; I0 y. V/ h2 U5 i- d                        }
( J' C8 t4 V4 S0 ~- x8 }' p7 [                }
0 Y4 I. N, }4 _0 `; Y. |4 u                if(flag)
                        break;
, h' k1 q2 Y9 @" N# L2 ]8 s        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
8 V- j. F8 `. ?- p6 Iint main()
6 `* p# Z4 Z# V4 M* v{
) Q8 h5 {- d- B4 c6 P1 X        int a[8] = { 5,8,6,3,9,1,1,7 };
+ T, Z6 ?# z$ m8 d/ l        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
8 j* j3 k$ {( d  ]/ `: W* l4 F" l        return 0;
}

0 z( M+ e) H3 |1 }8 x% \8 i! a那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
& l! \! e0 {6 x此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

#include <iostream>
  C0 u0 r3 \' _$ }9 P2 C#include <string>
using namespace std;
0 G/ [; ]# m* }, vvoid BubbleSort(int a[], int n)
+ g# J7 F$ t, f5 J{
9 M9 N  f& s; C% V5 F/ k1 m: I        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
5 @3 A* F7 `7 s1 t$ x        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
9 F4 P3 w" o8 ?$ `" J9 O        for (i = 0; i < n; i++)
        {
$ S  S! U0 K- W: J. ^9 V                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
. \  h9 r- ~1 V8 I6 K                {
8 W% G0 R* u% Y; Q. t                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;
                last_exchange=j;
1 x4 z" I; i; k0 [                        }
) ^+ U' A* h* ^' k- w7 A                }
                Bubble_Sort_border=last_exchange;
, l& l/ Q: Y1 N2 r                if(flag)
2 u* f+ s' U1 U( }                        break;
2 J! O- ?( q# h. G9 g% \        }
8 ^9 E0 K" P: ?: L! A        for (i = 0; i < n; i++)
3 c, H; ^: x0 R. h5 H& x4 Z                cout << a << " ";
}
: _6 y, Z, ~# k  T5 Z0 {int main()
{
        int a[8] = { 3,4,2,1,5,6,7,8 };
) T! k' D4 c$ u2 S        int b[4] = { 0,2,3,4 };
; |: f  k1 u* g        int count = 0, i = 0;
+ P. W4 }* C+ c5 Y; e: X6 N0 s8 c        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
) p2 ?' z5 r/ p" L+ @& G                BubbleSort(a,count);
        return 0;
}


% O/ H9 \6 J& S8 d- I4 B' k到这冒泡算法就结束了吗，不可能，你在看看这一串
/ @4 h. }4 |. t- u0 }5 w2 3 4 5 6 7 8 1
: X- U/ Q( I0 [8 w上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做
1 V& I( j- A( \0 B$ A
" X6 o  t! n9 ^+ v鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下
3 T9 i/ H* y4 S

1 Y6 m8 w: |* q+ t. p1 p& i#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
8 |! x4 w: q6 r( D        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
        {
                int flag=1;
% V/ t0 n2 `' l6 H3 m7 }# A5 E9 {8 N/ x8 z                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a[j] > a[j + 1])
                        {
7 w4 Y) M3 M, h, M: |0 Y0 \                                temp = a[j];
                                a[j] = a[j + 1];
' w( P/ ?9 C9 @. O/ r0 @                                a[j + 1] = temp;
% w; d" ]- `* r/ K( k                                flag=0;               
                        }
9 A1 ~1 p; L) l                }
                if(flag)
; T) C" Q# u; Y, r) B( m- [* [                        break;
  // 偶数轮开始之前  flag 重新置为1
, c1 ~1 Y9 B9 _9 _; [3 k                 flag=1;
+ `9 a. @% f6 l: E* G# X/ `                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a[j] < a[j -1])
                        {
* t4 R# r3 s* u: K! J3 p" E& S1 i                                temp = a[j];
  u7 ?% s% ~# y                                a[j] = a[j - 1];
" n& T& |0 p7 I0 G& a$ m' H                                a[j +-1] = temp;
1 n" G) E) b+ j+ h$ E                                flag=0;               
7 j: E4 x8 U9 B# d. i                        }
                }
                if(flag)
' k0 q/ b* B% Z+ E; Q) ^0 e                        break;
        }
2 K3 r4 Q9 G' Z# a        for (i = 0; i < n; i++)
' W: p$ Y* n4 V) r! ]: N# \$ w                cout << a << " ";
}
0 s+ D% a8 |. c8 B+ Q( Dint main()
8 s2 o/ P7 R* `( V{
        int a[8] = { 3,4,2,1,5,6,7,8 };
$ X/ b; g% w7 ?3 O) M8 ]        int b[4] = { 0,2,3,4 };
9 C* ^0 P2 M+ e        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}


  |2 `/ ~/ s. f: l以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序

: r& G5 V9 X$ `$ N" w————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524

" P1 n3 r' U, D; p& F6 c: B$ ^4 m
5 D, ?5 O1 B9 H% c/ O& k