数学建模社区-数学中国

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

---

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

关于冒泡算法的那些事儿排序算法的复杂度
7 U) f' i- x; W' ?* r
( h1 |: b9 k9 l
+ N6 ]1 R, e0 ?, z) g; P" @8 j
9 ^" [7 c' Y# j$ _! S1 b关于冒泡算法你了解多少：
首先我们规定数据如下
4 U+ u3 ?% `6 Q& U5 8 6 3 9 1 1 7

9 b1 L7 R* h2 B- s' _  C' r在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
* _& M7 }+ T) U! U# J: w如果数组是用vector定义的,即：
vector nums;
//或
vector& nums;
，则这样写：
if nums.size() == 0:
return false
方法二：
' `" G" p3 }+ j3 I& C. J! \2 _如果数组是这样定义的，即：
% P) ~- h. }1 J! e: I& r3 aint nums[] = {1,2,3};
先算下数组长度：
+ Z! d( y  K/ g; _8 ~nums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
; ~2 S6 a& S; R& fif nums_length == 0:
return false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544
9 X; _9 G6 C$ I8 `& I6 q$ T
解决了上述问题以后，最原始的冒泡排序如下
. s$ B) W  i8 }6 ]9 w+ z9 E
#include <iostream>
0 ]  I4 E, b6 ]+ l5 `5 Y#include <string>
using namespace std;
/ S  t$ P) f% {% g# w( Vvoid BubbleSort(int a[], int n)
- w. K3 ~# v8 f3 d4 c{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n - 1; j++)
8 S, [- {1 i7 i! @# `1 G9 f                {
                        if (a[j] > a[j + 1])
/ P# e6 F! g" M2 M- @                        {
/ \8 ~) y9 s% J. D* w5 V; p& J! `                                temp = a[j];
1 ?  r( }2 D; F4 ^                                a[j] = a[j + 1];
7 k+ j3 k' b' z# o                                a[j + 1] = temp;
                        }
/ s3 Z" p9 ~7 }: m' P% F1 ~2 V                }
+ I, ^+ j8 b' q  g8 Y        }
. _  Y2 R5 N: @: R' u* u        for (i = 0; i < n; i++)
                cout << a << " ";
}
% X% j( ]! ]+ [: O: _4 D6 pint main()
( l2 Q5 t7 w) @1 Z{
, I8 y. }! I% z! A/ g        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
/ V+ G+ ?! G7 r+ C- _1 t- Z        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
0 h: s0 g% i2 R+ r+ I; P# Z                BubbleSort(a,count);
        return 0;
& i* \7 f- @6 y& M3 D}
6 [4 b& @0 R& d8 l" u
上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
. U" X, v% K; _* X3 H9 J那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
9 ^+ |. O1 ~. z
2 g, v  m: B( A4 e/ R  c" o5 [#include <iostream>
2 R* `+ }5 q3 j; Z7 s: P# q#include <string>
) H3 r/ ~( ]( T& j! M1 kusing namespace std;
void BubbleSort(int a[], int n)
; f' `3 t' W+ d- S, w{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
                int flag=1;
                for (j = 0; j < n - 1; j++)
                {
+ \6 n# R3 i1 w+ E: i                        if (a[j] > a[j + 1])
) x6 Q- Q3 d: W7 J8 ?0 G+ S                        {
% ]0 S6 e! N9 F) g' C2 ~* q                                temp = a[j];
7 R! A$ _, r" C" r" y                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;
                        }
  K; H. N$ J# E8 g/ ^                }
                if(flag)
                        break;
