数学建模社区-数学中国

标题: 关于冒泡算法的那些事儿 [打印本页]

---

作者: 杨利霞    时间: 2020-5-5 14:19
标题: 关于冒泡算法的那些事儿

关于冒泡算法的那些事儿排序算法的复杂度
9 R  B8 k" ~- _8 F, \- ~5 N6 d

  {2 m+ H) Y( f% M! W9 A. k
0 _, {' S# t* o关于冒泡算法你了解多少：
首先我们规定数据如下
$ r3 a7 F- t0 U2 o5 8 6 3 9 1 1 7
: x! k' L( n& p7 H
在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
如果数组是用vector定义的,即：
vector nums;
//或
' \# G( r2 g5 Q; L- gvector& nums;
0 T+ k) L4 p1 d0 c& K$ ?，则这样写：
( i+ Q2 L* g6 ^* R/ c! |6 ^' T3 @if nums.size() == 0:
# _7 h+ P: l: L4 c, qreturn false
方法二：
如果数组是这样定义的，即：
0 @( p7 T: F) c% ~5 }int nums[] = {1,2,3};
先算下数组长度：
" T" t$ a2 e' {4 E: I( onums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
, ]* D7 }$ r- |) N0 R& Fif nums_length == 0:
: |! @5 p- G: T  s' E) p* z2 t8 rreturn false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544
( {% n! E& I7 r% `
- H; M9 N$ m% u( t& `( `) e解决了上述问题以后，最原始的冒泡排序如下
% z. H# O7 U) m. v- L
#include <iostream>
#include <string>
7 _0 `- ?" Y/ \3 uusing namespace std;
void BubbleSort(int a[], int n)
. U0 A) s( W, c8 c- c: q6 v/ q{
  c" }' B( G( y% t) J! p        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
  z' i5 {" X/ w1 C        {
/ }" [; T+ j. I  ~7 r                for (j = 0; j < n - 1; j++)
                {
( _; g' f3 l- J+ s$ N                        if (a[j] > a[j + 1])
                        {
: I! v  Q: c' x* Q! C3 t: I                                temp = a[j];
7 |0 W7 G. C4 t% q+ `+ G                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                        }
                }
  R8 g" F4 P8 f4 F        }
2 T0 j. I: m& ^        for (i = 0; i < n; i++)
                cout << a << " ";
( w8 I+ C: C7 ?! x7 S}
int main()
) f) ~" y! J  `9 H- s{
        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
8 e" ^+ i8 f1 X7 p        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
) K  f) c! M9 {        return 0;
) c# k2 {- }+ n7 }! s3 A2 S3 X1 D1 X}
; F6 n9 Y. P4 A
" ?: ]2 `) H4 j) A& t# M上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
! P, a9 w$ ~5 j2 _& i: r那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下

#include <iostream>
#include <string>
using namespace std;
3 p( G4 v( v, o! o! wvoid BubbleSort(int a[], int n)
( q3 `" m% I& b8 k{
& L1 D7 j; Q% w* k        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
                int flag=1;
                for (j = 0; j < n - 1; j++)
* ?, r) K& K2 F! k, F- A                {
! l7 ?* K+ M. j                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
$ l( S0 g/ Q0 l& o+ h                                a[j + 1] = temp;
6 F6 `1 b* o. B9 d- R. ^                                flag=0;
- n$ N  u6 V# }( ]0 l5 C% T                        }
                }
+ S) c1 |- i1 e8 K; d                if(flag)
                        break;
        }
        for (i = 0; i < n; i++)
$ Q- F3 r8 U2 C. |4 N/ h$ s+ w                cout << a << " ";
/ C* p, k, p! `" v" h}
int main()
{
        int a[8] = { 5,8,6,3,9,1,1,7 };
  S/ S. y/ K3 D) U        int b[4] = { 0,2,3,4 };
4 j; R( T# ^& N7 r) |) u        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
% B0 e6 r- g; ?6 F- _4 m* f                BubbleSort(a,count);
4 C; Y( `" t0 T4 t$ d0 o& {        return 0;
6 K5 y' t3 k8 e; F. P: F}

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

#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
( q! N0 r3 l7 P& Q{
) c- Z( X( i' ~3 S( h        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
6 B9 \. o6 ~7 p/ o% N+ f; w        for (i = 0; i < n; i++)
; e. W8 a- I. t3 z; d  J, C        {
                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
* M2 }! L/ Z/ I4 h8 S* \5 ~) b                {
                        if (a[j] > a[j + 1])
8 B$ F( y2 W" x, u) V7 c" E                        {
. h% }6 O2 u0 F7 Z7 P+ W                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
7 h  P" y3 I) W; g# c: k  G& [" R                                flag=0;
. B1 j1 I& |1 S* {9 L                last_exchange=j;
                        }
; c+ r: Q! Y- G" M& ^                }
# ]. R3 ^  V$ D( z! W, o# ^                Bubble_Sort_border=last_exchange;
                if(flag)
                        break;
        }
/ x. ~  i8 U$ A. }: g        for (i = 0; i < n; i++)
                cout << a << " ";
8 Y% W' t, O( o( O$ Y0 f}
int main()
{
$ R0 w3 H" \0 C) _* x        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
2 ?$ d1 F* W" ~. u8 A* H: D# U        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
2 |7 U3 ~; J3 C0 `}


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

/ ]4 q# I$ X6 s# m" S' p8 f. u鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
: |. o9 x9 M& P, Q第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下


#include <iostream>
6 C' e3 C* F6 |4 k, G% z: W1 c9 K#include <string>
using namespace std;
) D$ M. s4 z! K( I) G7 bvoid BubbleSort(int a[], int n)
# F# R- M, S( J" g, e{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
# i* D, l+ ]/ X3 g& f        {
                int flag=1;
                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
# \& x1 {& Y( |/ L6 c                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
' z0 \! U3 C) {% U' B1 d9 j9 S- o1 g                                a[j + 1] = temp;
                                flag=0;               
                        }
                }
' w* T9 C) M- d7 h& }                if(flag)
5 F3 ~* {, d3 {+ E2 P+ H0 }9 B3 `                        break;
  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
% D0 i. A3 `  f( i1 H+ N! C) V2 C                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a[j] < a[j -1])
                        {
6 G9 p2 z; }4 y! ^                                temp = a[j];
                                a[j] = a[j - 1];
                                a[j +-1] = temp;
8 a% a! D* I8 U1 E' v7 C                                flag=0;               
7 j1 j$ Q9 _0 S- c                        }
5 ^# X& Z' v  }5 w3 e                }
                if(flag)
                        break;
. K7 v: \$ y9 h3 ]$ w1 f        }
        for (i = 0; i < n; i++)
                cout << a << " ";
) D8 H6 Q- n/ ~. C; k) `7 A}
! y# D2 i2 D/ O& D- \* X& \$ xint main()
/ k% c1 M  E+ B1 b. g* m: i{
        int a[8] = { 3,4,2,1,5,6,7,8 };
* }0 k& u7 k! O. _. u        int b[4] = { 0,2,3,4 };
7 v  W: j9 Q$ F. c        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
' }) q0 N, S) V- B3 `}
$ z# ^6 b+ r) W8 x/ B

以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
- D" }2 O( o( g/ n5 q& V- y7 B
————————————————
9 B: O3 C4 W/ b版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 {7 z# D. O" y5 q, [- b原文链接：https://blog.csdn.net/delete_bug/article/details/105928524

7 p, S! h* R$ @7 f* U' `$ [
3 X. s6 \( n* W9 d% B

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5