关于冒泡算法的那些事儿

杨利霞

! U; P: J. ]# \+ K$ {关于冒泡算法的那些事儿排序算法的复杂度

: \% d, O( e: L7 I( x8 \
- w! F+ e8 C& [& A9 f& F2 a
关于冒泡算法你了解多少：
* o! i, W4 n  \+ G0 v* a首先我们规定数据如下
5 8 6 3 9 1 1 7

: ?' D; I, S$ v# G9 v在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
如果数组是用vector定义的,即：
vector nums;
//或
vector& nums;
，则这样写：
if nums.size() == 0:
2 V" W! `$ c0 Freturn false
4 K: }" s2 D: [8 B- A3 N方法二：
如果数组是这样定义的，即：
) J7 a' g, l; b# A+ F1 Mint nums[] = {1,2,3};
先算下数组长度：
' M1 c$ [7 [0 o; Z. w( wnums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
if nums_length == 0:
return false
! Y! S, F. [: L8 s* }原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544
4 Z6 z9 W$ s, A: \7 |' z
解决了上述问题以后，最原始的冒泡排序如下
/ C; V6 f9 q4 t
#include <iostream>
#include <string>
6 @+ \% T. E3 w. o+ Nusing namespace std;
3 e+ g6 l8 K/ w$ Tvoid BubbleSort(int a[], int n)
3 k8 i, I! P0 Z1 U! d{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n - 1; j++)
# ?* p! t7 A6 g8 x5 ]! q, d                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
+ ^' v* r! I, [                        }
                }
        }
" U7 R5 q+ `- Z, a        for (i = 0; i < n; i++)
  Q3 {! ?+ \8 _0 X4 \8 h: I                cout << a << " ";
}
- X6 R3 @5 E% ~int main()
; V( k+ R3 x& U6 X  d8 n{
0 r, @4 A. d; g" i# x" }5 z2 G) w1 T' s        int a[8] = { 5,8,6,3,9,1,1,7 };
5 y8 n' @2 V- S: ^        int b[4] = { 0,2,3,4 };
  e6 }0 a+ o" T. \9 G        int count = 0, i = 0;
4 j, l* H9 p6 {! @. e        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
& `3 x6 c  {4 a3 I/ L; c9 L                BubbleSort(a,count);
        return 0;
}
; y* l9 w% O# a5 @% m# T6 y1 P
/ w: C& \/ o. H( h9 Y$ @5 z7 {* z' T上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
6 \) t6 U0 G1 C5 B  p( Z那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下

0 t8 I, ?' ^1 |# \+ ?#include <iostream>
#include <string>
using namespace std;
- I5 e' a- V; ~  \6 E! d2 b! ~void BubbleSort(int a[], int n)
{
$ k% p7 r1 j) c( @4 M, k  O5 \        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
$ _: ?. z' g, R4 Y' _        for (i = 0; i < n; i++)
3 ?1 x, p  D0 [- r        {
6 L4 U5 e8 Y1 N5 ?: m# F                int flag=1;
( \! H- ?7 s$ A& Q                for (j = 0; j < n - 1; j++)
                {
3 G5 Q3 L6 S' R# F                        if (a[j] > a[j + 1])
! ]9 b# U: N' r2 D, g& p                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
( V( c* [2 |6 `" }! Y$ T                                flag=0;
  g/ e: E- V8 y, Z8 _9 A                        }
