关于冒泡算法的那些事儿

杨利霞

6 [, n- _- m9 t; d- |关于冒泡算法的那些事儿排序算法的复杂度
8 m) D/ b6 S1 f; I
5 W" T+ T$ D# R% D) n
" g% @3 t9 H, o4 H4 O+ R$ `/ U
关于冒泡算法你了解多少：
/ A# J$ b6 q9 ^3 u1 M首先我们规定数据如下
* h$ l9 `- q) A: G* A6 a0 _5 8 6 3 9 1 1 7

1 H( x) D* F% [+ j8 _0 J2 a0 A# d在对数组进行冒泡排序的前提下，首先求出数组是否为空
. \& z5 Q9 g; A8 v% N方法一：
7 `; J( E) o# z7 V# t/ V0 a" Y如果数组是用vector定义的,即：
vector nums;
9 C* I0 C8 A7 L& ?$ Y9 I//或
& R) t7 D# S! U" P" ?2 lvector& nums;
，则这样写：
if nums.size() == 0:
return false
5 E& `! G! ~& x  _1 ]! q方法二：
如果数组是这样定义的，即：
int nums[] = {1,2,3};
先算下数组长度：
) B% l- y0 U/ C: l9 ?" t2 |" vnums_length = sizeof(nums)/sizeof(nums[0])
1 n# \' J  v" }* m% ~' |然后判断数组为空：
if nums_length == 0:
# ^# j! q7 z+ ?return false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

+ E( @2 h" r  X$ U8 P4 u解决了上述问题以后，最原始的冒泡排序如下
3 ~* u7 t# m& f3 o* j/ }
#include <iostream>
1 l# c8 w( V  ]8 l( g4 l/ m' a( n  K  v#include <string>
; W. Y0 y% D6 |9 ^, [using namespace std;
void BubbleSort(int a[], int n)
" y6 I3 M. B2 W) z{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
4 T! D! c% T7 _9 H, \        for (i = 0; i < n; i++)
5 S% A4 T/ h) ~  ?        {
                for (j = 0; j < n - 1; j++)
$ P+ y9 Y0 F4 H- y; O$ Z# N                {
8 |7 x' i7 m; y* P5 V+ V( P                        if (a[j] > a[j + 1])
5 ]$ n+ Z. T- n% H! Z' d' J                        {
+ {' @" B+ ~  ~) E1 J6 j                                temp = a[j];
, [* P% d$ G+ X/ U9 r* T                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                        }
  N5 a( T, b9 X; H                }
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
* z5 F3 b+ _0 ]4 H8 \}
0 L/ F/ E+ |, _' n/ {5 gint main()
7 F7 s* x6 E1 @" ?{
* E; H; |, j+ W! G& Z        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
5 |1 j. ?6 {9 e( G& t7 e        int count = 0, i = 0;
& o: M. o& S. o  C' T0 G2 I+ n7 x        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
; d( Y4 L8 K' M2 o% @- T                BubbleSort(a,count);
        return 0;
5 T0 c7 z# |' i# c: G) z}

, M. d. w8 h; j7 \+ Y5 {! \上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
9 s! l1 [  J: N; n2 B; @那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
9 ~2 Q) t& U5 u/ C
$ R. c* P) _5 U! c3 j, F' }#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
' C- M% E7 m7 h/ K% b! d        for (i = 0; i < n; i++)
$ I7 C( w& ?6 ~0 Q" z, {- F! I. ~        {
* f' w, M' ~  q, V4 [, ~$ @  ~                int flag=1;
                for (j = 0; j < n - 1; j++)
6 j/ F) F1 n; ]                {
                        if (a[j] > a[j + 1])
" p2 M' @+ L7 F0 h2 l, P& l" X% b                        {
                                temp = a[j];
6 z1 Q7 u; q% n' M4 K                                a[j] = a[j + 1];
2 v$ f% ~1 s7 z                                a[j + 1] = temp;
                                flag=0;
                        }
                }
                if(flag)
8 [* c! B# _5 C1 [/ H; o% Q( G                        break;
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
% h7 P! Q! v% `  B9 J$ L3 [) u( }int main()
% y% ^% s/ S5 a6 S, U9 g6 Q! }$ O{
' V0 m4 J) ~! P2 M7 h2 S6 I+ v        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
, Q# B5 O2 q) D7 }        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
! }$ e1 H6 Y6 G9 z}

