关于冒泡算法的那些事儿

杨利霞

关于冒泡算法的那些事儿排序算法的复杂度

; [$ s- F; v2 L* G
2 J, i5 P, L- t1 K; w5 }; ^: t
关于冒泡算法你了解多少：
首先我们规定数据如下
5 8 6 3 9 1 1 7

8 o3 C% {# ^0 @6 D7 t3 `7 M( y, R( X在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
如果数组是用vector定义的,即：
4 q& _( i  a. ~, O/ }vector nums;
1 n6 T* D8 [) G! B//或
3 ]% S0 q; J0 Q9 ?( Z$ Mvector& nums;
/ {* w- o1 `) N+ L，则这样写：
0 J1 Q4 t7 [0 a; Z$ I: Sif nums.size() == 0:
; e: k" n, L' x! D- ?6 q3 J4 Oreturn false
2 w3 K7 ]% b2 P9 K: w方法二：
; ?) Y! g- _# G( G. t- [/ t如果数组是这样定义的，即：
8 G, S+ u0 o/ w. G  lint nums[] = {1,2,3};
- R& o( `) Y7 p1 C+ G  _  r先算下数组长度：
nums_length = sizeof(nums)/sizeof(nums[0])
: A( d% t6 |1 K7 @' h( f然后判断数组为空：
* H3 g9 t" I- E, ]; Tif nums_length == 0:
# S7 o8 _0 H5 @return false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544
! F: u% f' y* {; I' k+ S5 _5 c
解决了上述问题以后，最原始的冒泡排序如下

#include <iostream>
* x3 f* B8 P7 [; a, s$ H0 V#include <string>
; c; s* f  c# yusing namespace std;
: @: }3 r( F, Evoid BubbleSort(int a[], int n)
; Q  g# t5 R' b' j1 X{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
, V" ], j" K2 W0 Z        for (i = 0; i < n; i++)
$ z0 T1 M/ h  f% I        {
  j2 m0 K; g) g7 {  J! V                for (j = 0; j < n - 1; j++)
                {
                        if (a[j] > a[j + 1])
                        {
- H0 k+ L+ ~1 r7 D" e                                temp = a[j];
                                a[j] = a[j + 1];
/ l( `9 Z" @( U# i                                a[j + 1] = temp;
                        }
                }
        }
) P, y5 M! j+ C: e. A        for (i = 0; i < n; i++)
6 F9 s$ K8 c: ]! c) _2 G" v) }                cout << a << " ";
; Y" n: G* A* {3 X, r- {/ L3 r}
3 G% }( {/ u5 Dint main()
{
8 z4 @; U# G1 @) K9 w- s& ^        int a[8] = { 5,8,6,3,9,1,1,7 };
! t) C% a& t. O6 k* z3 ]# Q3 T, A6 w+ B        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
/ w! T+ \& y8 j        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
% [& `; `: W1 ]2 U$ C2 g}

上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
! q1 [# w2 I8 x) V5 _4 t那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
4 x! Y! |4 @0 P3 e" L0 Q+ x0 D5 p
#include <iostream>
#include <string>
3 m$ W( u, J' b& {3 Q, W" s4 Y% gusing namespace std;
void BubbleSort(int a[], int n)
$ R4 i" r& v" l{
1 e9 A$ L( Y+ e+ F        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
  Y8 Y4 L  ]5 C. Z        {
                int flag=1;
/ o# S' v- r7 b: R- C! P                for (j = 0; j < n - 1; j++)
' T6 r! y" K* C( s3 a% j                {
                        if (a[j] > a[j + 1])
                        {
% c3 z* w* ]$ `& ?4 Y9 @4 C( i                                temp = a[j];
                                a[j] = a[j + 1];
5 \" v/ U  b$ E/ g! ~  `                                a[j + 1] = temp;
: c6 l$ w" _( z- \- W* `                                flag=0;
2 @6 m0 o4 M! G( D( f- t8 b                        }
                }
/ h1 ?$ k" r2 q                if(flag)
2 e/ v7 A; B# v. V                        break;
( d) L  x" H3 U3 w# b3 H- x$ K        }
" P+ g# i) T$ a2 p  ~        for (i = 0; i < n; i++)
7 G5 l' c8 r$ B, Y" J3 I2 z                cout << a << " ";
}
int main()
- a$ i3 G1 a& N. k2 _! o4 t  a{
        int a[8] = { 5,8,6,3,9,1,1,7 };
+ `+ T5 x0 Q& `7 n& w2 t  E5 c        int b[4] = { 0,2,3,4 };
' H: l* P6 e/ y0 |8 Y' q0 Z' z        int count = 0, i = 0;
6 Y1 `5 |5 r0 R" {0 I        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
! @: U1 b  k0 H  A                BubbleSort(a,count);
- |" O: Y" D9 p. F! a        return 0;
}

! q3 a9 Y8 m' k8 C3 i那么再以一个新的数列来判断上述冒泡算法 的优越性
# D2 ]/ x" Y/ r' ?1 ~8 o+ v2 F3 4 2 1 5 6 7 8
这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
: Z& L/ P. s) n& F1 M0 L" l此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下
1 z4 F8 ?1 \+ Q. B& ^/ I
1 H: \$ _! S, D" K# L#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
! o) D3 k9 s: w0 N9 _* X        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
9 Q/ b) _0 E1 k2 B        for (i = 0; i < n; i++)
        {
                int flag=1;
% U  C( F- r- b" E( x* a                for (j = 0; j<Bubble_Sort_border; j++)
) r0 K% J; Y9 p- v1 {0 ~1 z                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
6 ?7 S/ t+ W7 K/ g! J/ Q$ r7 b                                a[j + 1] = temp;
5 {) P) @* x  C                                flag=0;
  ~% h5 A3 F7 f# l% z1 T                last_exchange=j;
                        }
                }
                Bubble_Sort_border=last_exchange;
                if(flag)
9 @; f) H! n5 n/ u% I& h7 a                        break;
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
2 j' K2 d2 u( I& f  L/ ]$ Gint main()
: M" D( F4 L; J{
) `) e0 V- W' D3 ~- s        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
$ u& j3 Y# R( u: n$ o' h        int count = 0, i = 0;
: B9 O8 o( @/ L5 o- A# n# Z( v        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}
$ \3 g) \2 e+ p4 b' [' o1 C) @

到这冒泡算法就结束了吗，不可能，你在看看这一串
% t1 |, X( V- i- K  g2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做

鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
# v) ?9 ]( \7 H: {第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下
* N8 f" \& h0 R, m; a
  G: I" W9 p: C% C. s6 k
#include <iostream>
6 H* o% v$ {0 K' @+ ~8 Y#include <string>
/ g8 J. h) c# r0 lusing namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
, f! j# S6 j5 ?  P# X& g+ Q1 N        for (i = 0; i < n/2; i++)//奇数轮
" |  p% ?: r' @, d        {
                int flag=1;
6 A- k: f- e: j3 {                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
* n3 }8 d5 F4 l                                a[j] = a[j + 1];
3 j% a. ]! q: i; Q2 L8 n                                a[j + 1] = temp;
                                flag=0;               
                        }
                }
                if(flag)
/ }# X& L$ |! G4 S4 }                        break;
  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
( b; S) e1 |: r0 P$ B8 Z* e$ v4 M                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
$ x  h" Z: U0 V, D% A; U+ S% n% _                {
                        if (a[j] < a[j -1])
                        {
                                temp = a[j];
                                a[j] = a[j - 1];
6 Y$ k4 Y0 G! e/ w/ @5 [                                a[j +-1] = temp;
                                flag=0;               
                        }
                }
1 Q4 ^/ b3 ?) h                if(flag)
: H1 i7 t. ]/ b% Z                        break;
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
6 }, p7 @3 l( S7 Z% |% I1 c5 cint main()
) x, a3 f! X- p8 T5 J7 J{
        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++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
4 Z( J% c6 t. ^+ Q. h6 V                BubbleSort(a,count);
: d$ g# a4 C4 Y        return 0;
" }0 l- [* T. a% A( J' b9 A/ ?, b}


以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序

) X! N! P0 U4 ]6 `: J————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% t5 R1 V8 j. }, q" @- z原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
9 q/ B6 d) {6 A2 \9 O
: z9 z; g$ O2 f  m4 g/ M8 I. {