关于冒泡算法的那些事儿

杨利霞

, O; t* a' }9 b8 _4 }+ g; I1 |& f关于冒泡算法的那些事儿排序算法的复杂度
' w  d# k' x$ D" K! X

/ h4 e- Q3 l3 p) d/ Z
关于冒泡算法你了解多少：
; c0 A/ I/ G* ^6 Q8 o5 y+ t首先我们规定数据如下
7 G. i" `* A2 X. t0 F5 8 6 3 9 1 1 7

在对数组进行冒泡排序的前提下，首先求出数组是否为空
& v* v+ U% c+ v  V方法一：
) G% x+ e, K' [如果数组是用vector定义的,即：
- z/ |% t, P, \: r& ~' u6 ivector nums;
//或
vector& nums;
，则这样写：
if nums.size() == 0:
return false
方法二：
如果数组是这样定义的，即：
6 W2 L& s/ q2 r9 dint nums[] = {1,2,3};
0 T8 ~( d# E9 h5 [先算下数组长度：
! H  ]3 t2 v/ Q* A$ {0 }3 \' Jnums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
if nums_length == 0:
7 `+ V7 n1 o3 u! oreturn false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

解决了上述问题以后，最原始的冒泡排序如下
; Q# e5 s/ ~  S. Y
#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n - 1; j++)
                {
) ~: ?. B2 w6 Q$ b/ c                        if (a[j] > a[j + 1])
                        {
( t5 f8 L6 H# {# s/ z# E7 s% w                                temp = a[j];
                                a[j] = a[j + 1];
6 V- i% W1 S8 e8 l! H                                a[j + 1] = temp;
                        }
                }
        }
' b3 N0 h! \) h7 t" a* G+ D" E        for (i = 0; i < n; i++)
                cout << a << " ";
- \1 B8 \0 q5 D0 v}
; W5 z0 h7 e, f8 L0 Tint main()
" m( G  V& o4 v6 a/ D4 }{
' G1 g9 Z4 K2 Q9 u' a1 N4 N; Q7 g        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
# v) u9 M- e# L1 ^& j3 W% k& C# V        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
+ R" Z4 ~( F+ f& @        return 0;
: x9 E% \; Y9 M+ |/ v  K}

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

. b$ H6 y6 N# A0 j* y4 y) b#include <iostream>
% t& W; f- {1 k, _7 y. D- w+ D/ I#include <string>
2 Z$ J& e: R; I; ~" c+ {using namespace std;
# r5 {$ _( H! [8 ]( |* i( Jvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
0 w1 m0 l3 T$ q. X/ z& P5 D  ^7 e2 I        for (i = 0; i < n; i++)
        {
; Q6 k4 I3 `6 _7 |3 M& [, l4 \                int flag=1;
; t) C  `' }2 `0 w4 G/ J- _                for (j = 0; j < n - 1; j++)
                {
& Z: u! z) \6 f+ w  P1 e( }                        if (a[j] > a[j + 1])
                        {
; V2 t, [: \$ v3 R' A                                temp = a[j];
. r0 p: R+ O( c) }+ }                                a[j] = a[j + 1];
                                a[j + 1] = temp;
" _4 F3 t' t& o% i0 y                                flag=0;
                        }
, u* L3 E9 l. w8 y: E3 Q                }
                if(flag)
                        break;
        }
* p5 Z" R  x$ J0 I7 I$ \        for (i = 0; i < n; i++)
                cout << a << " ";