( i. }+ P. p4 `9 c( M  k        }
        for (i = 0; i < n; i++)
. S" j- @5 K5 u# l                cout << a << " ";
}
int main()
{
        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
4 U$ \  \3 _8 P; T. z! N  \        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
0 ?4 O. p9 O; U1 S                BubbleSort(a,count);
, i# k0 F5 c) c. e" M+ {        return 0;
}

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

#include <iostream>
9 V, Z& U8 B5 p+ i" C#include <string>
( c; E8 p& }# yusing namespace std;
void BubbleSort(int a[], int n)
  M- }  ~8 @. l" g: |" D{
  j5 x& L& ^) I. h1 ^        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
4 W2 i' {; [7 E, [9 c        int last_exchange=0;
# a: h+ i' U+ s7 J        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
                {
6 H# J9 J/ I, n; Y2 k1 L                        if (a[j] > a[j + 1])
5 P) w- W% _) f  s# O                        {
                                temp = a[j];
2 a/ N9 i& P2 L                                a[j] = a[j + 1];
/ r9 M0 t$ X/ n  [: Y                                a[j + 1] = temp;
                                flag=0;
) d0 R/ \3 r& G- u                last_exchange=j;
                        }
. }1 e0 k& |; U. P                }
                Bubble_Sort_border=last_exchange;
                if(flag)
' n. r1 y" k% }+ |  \                        break;
9 X; A5 r- i2 p: V: T% c7 e7 V+ k0 }2 ]) l        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
! K6 n/ m) u5 g6 Q2 [int main()
9 c( F3 J' m+ @{
3 L* m- w' ?" }* w        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
" \, T8 ]1 X1 Y3 @. Y+ ]        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
  B7 f. W! |6 _7 j8 C9 _, \        return 0;
7 {0 l0 Q/ I4 y6 I% Z}


0 @' s9 n, W: B% K+ [! w' v8 A到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
  |! w3 Y0 O0 e# q  z% R上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做
9 g- C0 X7 R! H9 x# O2 h; R! x! N
鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下
8 ?9 ], ?$ c) L! Y, m

#include <iostream>
' |! d" I9 M2 G; ^( h; _#include <string>
- j3 }2 [$ E6 r" dusing namespace std;
void BubbleSort(int a[], int n)
{
' j% Q% Y# u" i8 N2 m" ?        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
        {
3 {8 X  S8 d& o2 [                int flag=1;
& U; S! |" O, a4 n8 A* X  Q                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
# i5 D; P" Q( N3 O                        if (a[j] > a[j + 1])
                        {
& J# _, E- d" x2 \  W# E                                temp = a[j];
0 t5 V: n! u' V2 r6 _( g; _, ^                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                flag=0;               
. B% s: k3 S, R6 _! t, ]4 h" m. x                        }
2 n6 R: a; i7 R5 N6 U' N1 H5 k                }
                if(flag)
                        break;
5 q. k+ U5 ~$ A7 V  B& [  // 偶数轮开始之前  flag 重新置为1
7 N/ r. i5 O, G( ~% |9 p                 flag=1;
! X% u$ H! n# x9 w                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
& @5 Y/ o' D! ~" [3 ], r                {
* W7 Z1 I' F& `- _8 u' ?                        if (a[j] < a[j -1])
& E7 H8 i7 s; A7 u' |: n                        {
+ t$ N1 H4 z3 Z3 i  J6 g                                temp = a[j];
                                a[j] = a[j - 1];
                                a[j +-1] = temp;
, T' Q0 ?$ q* @" q% Z4 O8 V! P, s- f                                flag=0;               
  G$ e9 s9 [$ d  Y: s' o$ \# D                        }
+ m8 G: A: k" p, s/ j* w% O4 C: C                }
$ J9 E3 f1 W2 r4 I                if(flag)
/ o  m  W( V; M2 A                        break;
5 |. o* s& g1 ^( e# n# X. T# L        }
+ Y$ c2 O) d5 n8 e( Q3 \8 N        for (i = 0; i < n; i++)
4 o# U, t7 m# G- j                cout << a << " ";
}
: I9 g1 F7 l, b: v* [. D+ iint main()
{
1 o6 p/ M8 C3 a6 V) ~        int a[8] = { 3,4,2,1,5,6,7,8 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
9 O5 R7 U4 r; v                BubbleSort(a,count);
        return 0;
5 A9 |* C4 s; i$ u3 V  b}
, P4 q5 _: W6 O; V% G0 j
/ t: j5 e$ A' d$ _
4 g, D" A& G$ C2 s* _. W以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
/ f1 H& f% A+ k$ Y3 |
————————————————
9 F) a/ q$ E$ f& `* x) ^版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
( g( Z' a' q% W8 z" R

; c0 R) x: x% i8 n

---

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

Powered by Discuz! X2.5