关于冒泡算法的那些事儿

杨利霞

关于冒泡算法的那些事儿排序算法的复杂度
3 K5 J- N& @+ n5 x2 f: L

* \  o) |' }6 B6 x$ Z5 q# g. h' `
% \- }: l: o6 |5 X9 n关于冒泡算法你了解多少：
8 M7 U$ I/ d1 D4 o首先我们规定数据如下
5 8 6 3 9 1 1 7
3 v: @( b/ y2 D2 T+ V/ h: B
7 E4 \: C( k7 X在对数组进行冒泡排序的前提下，首先求出数组是否为空
$ a3 i+ r; D4 c+ ?8 C方法一：
如果数组是用vector定义的,即：
, `& ^# L: X0 Y1 t, nvector nums;
//或
( w* Z& S: d( _vector& nums;
8 Z% \. u2 _6 R，则这样写：
+ F; F/ N, `5 }( [" iif nums.size() == 0:
, a3 e* l! w% U: greturn false
  H. ^0 G+ Y8 R" J3 ~方法二：
如果数组是这样定义的，即：
6 Q1 U% d' e1 Kint nums[] = {1,2,3};
5 J- S% X2 m5 ~先算下数组长度：
nums_length = sizeof(nums)/sizeof(nums[0])
! S  Y" d8 H( ?# F6 ^7 `, J2 ]然后判断数组为空：
if nums_length == 0:
return false
; L5 j' ?( g4 |; C' y( C; P5 I原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544
& A4 w2 U+ U7 \" V, h4 m& @
" @( V5 B+ D5 [* c解决了上述问题以后，最原始的冒泡排序如下

' n- I. |& {7 j* k#include <iostream>
#include <string>
using namespace std;
; J$ R- @; i) Bvoid BubbleSort(int a[], int n)
" c: b: x- T5 n) Z8 K{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
! ]6 a' |5 e& X" a5 }        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n - 1; j++)
                {
                        if (a[j] > a[j + 1])
4 \/ [& L& t; n! e1 H( ?$ i$ [                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                        }
  t4 b9 i, N, `0 g! B                }
. o/ m4 B7 I  ?( g6 z  e+ x( }- c        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
. t2 I" T, y# Z! F- Sint main()
# ~, C) t! N4 k. ~; c3 o{
        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);
0 t/ t* b% Q& g5 E' g        return 0;
) c. }) w. m; T1 {6 F4 i# g4 [% P}

上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下

3 v: B3 ~- e6 j4 _4 f#include <iostream>
#include <string>
using namespace std;
" a* ]8 [0 ]  v& Y( M+ P- |  M6 Mvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
- f. A  u8 p" \/ i' m  [- e                int flag=1;
* J6 t1 D" l# a7 B% }; |                for (j = 0; j < n - 1; j++)
/ N% T9 ~. j" w2 r                {
                        if (a[j] > a[j + 1])
, b/ m& B) J; ?! ?6 c; Z- O2 M                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;
                        }
                }
8 T' z9 @' ~. z1 B+ z9 ?                if(flag)
2 g8 A& t6 ~" E8 p2 L+ _4 R                        break;
( v" `  |& C3 g; \0 f1 A4 f        }
        for (i = 0; i < n; i++)
5 e5 B$ Y% G  b* M                cout << a << " ";
}
int main()
( R7 g$ \5 W2 j3 }1 M' P# _{
# a( l# @# n# C2 R& Q        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
; }6 ]+ n' i( m" D3 ?! p7 p3 ?        int count = 0, i = 0;
1 U* b1 i+ k# K# @. {! ^        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
4 U. J4 R: ~: w, M- S* Q$ H8 q5 i                BubbleSort(a,count);
8 l: y9 e( d# a( J! W: Q7 \        return 0;
}