8 _7 s3 M: I+ ^2 P# b$ k那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
6 E9 w9 Z/ R, \此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

& s" k3 k, a- B9 P9 E#include <iostream>
, ]1 D+ a5 Q- A, i9 S$ x; R#include <string>
4 k% h9 S9 H7 U0 M4 Eusing namespace std;
void BubbleSort(int a[], int n)
{
6 k0 Z1 o9 y+ O2 b5 B- l2 l% K        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
1 A0 e$ o- ]1 D5 U3 u        for (i = 0; i < n; i++)
2 S5 p& B0 @" m# l3 h- m; n9 c        {
                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;
                last_exchange=j;
! _$ a1 `4 r4 Q9 |( R9 B9 R2 m                        }
                }
+ R0 N+ y* e' m6 R1 K& p, u8 {4 B4 f                Bubble_Sort_border=last_exchange;
                if(flag)
6 |6 b. [0 B5 b' y                        break;
        }
8 m/ I8 i4 _# q) i" f. ]2 Y        for (i = 0; i < n; i++)
- R: s" ~2 i; D                cout << a << " ";
}
# U# ^' s4 u6 l# e2 N" |; bint main()
{
        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);
! q2 a# G* \3 h0 q        return 0;
* t7 C0 C8 K3 A4 D}

+ `  I" |: E7 Q9 U
到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
- t3 V( _" d5 z8 Y; k) t& Z( ~上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做

鸡尾酒排序
& v8 i) S* D1 |& O- Z8 v鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
, R$ h% G( S1 y$ n1 ?& T2 Y; h第一轮，1和8交换，
, N# c' r8 s' j  h第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下

! |; ~* p. |& j) G8 v5 [, g) b6 m
#include <iostream>
! W( \# u, x1 y$ I0 s5 D: E#include <string>
- X& c* B# X, e6 J( c  j6 susing namespace std;
% j+ a- ?! p/ }5 d- ^# Nvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
( `. O& i! h) B& F! i        for (i = 0; i < n/2; i++)//奇数轮
        {
                int flag=1;
$ m9 _5 |2 d+ z1 Y1 `; b; @. {                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
: M0 q% ?& B; H5 C4 n4 D+ g$ @! R                {
                        if (a[j] > a[j + 1])
                        {
  ^* D9 M, j1 j) J- _                                temp = a[j];
% c5 k  z: E- ?8 H                                a[j] = a[j + 1];
/ d& I2 F/ t1 U                                a[j + 1] = temp;
                                flag=0;               
                        }
                }
  r0 R: C/ Y# u& D' U* d                if(flag)
                        break;
  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
- G( U& {0 e/ F                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a[j] < a[j -1])
                        {
                                temp = a[j];
/ ~, A6 ]( c7 F* w8 `4 L, a0 N% _+ q                                a[j] = a[j - 1];
9 x- N4 X7 Y, J& o$ ~1 D# z                                a[j +-1] = temp;
& m- i5 p5 P, V$ C, O5 g! N                                flag=0;               
0 G4 u' a0 r1 }% m, n! L% Q3 Q! k# W                        }
* N* K  S& _- E$ S                }
9 |$ c9 ?( d, ~" o# ]* K( a: w3 f0 v& z                if(flag)
                        break;
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
+ R* ^3 b3 k8 [  U3 Sint main()
{
  U+ g! v7 P& x5 z  {        int a[8] = { 3,4,2,1,5,6,7,8 };
5 W8 i' H$ F6 E1 G        int b[4] = { 0,2,3,4 };
8 T) J" D9 h* V        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
3 ]( A9 B$ ]6 D8 h( Z0 `) w1 k/ ?                BubbleSort(a,count);
        return 0;
}
* q3 G1 w0 L9 p- Z! I

" c' j; @1 W8 [: m$ U以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
) q6 {- y% P+ c5 X
, L$ ~: z- L$ @————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524

( B8 c* ~( s% u* C' t) c