关于冒泡算法的那些事儿

杨利霞

关于冒泡算法的那些事儿排序算法的复杂度
) s* v, e- C6 F( O3 o" q

: k5 D5 e7 A% K# ^, d7 M6 Y
关于冒泡算法你了解多少：
首先我们规定数据如下
* A! T+ }" N+ a$ |. z' s5 8 6 3 9 1 1 7

" \/ `  J8 m1 @. @& }在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
如果数组是用vector定义的,即：
vector nums;
//或
1 q- L! C( D2 l' v, ]/ l8 zvector& nums;
，则这样写：
if nums.size() == 0:
return false
方法二：
6 J; ?' v& `' }如果数组是这样定义的，即：
int nums[] = {1,2,3};
先算下数组长度：
8 W6 r: h4 a9 N  lnums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
- x; F1 c2 |9 Q2 w3 |9 `6 Iif nums_length == 0:
$ y$ e9 k- O& c( E# Hreturn false
0 v) D* r8 N$ V2 o) I原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

解决了上述问题以后，最原始的冒泡排序如下
* f# R1 I( ^- H+ {7 {( D3 {  z  ^: F
/ ], N0 n) M9 b5 o0 I3 ?$ p#include <iostream>
1 Y' Z  P* E0 Z# @) k, {#include <string>
using namespace std;
8 y* l2 g! a! B6 d0 g" H. o3 `) uvoid BubbleSort(int a[], int n)
{
2 o3 G) U$ P8 n) r4 B        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
% C& w- C- H5 j2 l. _, T        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n - 1; j++)
                {
! n6 w# W4 f" c8 }  w                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                        }
( e2 j) J3 t  V6 u: v0 Y0 ^7 J) G                }
! w$ J8 T" I8 U+ a. x# e; [9 z+ K        }
) q& Y0 Q! y2 U        for (i = 0; i < n; i++)
$ j. h5 l+ x1 \, r' P                cout << a << " ";
8 F7 E0 y  i) x2 v5 c6 x}
, I% a0 ^8 M5 w$ c* W& Pint main()
  G1 j/ v2 N: s' f$ }' x: G{
2 F" g; Z" |9 {5 C& w! {( S7 s7 v        int a[8] = { 5,8,6,3,9,1,1,7 };
2 v0 S  p1 r  Y$ m' g        int b[4] = { 0,2,3,4 };
* ~- Q' A% ]6 Y$ T5 Y- K; c        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
. L6 ~. P$ [# Y        return 0;
}

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

#include <iostream>
#include <string>
using namespace std;
) q/ ^" L# C: n4 z6 L: I0 Avoid BubbleSort(int a[], int n)
% V3 m  A8 F9 e% v1 i: ?& q7 W{
6 D6 b! d7 {1 |/ f0 S, H        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
) U" }4 ~- I/ u6 l8 D, c/ h( ]        for (i = 0; i < n; i++)
) Y) a- \& h3 {. p. V        {
# L. @) d( f& _- d/ l: E5 m. t. ?                int flag=1;
                for (j = 0; j < n - 1; j++)
                {
9 c0 n8 u6 R5 r                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
/ {9 g( f  q' [" p% X$ t( K                                a[j] = a[j + 1];
0 O9 A- x8 F8 z' w4 o8 _                                a[j + 1] = temp;
  [: b" T$ t" D# T                                flag=0;
                        }
                }
                if(flag)
                        break;
$ z( I) c9 o6 x$ J2 J        }
/ t' j( P7 o9 d, t" G; z/ z        for (i = 0; i < n; i++)
5 Z# s+ o0 o1 i$ }5 q                cout << a << " ";
. Y: h6 ~4 D* x4 H' ^) @- u}
int main()
" T" z' s3 S0 e7 z9 \# n, S{
        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);
3 B  I* Q; R6 r% l, g2 ]        return 0;
}

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

3 ]! F# q! X! z1 N+ g! M. U$ D#include <iostream>
#include <string>
2 s' E; _$ J+ ~4 Nusing namespace std;
void BubbleSort(int a[], int n)
{
* A" w; g' |. c4 Y- C        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
9 W8 z, d) A$ f( i0 F        int last_exchange=0;
# V0 s$ l3 q0 j$ `0 l* d        int Bubble_Sort_border=n-1;//无序数组比较的边界
7 R& x8 }. n& P' _' h6 N        for (i = 0; i < n; i++)
        {
5 i3 c- z0 q, i9 z, D                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
                {
, E" a4 ~2 h/ [3 G* K6 n; O( m                        if (a[j] > a[j + 1])
/ f- A8 l* c* c( |$ h8 `' F9 B                        {
* y7 X2 f( {0 X                                temp = a[j];
+ {! G# P: t' Q+ _                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;
: x  R- V5 F# g: Y                last_exchange=j;
                        }
. M$ n( q0 q! }( T6 E" L                }
* D/ c+ K' D, w7 B4 i                Bubble_Sort_border=last_exchange;
                if(flag)
, C. ?$ ]$ Z7 h. a) v2 l8 A- |                        break;
        }
; C$ J* c, n8 F$ x3 O, m        for (i = 0; i < n; i++)
  s7 K8 y' o) F8 B                cout << a << " ";
, B# K9 e2 E, _9 |/ V7 X. g1 ~}
int main()
5 `6 ?- F) C: ~{
        int a[8] = { 3,4,2,1,5,6,7,8 };
0 _/ q' L* j7 Q. t        int b[4] = { 0,2,3,4 };
  L6 p9 y7 e3 P& c# P        int count = 0, i = 0;
4 w: p  h$ V# Y$ O2 e: q        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
0 q: p$ p3 A8 X        return 0;
4 d* f: g2 v# V6 Z  Z9 q}


. P; g- X: d0 b到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做
# R: t) N; O% v/ {
2 X$ q7 N. C7 K% q/ c+ R鸡尾酒排序
, o+ t- {; G! z# [2 H鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
" D2 D! u- n5 {% {2 A2 }第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下
# R# @6 \0 h7 a0 {9 ?6 g
0 N) y+ G. ^5 T$ n3 N4 P/ \7 l6 D
#include <iostream>
#include <string>
using namespace std;
# `( T, Q" z. ~5 @- \; v& l$ rvoid BubbleSort(int a[], int n)
{
7 l& `, @4 h3 r1 }0 d) N        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
" ^* _3 {$ g' P- Q, u' {        for (i = 0; i < n/2; i++)//奇数轮
        {
                int flag=1;
( l1 @' t1 m8 |( y7 J' G2 j2 T                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a[j] > a[j + 1])
                        {
( F. y: G$ E! s+ n3 S4 D                                temp = a[j];
                                a[j] = a[j + 1];
$ R" h0 h" e5 S: x" y. {                                a[j + 1] = temp;
! u* A6 v  S. d# r) v                                flag=0;               
4 l) R3 I( }4 v$ z) `6 F                        }
  _  C4 x1 G5 X5 D5 c                }
                if(flag)
                        break;
, ~0 P: F+ R6 d: \9 Z3 Z  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
( O- T. m! x' |+ |, n; k                {
. w% h  g. x7 h) i                        if (a[j] < a[j -1])
                        {
" C; F1 H$ S; Y6 K                                temp = a[j];
$ e% ]  ^% Z9 h& g& |7 W- A. ^                                a[j] = a[j - 1];
                                a[j +-1] = temp;
5 W6 {: ]) D  A3 ~, T& u                                flag=0;               
                        }
                }
6 J* s) d% D( h- K! t; P  U                if(flag)
; y& U- O, _) ~) S2 H                        break;
% p9 j; v: P1 Z        }
        for (i = 0; i < n; i++)
) j# n" c6 l: ~" c                cout << a << " ";
/ r! B5 n# L# B7 s. ?- q) y}
6 i5 ]  t! V, H# T6 P8 `+ }6 rint main()
7 @7 f/ Y0 J) ?5 s{
  P( o# q9 d3 j( m9 J% j        int a[8] = { 3,4,2,1,5,6,7,8 };
0 q1 K6 n) V( ^) S5 g; R        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
3 H- C% W4 g1 t/ A/ E! u        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
. n2 y$ m2 j7 J% G) E0 P5 z- i4 Q}
9 S9 g% q7 j6 I9 {1 Z5 [

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

. i  i5 u9 z3 C/ a" x  z& n————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
: T" Q' U0 Y. C/ m) T# q2 b! ^原文链接：https://blog.csdn.net/delete_bug/article/details/105928524


2 Z8 y4 i1 {8 J# b" g: B