关于冒泡算法的那些事儿

杨利霞

5 f  @# w7 E/ Y+ v3 R关于冒泡算法的那些事儿排序算法的复杂度

0 Q8 ^, O* Y: X/ E9 N/ I4 U7 X

4 T6 y6 B0 ^5 s4 g2 I' g关于冒泡算法你了解多少：
6 A; m5 a7 A0 G4 g8 t首先我们规定数据如下
5 8 6 3 9 1 1 7

在对数组进行冒泡排序的前提下，首先求出数组是否为空
7 M# _- T1 z7 Y5 H0 a4 v方法一：
如果数组是用vector定义的,即：
vector nums;
- M" s' m6 P  R8 A9 ^! y5 u//或
vector& nums;
( x+ T0 [! d# s, A  @4 U( U; `; m% z1 }，则这样写：
, N+ O) u1 O) k* C! bif nums.size() == 0:
5 s9 D$ E0 \& v( [return false
方法二：
& R; T  ?6 j/ g, m: [2 i& Z如果数组是这样定义的，即：
int nums[] = {1,2,3};
! I( J1 ^) i$ T/ U2 p2 W先算下数组长度：
# l- k% O* }' f; d: J+ ?" vnums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
if nums_length == 0:
return false
/ v7 i; F- f" L9 ?3 k7 b& D原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544
" t6 n1 c/ Y  Q5 y6 c, ]
解决了上述问题以后，最原始的冒泡排序如下

5 A3 g/ d- M8 K/ W5 g8 b#include <iostream>
#include <string>
1 [9 b9 W( f. c( C. J& qusing namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
% s7 P6 z3 p! ~3 ~2 g6 U' _- \6 C% A        for (i = 0; i < n; i++)
4 }  H# V, k0 ~: L: I+ Y; {( s        {
* S. H. N( `: p2 O( ?8 n                for (j = 0; j < n - 1; j++)
                {
1 m# T4 a8 F+ `6 v' c  [                        if (a[j] > a[j + 1])
$ y, ?6 h& O7 p1 g                        {
6 x% i: t. K& |( v  K6 |! A" Y! w# V                                temp = a[j];
+ F  j: {. T5 D1 o# k. s                                a[j] = a[j + 1];
, j! Z5 d6 F3 F' G                                a[j + 1] = temp;
                        }
; s" S% E  ~( A. N2 D                }
0 x- H) p9 q9 r" A) O2 v3 X        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
' T! y$ s4 F3 Hint main()
& K! e# ]# @8 E9 V3 z{
  k/ R9 ~! v' A; |; i6 O/ x, Q        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;
; I% J: ]7 @6 n0 B( e}
; Y, r9 }0 Z) D6 N& p0 g
上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下

#include <iostream>
0 e( l) [. o; {7 O  z#include <string>
/ j: L# E. J! q6 y9 [9 P, Ousing namespace std;
: D0 f0 }# P6 s7 G, z: Hvoid BubbleSort(int a[], int n)
{
( s' ^  ^! @3 G( C        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
4 n. A- U3 K* Q* A( a8 ~0 m        for (i = 0; i < n; i++)
        {
0 c& {9 n2 B0 k2 a& w& Z' U                int flag=1;
, D9 y( L7 C- I2 M) q0 u, p9 f                for (j = 0; j < n - 1; j++)
8 F5 Y' r$ n5 A                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
4 z" f; z/ _& ?& C% H+ \8 `                                a[j + 1] = temp;
                                flag=0;
4 C( y- B, N3 H" \. H- J                        }
, }! p' ?) G+ g6 L2 H2 O                }
2 ]' L/ _1 n3 d) Q$ x                if(flag)
2 z4 ?; z. @6 j6 ]# s                        break;
! w& G9 F/ J7 q* n. ~3 P        }
        for (i = 0; i < n; i++)
                cout << a << " ";
. s1 O/ Q& w9 T}
int main()
7 M2 M$ J$ s$ \5 b, U{
( N0 C) x3 R0 ^. a3 F        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
$ C$ H% p* B; P5 k        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}

* H0 C7 G( Z! O& J. L3 c/ F4 y4 a+ y那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
2 X, v+ P0 S( I. f7 G- `1 w这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

* y4 L% V! F' d1 a#include <iostream>
#include <string>
& p$ B* k6 _  i3 A$ t6 qusing namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
* {6 O, ~8 N' k. r$ B6 s        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
2 p3 O. ]/ \: z' i; X/ Z2 g        {
4 g$ A8 k0 S0 ]" r: Q                int flag=1;
) d0 _( ]6 ]! g$ H" F" x2 d                for (j = 0; j<Bubble_Sort_border; j++)
                {
                        if (a[j] > a[j + 1])
1 l  _; X+ a2 j: }. T" \$ u                        {
& T/ o9 m6 D' a  W                                temp = a[j];
+ h6 Y5 o: F6 g                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;
- @# c: {+ t  U3 `6 e1 b; v7 |# w                last_exchange=j;
9 B' K7 N" G( p$ P! t                        }
                }
8 s$ A- H3 Q! O, p' z5 x                Bubble_Sort_border=last_exchange;
- ]# g/ b8 }/ }                if(flag)
0 u" w5 J; ~/ Z1 I                        break;
        }
5 _' e! x% n/ Q/ A5 ~        for (i = 0; i < n; i++)
+ A3 F% X0 R( G/ p                cout << a << " ";
% b0 n' w  f; g4 {# |; c}
int main()
{
        int a[8] = { 3,4,2,1,5,6,7,8 };
' g) M# q; _( d) j! K1 p! J/ @4 z        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
$ |$ l. i( E2 X1 B5 D! C: m4 {; ~' @        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
9 p" J* K7 V/ T* e( c% o}
5 v) [1 {+ T3 ]/ U
) Y1 h' a8 ?! r9 G$ D/ G9 B
& I# V) H- j9 s到这冒泡算法就结束了吗，不可能，你在看看这一串
8 Q) J8 Z; N( D3 @2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做

鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
" c% W# m! C3 Q( V  p7 W7 q2 h首先正向还是向冒泡算法一样的排序，
2 q, g1 k& v6 g4 _第一轮，1和8交换，
, V- v9 Y# p+ J第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下
. f) }! g/ e7 d; h: y
2 q9 h3 h, _# h- m! _
$ b5 F( r" B7 d- w) o#include <iostream>
#include <string>
using namespace std;
, m. M; r3 G) A, z6 A" U, X- D" T. avoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
        {
                int flag=1;
8 W7 _  r; {5 }$ R% Q4 Z' M                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
1 W6 O+ R7 ?3 I3 u                {
                        if (a[j] > a[j + 1])
                        {
" q5 _2 J; f5 |% j, F9 G                                temp = a[j];
                                a[j] = a[j + 1];
+ C4 I8 L5 p0 h  g                                a[j + 1] = temp;
                                flag=0;               
/ q+ x" D, F# k5 F3 k  Y                        }
/ y5 `8 R- w5 V8 p5 Z                }
                if(flag)
                        break;
  // 偶数轮开始之前  flag 重新置为1
8 b- [" n: S) W                 flag=1;
                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
: Z* j6 q* v0 Q( M                        if (a[j] < a[j -1])
/ S! W" c+ [: Y                        {
                                temp = a[j];
% i& P' e2 {3 V0 D/ E3 E" J. ~/ k0 I                                a[j] = a[j - 1];
                                a[j +-1] = temp;
+ s2 c6 D( s0 m' i2 N+ q+ F: w                                flag=0;               
7 J7 O) g) }& _2 \% k                        }
/ a! \" `. H' P' \5 F3 q# r5 d                }
                if(flag)
                        break;
+ p2 v# Y0 r8 `1 [        }
- o* u3 ]/ o4 E1 T        for (i = 0; i < n; i++)
% n; A3 G- Z- p% u6 ^1 Z. S                cout << a << " ";
}
int main()
{
: Y+ z  H1 D- m$ k$ I1 Q3 m* c        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);
  I) C0 l& K3 Y6 t, q+ G, t        return 0;
}
" K; u1 P3 d9 u" ^0 ?) k$ S) i" y2 ~' @1 |
5 @/ J" ]( }7 I) o4 F% e
以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序

————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! V+ x! y# T, P- e5 ?原文链接：https://blog.csdn.net/delete_bug/article/details/105928524


0 l1 D  t2 S8 O