关于冒泡算法的那些事儿

杨利霞

3 V8 T7 `% a0 v" Z" n- o关于冒泡算法的那些事儿排序算法的复杂度
/ ^5 S0 G5 Y  B6 x' ], M" S% Q

0 R; U- w' j) B, `( p9 W, p" y
1 u3 h. a7 L, Y7 s8 V关于冒泡算法你了解多少：
3 V+ V& }9 N. r. H5 Q& @, j首先我们规定数据如下
& ]; d9 O, U" u) \( A5 8 6 3 9 1 1 7

" K% f0 `/ t# e% P在对数组进行冒泡排序的前提下，首先求出数组是否为空
" [+ H$ T' p. {  a9 i2 P( A$ I方法一：
如果数组是用vector定义的,即：
vector nums;
//或
5 l! Z) X: z& q8 avector& nums;
- V& c4 F5 |- d1 i6 W，则这样写：
if nums.size() == 0:
return false
* `+ e+ L. Z" N- Q: P% L/ [# h方法二：
如果数组是这样定义的，即：
int nums[] = {1,2,3};
/ T  r/ Y1 t! P5 K先算下数组长度：
' w9 l" C3 `# n$ A& g6 Qnums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
$ D: {2 x# `5 H& d; X' ?if nums_length == 0:
return false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544
+ L/ p6 R& O+ U1 m' X, r/ Q; k9 v
解决了上述问题以后，最原始的冒泡排序如下
3 p$ }) L/ J# w
#include <iostream>
#include <string>
1 K) u) j! N: _9 M6 N; H) Q/ Rusing namespace std;
void BubbleSort(int a[], int n)
! b8 |& _1 R8 w2 J/ P0 {{
$ J" s+ |/ @8 I: d2 n) {/ }/ [( i        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
) t5 N8 I& O0 o1 S) X/ O( L        for (i = 0; i < n; i++)
        {
2 {( _, F2 ~* z/ Q                for (j = 0; j < n - 1; j++)
- t3 o8 ^' p- `4 N                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
2 L0 P/ M# \" {                                a[j + 1] = temp;
                        }
/ q8 Y& F. S1 ]- v. |5 y& ~                }
        }