1 ~: B9 P. ]: G& d) ^                }
                if(flag)
                        break;
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
7 D4 z$ V1 v6 h: G}
, q, i; A! w; B' L6 z- Qint main()
1 r6 l$ {( e5 X" d; T1 J$ F8 N{
        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
' T0 K5 O8 d: I2 S! P        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
$ F2 W2 s1 i0 q: w7 f; c8 ~1 Z+ b3 p                BubbleSort(a,count);
        return 0;
8 S  x5 c' [$ p! L; X- A}

那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
" |; @# v+ j* x这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
$ T  p$ m# A; E% [- V( \此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

#include <iostream>
#include <string>
+ m/ t8 Y/ P' H" k+ V9 Y; R! Dusing namespace std;
void BubbleSort(int a[], int n)
' K3 n+ }+ i1 e- F/ L{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
4 E3 k5 a$ b6 G" n        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
' N+ s$ i7 o$ S/ ?& h                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
                {
& _0 z' S# E/ ]  Q6 l                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
  T7 f# c9 t4 u9 L                                a[j] = a[j + 1];
$ U2 C: {) V9 P2 {! H                                a[j + 1] = temp;
                                flag=0;
) Z4 ~5 H5 Y8 y( t                last_exchange=j;
, ?5 o( i/ ]( X- U2 @0 H5 h                        }
# n! t, s' j9 t. C                }
                Bubble_Sort_border=last_exchange;
# R5 y. z9 S% A( y+ b7 |# V6 ~                if(flag)
                        break;
+ g/ G5 `% |9 |        }
# O( }$ T/ i4 {9 Y3 x. ^        for (i = 0; i < n; i++)
2 H- e  P6 Q# b! e1 Y                cout << a << " ";
}
" n; ^. A. n9 O; pint main()
8 M; ^! e* D" q{
9 ]& `  x# n7 s5 Y: c        int a[8] = { 3,4,2,1,5,6,7,8 };
5 ?& k8 w# P- n3 d        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
& A( r) M4 y) N1 H        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}

2 D8 `( [9 @" i: a6 m* \
到这冒泡算法就结束了吗，不可能，你在看看这一串
0 l% }- r  b) H( I" C; c$ W5 m3 r2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做

鸡尾酒排序
% Z: e) }# }# d: A' y! o鸡尾酒的排序过程是双向的具体怎么实现了
3 W; ^5 R) `4 G8 r" ]1 F+ c: g首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
+ h& b( Y: i/ S* r4 B第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下

: m' W- m6 F0 r3 p- m7 Y. j
, S+ H/ T" A% B8 l+ f& `  p#include <iostream>
#include <string>
using namespace std;
; E& U  I. b3 r7 s8 N5 S( Yvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
% h4 P$ F0 B, {' ]# j  q" Q        for (i = 0; i < n/2; i++)//奇数轮
; t/ H! d% ]( _9 l& y' A        {
8 A; f# Z- Q" n  D& }* r$ P                int flag=1;
                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
4 i; S  S( s+ K                {
                        if (a[j] > a[j + 1])
                        {
$ s9 F7 ?* ~6 `- W& p8 ~                                temp = a[j];
9 v- I, Q' T: F+ w0 w8 t                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;               
                        }
                }
                if(flag)
                        break;
) ~) g- T# l9 v5 }& ^2 A/ X  // 偶数轮开始之前  flag 重新置为1
, |2 H% E3 b, f                 flag=1;
8 d7 o1 N% ?6 c: ?, u% |                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
# A$ M9 o9 h2 [+ g1 n, L                {
                        if (a[j] < a[j -1])
                        {
                                temp = a[j];
, f$ N5 W3 s, Z# S                                a[j] = a[j - 1];
9 Q+ W4 ~8 o* c( d( i/ I2 p1 w* o                                a[j +-1] = temp;
                                flag=0;               
                        }
2 f+ o" U  A+ `  z! z$ L8 Y                }
                if(flag)
1 n+ x- B5 d8 l8 I                        break;
" C, N% f/ `$ n, P+ }% y        }
        for (i = 0; i < n; i++)
# s9 r% c! i/ E) H# d                cout << a << " ";
/ R( |$ u( w: U}
& Q5 J/ h* S4 q1 Q# `0 eint main()
{
" q+ D- T9 o7 m$ {7 ~0 r( v        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
( P) g. N1 q( c; d8 ^# a" d        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
: z  `$ J+ W. p5 h! S        return 0;
}
7 s! m. K0 S% l6 P+ k5 N

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

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

* M- g' h0 m( h