关于冒泡算法的那些事儿

杨利霞

+ v0 x+ w/ r& j* z7 ?, D- z+ T+ ]关于冒泡算法的那些事儿排序算法的复杂度


# m, B- h8 n4 n6 `: t! Y+ p
关于冒泡算法你了解多少：
首先我们规定数据如下
% g+ `7 z2 d3 z$ d+ i* L% X5 8 6 3 9 1 1 7

. x! B, r+ Z6 l/ Z) e在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
# Y  i3 Z8 K: l6 Q9 h如果数组是用vector定义的,即：
vector nums;
//或
vector& nums;
，则这样写：
4 l; M9 U. T9 ^+ j3 a# Dif nums.size() == 0:
return false
8 g( M6 x0 F8 Z4 B# h2 ]0 l( b方法二：
; q9 T- t) {7 j+ x( ^3 A2 l如果数组是这样定义的，即：
& Q( m0 K0 u* J$ n. G# Tint nums[] = {1,2,3};
先算下数组长度：
nums_length = sizeof(nums)/sizeof(nums[0])
4 V- E6 P1 `  `# L( W- t+ i2 x然后判断数组为空：
if nums_length == 0:
4 o* g1 G4 G7 T3 I- vreturn false
( Q( P) D/ A, k原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

解决了上述问题以后，最原始的冒泡排序如下

4 Y% `1 E4 Q" A3 g# r5 ?$ t#include <iostream>
$ V7 ~: K% e( {#include <string>
using namespace std;
void BubbleSort(int a[], int n)
& m$ F, R4 w# J/ k9 t; \{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
# K6 _, d' O4 b        {
                for (j = 0; j < n - 1; j++)
                {
                        if (a[j] > a[j + 1])
3 t. C) L" ?) T! C( R                        {
                                temp = a[j];
                                a[j] = a[j + 1];
9 p* [7 z4 Z4 E% @* l( w) S# I& \                                a[j + 1] = temp;
                        }
                }
, `' ?: H# X2 j" z        }
        for (i = 0; i < n; i++)
2 S# K4 }0 L. c* e4 D3 j1 @                cout << a << " ";
}
8 b  ^2 o% S3 r. ~4 C1 a* m: b, G% `int main()
4 S& z( }& A" g, Y0 u' L$ h) H. U{
2 O% l9 k* B- y6 g  O. f        int a[8] = { 5,8,6,3,9,1,1,7 };
. k' Z5 w2 E) J2 T1 Y        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
  {6 u0 L, L( ^                BubbleSort(a,count);
        return 0;
' P. u: T& }+ X/ e# @! K% Z}

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

, \9 I" i4 B3 x8 P% E2 t- U9 [#include <iostream>
+ J) a5 m% ]8 X4 z. H; B#include <string>
using namespace std;
, C& l; G) T: ?void BubbleSort(int a[], int n)
; d6 ]3 Y2 W0 I: a( S% F{
! U! R$ h& D$ a        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
: c% K( j* F! a1 b# T" `        {
* ^: q6 [! J+ D3 \1 ]* d# g                int flag=1;
9 J' m0 P  c! d* r* G                for (j = 0; j < n - 1; j++)
                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
# B" y4 ~+ P' G: k$ Q% Z: W                                a[j] = a[j + 1];
0 S9 k1 a" n+ W- Y7 [+ V                                a[j + 1] = temp;
$ I& A7 V; P; Z6 M" \                                flag=0;
                        }
                }
. k: J. |+ p. L( {, n. j. }                if(flag)
' W6 f! [0 S6 Q$ D) M  [, k                        break;
        }
5 B5 G) H) S# E6 x* M- T        for (i = 0; i < n; i++)
                cout << a << " ";
) D9 T8 A! A4 u7 H  A- o}
int main()
, W, Q& l  N- U7 \1 T{
: @7 A9 ~& d' Y0 a1 r7 r" _        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
) J5 |' `7 m2 p% W        int count = 0, i = 0;
3 g5 n0 a! p5 j( b        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
* W( ^$ F, N' I" ]! Y' b) \! t( U9 a                BubbleSort(a,count);
" I/ @9 i7 Y2 U5 a) m- B2 i" c        return 0;
}
- T$ R/ p% r; F, h& S4 j
那么再以一个新的数列来判断上述冒泡算法 的优越性
2 Z2 @+ ~3 `; M! c: h6 I/ ~3 j+ ~3 4 2 1 5 6 7 8
这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

/ C! \0 D# Z. Z6 H- u+ D/ n  i* A#include <iostream>
9 F$ y+ l( v6 A; s: E. p. |#include <string>
& X$ N1 f" K% Y9 m$ I; @3 D) s$ t& B( lusing namespace std;
+ _4 v$ K! X. S  jvoid BubbleSort(int a[], int n)
{
; D& \" e! d0 f+ N1 Q# c8 L9 W* E! f        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
6 X! }. f- b( i& R        for (i = 0; i < n; i++)
9 Z2 v; ^" {8 b% D+ p        {
                int flag=1;
9 G3 I% k  g$ Z0 S- V, N                for (j = 0; j<Bubble_Sort_border; j++)
                {
                        if (a[j] > a[j + 1])
                        {
, {" T1 S- \+ B2 \. A1 ?/ l                                temp = a[j];
                                a[j] = a[j + 1];
8 ~7 K: `, e# M8 W! \" H                                a[j + 1] = temp;
                                flag=0;
6 q8 p  R/ E* X* l  [  E                last_exchange=j;
' n* C7 M) e  Q2 B$ K& [                        }
# c: L) {! ]) ?# K9 H$ `/ ]4 c4 j* j; K                }
: B+ e/ h: D9 W. F+ O1 P4 I7 _* I                Bubble_Sort_border=last_exchange;
                if(flag)
# t/ {% g; i6 D7 K                        break;
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
2 Q8 k$ s6 e7 \3 ^int main()
{
( z6 \5 V7 u8 ^2 T2 U. g        int a[8] = { 3,4,2,1,5,6,7,8 };
% ]4 E( X, S# N        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
( I( Q% F$ E" X' E: @) |        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
: y+ \7 S4 j% d$ B, o( r                BubbleSort(a,count);
        return 0;
# Y' Z$ Z6 X! l9 \& u) \}
- {6 a8 S  a; u; ^# w. O

" d: K. s0 L  @/ V4 Y- ^& o$ \到这冒泡算法就结束了吗，不可能，你在看看这一串
# S* b( p4 a! g& T0 a8 Y2 X7 H2 3 4 5 6 7 8 1
4 i7 M( T& p3 f  W# D5 ~上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
7 u- s/ _& S/ q" Z. O+ ?基于冒泡算法，延伸出一种算法叫做
7 k  j# k# Z( @) i# {
, x0 x9 `$ u) n2 L+ w' [鸡尾酒排序
- z8 |/ J) ^  B) X鸡尾酒的排序过程是双向的具体怎么实现了
  B0 |3 ]( T7 y0 g9 {% F) V7 l+ Z首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下

& h; i2 Q+ |+ [# D# L- a
1 U$ G& e: T9 ~# s3 K#include <iostream>
#include <string>
using namespace std;
, _: T: v' [$ \( b+ X$ Bvoid BubbleSort(int a[], int n)
2 Q4 ^1 @) }/ |6 h{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
8 S" w- f8 h! ?) _" W5 n& c        {
                int flag=1;
$ Q: L- r$ L1 s$ ^4 N/ {                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a[j] > a[j + 1])
                        {
3 N0 o! `) F  c' K" E$ {% [4 R                                temp = a[j];
, U0 S( \1 @" S( q  n                                a[j] = a[j + 1];
  \0 u  w: Q" E; ^( a3 [, j4 H) Z                                a[j + 1] = temp;
                                flag=0;               
) L7 \. C) Y2 c                        }
! n/ d( m( l( v9 _                }
                if(flag)
                        break;
1 Y1 ^# _% f+ k0 [3 ~; J: B  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
8 c; s- O) @- |6 M                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
; N0 {% \4 y9 t                {
9 z1 y% |- F: U6 ~* O  U9 t                        if (a[j] < a[j -1])
                        {
                                temp = a[j];
- ]  y( n8 g8 f8 m2 G                                a[j] = a[j - 1];
& J" K, p* n3 q- L                                a[j +-1] = temp;
                                flag=0;               
) E+ S; P+ K% A$ |( r- U4 a                        }
, ~( I+ ?$ Y' ?                }
                if(flag)
                        break;
        }
2 F2 p9 |& N5 M0 A        for (i = 0; i < n; i++)
8 j$ k4 f# y5 j1 S8 m0 c7 V( Q                cout << a << " ";
}
. B- H  C( B) jint 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++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
$ Z! e' ~0 q, e                BubbleSort(a,count);
        return 0;
}
; P) _7 b) g+ E" d: i9 R8 u- a
8 E3 f+ v) D- K) M1 _! x2 X& k
以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序

8 @, s) s$ R( C6 Q————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% e1 v4 Y& z: h+ C7 f原文链接：https://blog.csdn.net/delete_bug/article/details/105928524