5 p: `' o2 O9 @( N( b        for (i = 0; i < n; i++)
) E" H: Z' I6 n3 n" j6 ]" _& s                cout << a << " ";
8 S" ~. v* ]- w* O$ q}
: A8 x, B+ ]; c* q1 qint main()
{
3 |5 _9 i9 {6 u0 ?        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
: i0 h( o* A2 l; ~% Q0 ~7 c        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
, L- h: U0 C' @        return 0;
}

上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
4 V0 g4 E3 U+ ~7 k. ^! L那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
4 H5 T8 U- Z/ b, c' D3 M
#include <iostream>
+ M. ?$ {, _; v6 ]  e. A6 d; h#include <string>
& {; @1 n% o; gusing namespace std;
void BubbleSort(int a[], int n)
{
% t& G) H2 E( {5 {( T6 o' s        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
$ E1 Y) }- J7 v* t                int flag=1;
                for (j = 0; j < n - 1; j++)
) U5 u. v4 R: D2 _3 q; U                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
" }8 l9 K/ @% A4 Z. Z                                flag=0;
                        }
                }
                if(flag)
% R6 z( |6 U9 a3 j7 P                        break;
        }
4 H- v( L$ z. x; m# Y        for (i = 0; i < n; i++)
                cout << a << " ";
) L8 _9 H- x& T# ~# [5 K}
int main()
/ n( @* D+ G, h{
        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
2 S. U6 U( \( m! l4 [1 ^0 Q        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
8 z+ B& s7 t7 I) L/ ^  M        return 0;
% H# o1 X/ Z% o& G& Z, T  n}

那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
# Z- \% t4 B( k" T6 s' I  G2 a这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

/ B4 B* _- u/ t& e7 [- l5 X! |#include <iostream>
#include <string>
using namespace std;
4 k/ x, \, E: A/ r! F' nvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
/ h" \7 [# x4 F9 k& n        int last_exchange=0;
- A: V3 X- e/ D6 e/ ^. N        int Bubble_Sort_border=n-1;//无序数组比较的边界
1 ~  d/ W" K1 l% K        for (i = 0; i < n; i++)
/ u; I: ?" e) W: x/ Q& |        {
" w! M" X' W8 \4 o( O/ y2 s                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
                {
                        if (a[j] > a[j + 1])
4 t# }  B; ?* R, {: R# N- h                        {
1 F9 {/ v  N5 F  ]                                temp = a[j];
* {8 x3 x1 m3 w: F# f                                a[j] = a[j + 1];
* f4 e+ ]* u) k# J                                a[j + 1] = temp;
                                flag=0;
$ V: m- P2 e' Y6 q3 u# _% {! X5 m# F2 u                last_exchange=j;
                        }
& |+ p' D4 z7 u6 V- r* I& a" k                }
4 K0 d, `( [1 [$ d  s  f5 [7 C4 g                Bubble_Sort_border=last_exchange;
, T3 U4 L# _- `. U$ S                if(flag)
                        break;
3 Q& n1 y! X6 [$ e        }
        for (i = 0; i < n; i++)
4 F" H; X' v0 ]& S5 l                cout << a << " ";
: H+ _9 u  ]: L7 X8 m}
int main()
{
% h3 d3 A; x+ L4 ~* w$ B( n0 X$ l6 V7 E        int a[8] = { 3,4,2,1,5,6,7,8 };
' |3 j$ b# ?5 \/ G" w. x        int b[4] = { 0,2,3,4 };
" d/ z/ {+ w1 q        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}


4 W- J( |5 g- o6 D8 S5 R6 F  Y& _. D9 a到这冒泡算法就结束了吗，不可能，你在看看这一串
; A3 Y! y1 v2 r# g7 ?2 \! p2 3 4 5 6 7 8 1
  t" ?4 Z7 u/ c上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做

) F" t+ v2 L( z1 c0 }9 f鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
' v. r, G% C" f- Z: u+ U# Q& d第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下
# t1 ~, C2 \# @9 ~9 r$ J

#include <iostream>
#include <string>
using namespace std;
( L( h# B5 ~) h) v# E7 ~4 l2 ]void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
        {
  N8 ^; I% g: e& I# u                int flag=1;
                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
: L- S- x$ A! L& k                        if (a[j] > a[j + 1])
                        {
! ~$ |* ]6 y2 y% e                                temp = a[j];
, I: u( d$ w! d3 \                                a[j] = a[j + 1];
  r& Z0 A# r. c: n1 t5 p                                a[j + 1] = temp;
& ~2 ^4 u# e( D3 A                                flag=0;               
3 }# N9 ?! T/ ^8 A0 U5 z' c, Q# W                        }
                }
                if(flag)
                        break;
4 Y( r- k, c* m$ J' T: w% L$ s  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
- e# o- k4 E/ b& W! A                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
+ c' }# q6 Q" d( I2 L                {
                        if (a[j] < a[j -1])
                        {
                                temp = a[j];
! F1 @, c. O& s; c( k3 T                                a[j] = a[j - 1];
+ q, L" n: j2 F& o8 e/ x- i2 O                                a[j +-1] = temp;
4 Y$ B) i$ T& m' e                                flag=0;               
                        }
+ w/ w* h6 ?$ r" x' _9 H                }
: h9 N$ q( n* V& }- B$ T                if(flag)
                        break;
        }
8 ~/ L6 A" ~4 c* Z* e# B4 A; x0 A        for (i = 0; i < n; i++)
3 J, h6 M5 O+ G) S- X- B& c                cout << a << " ";
}
. u" X7 r# p0 m, U- Y/ t7 e6 |  kint main()
0 ^& [: A; X+ n1 @" }{
        int a[8] = { 3,4,2,1,5,6,7,8 };
* ~6 o& p1 R2 j  V        int b[4] = { 0,2,3,4 };
! R" K$ `& M, }; H3 I2 N& A8 c3 K6 c        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
, C. X" c" ^5 H0 V$ B' V; S0 U- o                BubbleSort(a,count);
- }, a) H+ k6 S8 f. ~        return 0;
}

0 g! K' \, \, j; g
以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序

* V6 }* d* |$ t. j————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
  T. T- Y" _: p. M0 u# {原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
5 i5 [5 y$ q2 c( z" c

. k# d- s2 y3 _! f/ j