数学建模社区-数学中国

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

---

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

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

! U7 d9 N% ~. v: j5 T9 t5 B

0 C& c. l7 J9 H  U5 q, c+ ]关于冒泡算法你了解多少：
首先我们规定数据如下
5 8 6 3 9 1 1 7

. M4 a9 J( \1 V5 `/ p在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
如果数组是用vector定义的,即：
: B, \6 c- E% R- ~; c" Q: [8 yvector nums;
//或
vector& nums;
# L# e0 b8 o) u6 A，则这样写：
9 o: o& t1 P( Y. o6 Tif nums.size() == 0:
return false
方法二：
& z8 w* C/ {0 {如果数组是这样定义的，即：
* p* ~2 X6 S% f7 yint nums[] = {1,2,3};
先算下数组长度：
nums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
if nums_length == 0:
& H5 K+ i& E. v$ o3 K$ e' O" W9 O- kreturn false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

解决了上述问题以后，最原始的冒泡排序如下

$ _+ q1 F0 ?) o#include <iostream>
#include <string>
9 a7 G  }* w4 M0 uusing namespace std;
void BubbleSort(int a[], int n)
{
7 i& l0 E& [8 n( H: }* g5 L2 r        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
( ]3 @# d8 ]- v# _! j" M9 ?        {
. G; L, _/ h! Y" t2 b' O                for (j = 0; j < n - 1; j++)
& g+ y- k  w' @  l                {
                        if (a[j] > a[j + 1])
; S1 h$ k$ W) l6 m% R8 c9 A                        {
6 G5 D0 V' \/ q. T" F' h                                temp = a[j];
! M' v1 K) c3 h8 T                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                        }
% _& O/ r  L+ E) q) ?* z( o                }
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
/ D  b4 \  v( X* w* U}
6 {2 b  L( o7 A/ k+ K0 \# |0 Rint main()
{
        int a[8] = { 5,8,6,3,9,1,1,7 };
9 W3 S9 z# f7 s- K! B/ `        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
( f+ x* I( ?) T        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
( E( e) t$ R  R$ c5 D                BubbleSort(a,count);
        return 0;
; f. Y  ^( Z( c# t}
4 U  W8 q8 S* `8 x
上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下

' K; X3 V( N( G- }; j$ o#include <iostream>
& c5 ?. E( |4 u' H+ Q#include <string>
5 x, O6 H* l, N$ Cusing namespace std;
void BubbleSort(int a[], int n)
{
( P2 w/ U5 f8 X5 `        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
. t6 T& o* v# f# o+ O+ F# F        {
1 f; Q3 j; V8 t" `" v7 E% `8 Z                int flag=1;
                for (j = 0; j < n - 1; j++)
                {
                        if (a[j] > a[j + 1])
                        {
) k4 O: s, h) n0 J% a; z5 z9 _                                temp = a[j];
) }, h, m7 Y* S2 a# t                                a[j] = a[j + 1];
! [: e! g) A6 j% K- X% x                                a[j + 1] = temp;
                                flag=0;
: ~3 v7 Q$ K, N' l                        }
                }
                if(flag)
                        break;
, r8 Y/ B7 K0 K2 B        }
; I/ t+ Y, C: u" o% ]        for (i = 0; i < n; i++)
7 T* J9 K5 f/ e9 @* w' L                cout << a << " ";
}
& K' v6 B$ |5 h3 Nint main()
3 V& H$ T) B5 W4 f) f{
        int a[8] = { 5,8,6,3,9,1,1,7 };
4 `6 f2 ?) z/ u- h' M+ S& k* w        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
0 Q+ i- `  }1 a% j& x        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
2 l& |$ [: H" g2 S9 R8 L" [                BubbleSort(a,count);
        return 0;
/ |8 d& `7 n# Z6 _/ i; }}
) W5 a1 c: B$ ?* P) d
, k8 d4 |, m% ^4 }4 f那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
  j) J/ T; h7 [. E( k4 t3 ^这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下
( L/ D- B3 j$ i/ T8 W! f( f6 _
* P- e. Q0 P/ o1 o5 p$ i#include <iostream>
" [0 X) U* q5 S' X( t+ x. [9 Q1 c% b#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
4 d4 N$ X, p5 V- s/ l! \( t# N        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
5 j. i0 h: z! ~; f        int last_exchange=0;
        int Bubble_Sort_border=n-1;//无序数组比较的边界
1 r* N: @: @3 j4 H8 \; p, W0 q- j        for (i = 0; i < n; i++)
' c& G- i. Y  m% i: P4 z5 |        {
                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
3 e  S3 f8 J# {8 N- z. m, g3 q                                a[j] = a[j + 1];
0 `0 l& j1 J# O/ t- [- T/ l7 [* K9 A                                a[j + 1] = temp;
; e. k- w, ~0 K' V                                flag=0;
                last_exchange=j;
                        }
                }
$ a$ |; O* \* }) j& T  z' s% R                Bubble_Sort_border=last_exchange;
: M5 x; y( e" [& K- n                if(flag)
                        break;
1 O- Q( c* A" F+ }        }
        for (i = 0; i < n; i++)
0 e0 q* W/ d- v( B$ C                cout << a << " ";
% z. P/ E( p- r- ?7 R9 L) o4 B}
& T: z) _9 @) m5 ~2 {; b3 Gint main()
{
: a8 v: b4 `; j- S& d        int a[8] = { 3,4,2,1,5,6,7,8 };
( b* h% }& z: R# u7 w& t2 |3 [        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}

9 Z$ y+ N/ _- }/ H/ w9 Q) `- ^
到这冒泡算法就结束了吗，不可能，你在看看这一串
& U4 i- D# ~9 X/ y2 3 4 5 6 7 8 1
5 B6 o, L# U, U) u8 P上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做
& T& C7 C$ k0 Q1 \7 t, c5 g
鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下


) A6 N, b1 P  X+ \#include <iostream>
! o$ O4 z7 M- w5 Z#include <string>
# I4 r: \4 A% Z( `- ~+ zusing namespace std;
7 s& f# x! S- H3 l- M( ~void BubbleSort(int a[], int n)
" g5 Q, G% I# _( X- \3 w{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
% D1 ~* c# `  e6 O* A- W6 f7 H2 b$ D        for (i = 0; i < n/2; i++)//奇数轮
        {
                int flag=1;
                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
! M5 i& D' b. |3 v5 B7 H) L$ a                        if (a[j] > a[j + 1])
                        {
7 {, d+ s8 D3 d1 ]' m! t                                temp = a[j];
3 h: y  [/ L# t  ^* C' Y! |1 ~; O8 X                                a[j] = a[j + 1];
                                a[j + 1] = temp;
6 ^6 t4 y) t* M* f6 I: `' {  N, y                                flag=0;               
                        }
                }
                if(flag)
                        break;
  // 偶数轮开始之前  flag 重新置为1
! |" M6 V1 G' y( t( }3 i                 flag=1;
, m* e; Z: R7 y( y# t                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a[j] < a[j -1])
+ i" `& o) R* d0 K2 m+ ^                        {
* r5 D" U8 w+ Z" w: U) t                                temp = a[j];
. u6 t8 _. V) n, F5 I                                a[j] = a[j - 1];
9 `$ B; w  @& K4 x, B                                a[j +-1] = temp;
                                flag=0;               
                        }
( I+ w+ z% M( s6 @5 T4 `( |                }
                if(flag)
                        break;
* L$ @- o, _0 T% z+ ~        }
2 Y3 D- q5 p4 s0 F/ r2 U% I6 W        for (i = 0; i < n; i++)
; J! D2 I. E0 n- a$ H+ g6 ?2 m                cout << a << " ";
5 [- Y0 I& g8 u0 Y" F}
& G5 ~! U  C- D% K3 g' s# rint main()
{
- e; v$ P* B. G" a# _        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
7 F; W" H# I9 T! x' p& e" p        int count = 0, i = 0;
8 [. V6 a9 w* P/ ?( F7 e        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
& j; |3 ^/ c+ Q7 n+ L3 V5 K) {7 h8 g                BubbleSort(a,count);
        return 0;
- ^  u# U% o% S; ?0 ~& E7 u}
4 ^; a  k4 Z# W- {4 R( n( I8 a

以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
2 m5 y4 E# j; U) o
3 F& I( g& v" J- b! `' l————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524


  m3 i( Z8 r4 P8 l/ H1 Z9 z

---

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

Powered by Discuz! X2.5