6 a" \1 r& J8 J4 _7 ?( M2 l" L# K) V}
' L: }# n! N* ?. N* [1 b, q) cint main()
{
        int a[8] = { 5,8,6,3,9,1,1,7 };
9 l- U0 w' H, O1 g7 o! g        int b[4] = { 0,2,3,4 };
& ?1 e( b; r% J8 S7 O# u        int count = 0, i = 0;
5 ?; F3 K2 B; v; L8 C, K        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
5 `, ^! H% E( y5 u4 L}
0 g6 E- Z* W1 F. }5 n7 d1 g. }% V
那么再以一个新的数列来判断上述冒泡算法 的优越性
- z# v; ?: x6 U% E/ k3 4 2 1 5 6 7 8
这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

- {0 ?4 w- x$ K8 U" O3 k3 E#include <iostream>
* w& R7 K$ u& _9 Y- G#include <string>
using namespace std;
void BubbleSort(int a[], int n)
: O' ?5 w. J+ r% O' C{
* A$ l' e* O* b2 d. F8 u- s) R. G        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
3 s: P8 L4 W; b( M  C  H5 ?        int last_exchange=0;
2 r) c+ P( {0 x        int Bubble_Sort_border=n-1;//无序数组比较的边界
; c. ]& A$ i; \' ?; |        for (i = 0; i < n; i++)
+ l1 _- R. e4 {, Q) m% ~        {
                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
: M$ z' T) m" ~0 v* H                {
                        if (a[j] > a[j + 1])
                        {
! Z* R$ q  q& k0 _                                temp = a[j];
3 x! Y2 ?" I- K* @& R1 @4 ~                                a[j] = a[j + 1];
' ~. u1 l: L, A                                a[j + 1] = temp;
& }* ~" u2 F) }. M3 i                                flag=0;
                last_exchange=j;
8 x' [$ w( Z: l6 O5 J" N                        }
; y" Z. n: i# J5 \3 h3 l                }
                Bubble_Sort_border=last_exchange;
                if(flag)
$ \  Q1 n! M  v, x+ W7 H. K3 W" O3 X                        break;
, F4 X1 O6 U/ g( |3 c/ `        }
! `0 D; f- n' V8 h        for (i = 0; i < n; i++)
% X. g5 w% {7 x( l; o7 l% |                cout << a << " ";
+ b9 E9 I- ~' R; ]" B& w1 f}
6 {" g: q! @) P. F" N9 A7 W6 x0 Sint main()
{
8 e$ {2 f6 ~8 C) h        int a[8] = { 3,4,2,1,5,6,7,8 };
/ [, }; Q; x. i1 Z        int b[4] = { 0,2,3,4 };
! [; w# `, \  S1 W$ \        int count = 0, i = 0;
2 |& {' H: M5 s8 g  p        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
# d( P2 V/ x& O' U2 F. o2 @0 m        return 0;
}

' w; D) `+ g; T
$ H" Y+ `2 c7 P' p. }8 B到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
, m  v% X0 z5 M上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做
3 e2 g! X( }( E
鸡尾酒排序
/ z% U7 H$ R! ]9 m5 x鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
+ E( q0 o% P  W  Q第一轮，1和8交换，
2 d8 r% E- w) s9 ^3 o7 ]; k第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下

6 w* L, x! s- Z) S
#include <iostream>
" M' S! d5 e% m#include <string>
( z2 \0 f9 j' b# eusing namespace std;
void BubbleSort(int a[], int n)
{
) }3 G# Y9 R# U- {# r        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
1 M; Z6 z& u( K5 C, |3 [9 U        {
2 }% I( ?6 O4 h                int flag=1;
                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
  m! l4 C* P/ y) ^                        if (a[j] > a[j + 1])
/ e8 V5 \+ m2 ^$ \7 z1 O& C                        {
6 T; ?/ ~0 N: Z6 ~) h                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;               
                        }
! E8 ?6 B; O- a' J9 U                }
                if(flag)
                        break;
  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
& x. W7 F( d. G! |1 u# p                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
- X' ^) M! Y( Z2 M) \                        if (a[j] < a[j -1])
2 D) c$ X6 ]) D                        {
                                temp = a[j];
                                a[j] = a[j - 1];
                                a[j +-1] = temp;
+ u$ C' o+ a5 }# x, P                                flag=0;               
5 ^# g! }) m/ |4 ~$ }                        }
                }
& _2 H3 g, ]9 D' ]                if(flag)
! Z; ?6 _% x1 k0 _                        break;
6 s3 e( t! N  ]# ~# [$ j        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
{
/ ~, n/ v, W$ u* o) O( Z; T  E6 t        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
/ A1 U$ @" V  K& ]4 s        return 0;
0 l+ t0 R& a* J  `% `}

. K8 l% w- {7 X, e
2 \% j- \% `* s" M5 W以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序

; x' ?+ M' x+ f& G————————————————
0 \% O! c& J2 b版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
0 H7 Y+ t6 G$ w) o! M2 G, r

, o- C& l6 \7 t