那么再以一个新的数列来判断上述冒泡算法 的优越性
3 B0 o" k7 k3 N( K2 L1 j! K/ i( l: Z3 4 2 1 5 6 7 8
4 H( H  `1 m, H6 |. @* R这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
( T( G; C9 }: h此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

#include <iostream>
#include <string>
5 C/ `; F% L2 _, N2 u9 iusing namespace std;
void BubbleSort(int a[], int n)
7 R; L% Q' H( h! x. F- K: |( x{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
9 F. c2 S! y. z1 T# z( y: p        int last_exchange=0;
* S2 u) k" L* s1 ]. ^* B  B7 |8 O4 S& v        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
0 g6 E- Z  P0 c( ]        {
                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
5 u/ M4 z1 I4 d  l5 G+ C! M                {
                        if (a[j] > a[j + 1])
                        {
' x) F9 A2 p. {( ?! H3 ^6 r                                temp = a[j];
  m8 E* [" Q, b2 }1 u$ b; u  M* d                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;
" u2 A7 M' ]- F3 q6 o                last_exchange=j;
# d$ z+ P2 H# V5 q                        }
                }
* I% q) I7 v2 t1 `( ^/ ]# T                Bubble_Sort_border=last_exchange;
                if(flag)
# r& J/ s, S- o4 w                        break;
: v) y$ [9 S: v& u" k3 E        }
/ I8 O7 o( x4 e- P2 V, R5 m/ O3 }        for (i = 0; i < n; i++)
0 x- @4 c1 c5 S) s2 g                cout << a << " ";
3 g2 S7 _/ a& q2 e. I2 J" ^& |# g. v# K}
int main()
{
        int a[8] = { 3,4,2,1,5,6,7,8 };
- k/ ^- q0 S" o% q7 q& y$ [& n5 e        int b[4] = { 0,2,3,4 };
' g* Q- K+ b! ^1 [        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}

0 N4 h0 z' c" w' c
到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
) v7 O- W4 g9 l7 X9 D基于冒泡算法，延伸出一种算法叫做
8 ~, N: [* H! `1 m
鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
: ~! S$ p% j$ e. t第一轮，1和8交换，
/ E' j+ [9 B! }0 A第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下
+ L1 P5 z. p1 i# B7 Z7 l
: Q5 R( D' y9 Z! K7 ^) [- N
+ Y" ~8 B( B  z: o. b#include <iostream>
2 Q1 @- J5 o- I; r. J5 d#include <string>
& P3 Q; l" C2 }- `using namespace std;
0 a9 W1 r$ q! q9 I0 svoid BubbleSort(int a[], int n)
{
5 d% d! P  U* D        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
1 R4 {0 U/ _7 _- {" T        for (i = 0; i < n/2; i++)//奇数轮
5 p" L7 B8 D0 F) I' A0 M" ?        {
, m( x% ?5 {/ V/ m$ T- a7 B                int flag=1;
8 I( |, c3 }' p5 F+ _' t                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a[j] > a[j + 1])
                        {
* f8 O7 s+ D- o; M$ c                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;               
                        }
                }
                if(flag)
3 V/ k+ Q4 p. G/ [# o. o1 i                        break;
  // 偶数轮开始之前  flag 重新置为1
9 J% z& q9 F" [6 @, J7 V3 H                 flag=1;
8 i7 B1 n. N- W+ G$ [4 y0 U: k                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
6 z+ q1 ~2 M  q6 h) E) x6 g                        if (a[j] < a[j -1])
                        {
  l3 o% i$ N! E" x7 n# G                                temp = a[j];
                                a[j] = a[j - 1];
                                a[j +-1] = temp;
8 v3 s- ?( p# d; Y                                flag=0;               
                        }
                }
0 A# p1 O& q7 T4 A                if(flag)
* n5 F7 `" C1 X, W! O                        break;
$ u  {2 K. U/ ?9 M- Y        }
( {, [3 z7 Q! j4 n- b9 \        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
: W7 t6 S' g' X# G: b{
        int a[8] = { 3,4,2,1,5,6,7,8 };
" n( k, b+ @. h; p# d        int b[4] = { 0,2,3,4 };
0 t; Q( @2 H5 X0 p# ^6 Y# M- z        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
$ f6 W0 P  e* _5 j# E( A5 p; y  ~        return 0;
}
4 \0 }( ~0 c! r8 [

以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
& x' i% B" {. `2 b
————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
7 n) ]9 s$ x3 z0 [/ o  J