数学建模社区-数学中国

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

---

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

关于冒泡算法的那些事儿排序算法的复杂度
( i* f8 ], ^2 R
: x  h" Z. A1 f; }- P

9 b- M- d' |1 g' ~# Y# s关于冒泡算法你了解多少：
首先我们规定数据如下
2 h# u( k" G% P  r" s6 [& r5 8 6 3 9 1 1 7

- j6 E  P5 N/ g9 k" h在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
如果数组是用vector定义的,即：
vector nums;
! v8 i9 G) @7 y" `7 `) x* Z//或
vector& nums;
，则这样写：
% w& @( P, h) R+ [2 Fif nums.size() == 0:
" u/ A  v% Z2 {return false
; a' V" y+ M' A# W  h" R" n* o9 ~方法二：
如果数组是这样定义的，即：
int nums[] = {1,2,3};
先算下数组长度：
0 O7 l6 J( _2 ynums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
if nums_length == 0:
return false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

& P; `; A6 ?# l; @1 l" I* O( @8 f' g解决了上述问题以后，最原始的冒泡排序如下

( j/ v) G) A/ E#include <iostream>
#include <string>
+ y2 _& y- K4 R9 {& g+ j9 \- O3 a* P8 R2 iusing namespace std;
- T7 q! z! ]" e4 r. Yvoid BubbleSort(int a[], int n)
{
0 Z4 Q8 d, ?: u& l' w3 O        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
' Z) s% g/ A) c: f! K) l3 R) g        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n - 1; j++)
3 j3 `. j! w% O7 P                {
1 k- v0 C, h$ B# t4 R9 O- D- P                        if (a[j] > a[j + 1])
                        {
! y# J2 i+ ^) g. [                                temp = a[j];
; v: }' ?- D# o                                a[j] = a[j + 1];
                                a[j + 1] = temp;
8 A4 }# Q6 _8 i. f. I" e                        }
4 H, r+ ?* u* ?- V% n& T! ~( j                }
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
* n' X. v4 D) Z- w. {$ dint main()
{
        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
$ [1 K+ E) C+ f+ i' E1 J  u' x        int count = 0, i = 0;
6 N8 J9 G+ a* S/ f+ e) L% X/ l8 z* N        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
' e& p( J- b7 W5 w5 Z0 N        return 0;
}

上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
; W7 z1 K; \' M, K7 V; B7 w那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
5 F1 @, n1 ?. }* X% s, w
/ L, z- X3 A* Y, Z- _& W#include <iostream>
#include <string>
$ @5 g6 @' y# zusing namespace std;
- E, W) k6 [8 x: M! U; F  Yvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
( t% V0 B' `) M3 ^* A, H; J3 N        for (i = 0; i < n; i++)
        {
                int flag=1;
$ F% {2 u. ?) B# h9 R  b                for (j = 0; j < n - 1; j++)
                {
' U; F' h& ^* M. x1 g" j                        if (a[j] > a[j + 1])
( X# V' ]$ s) g2 E8 L; C& u  Y                        {
                                temp = a[j];
                                a[j] = a[j + 1];
7 J2 t6 d8 W; [3 L  `( a                                a[j + 1] = temp;
& H7 Z( ^) T- y! ^% F                                flag=0;
                        }
                }
7 {) C- }4 Y  {6 X% p                if(flag)
                        break;
        }
        for (i = 0; i < n; i++)
7 P6 g! E" h4 `, D. u( Q                cout << a << " ";
}
int main()
3 a. i7 n! g# w8 `( l0 m, A{
        int a[8] = { 5,8,6,3,9,1,1,7 };
6 d( ~% R' F/ d        int b[4] = { 0,2,3,4 };
- C. b* q6 }+ @: `/ B/ m2 A6 ?        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
5 [! t  ^* N& l( Z$ |7 I7 t/ P        return 0;
}
& W# T( V0 i( F  X7 r  Z; U
$ A, Y& }2 f; S+ e/ ]& j那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

$ Z, j% d9 |' \: W! a7 U#include <iostream>
* q% M! L2 [. [+ T+ k; y  W#include <string>
using namespace std;
, S  _! h8 {5 K* s4 q( H* T" Wvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
- O* t; d$ e7 s! n2 Y4 l( c- V* A        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
$ W7 \; y2 J: o7 c, S        {
                int flag=1;
' n4 U! Q9 V; R5 s                for (j = 0; j<Bubble_Sort_border; j++)
8 L1 S; l7 m1 |9 g5 I                {
                        if (a[j] > a[j + 1])
                        {
  e5 g- P6 a  O! w( q                                temp = a[j];
& c- k7 W; \: J- T. b                                a[j] = a[j + 1];
  y" c% P' R9 E                                a[j + 1] = temp;
. L, @$ J. A. }+ V$ y                                flag=0;
                last_exchange=j;
                        }
( c6 G2 w2 `8 C: P! Q                }
                Bubble_Sort_border=last_exchange;
8 ]9 `" e; l, N# H8 ~  m0 B! H                if(flag)
                        break;
6 ~" \% z- N" E) c7 ~3 \5 w# s        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
" }- L5 F5 ^7 }3 L; a3 ^& F. }{
        int a[8] = { 3,4,2,1,5,6,7,8 };
; Z* G, H- M( d* a  E" H        int b[4] = { 0,2,3,4 };
# D5 ?% V  L; M        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
! X; U/ o/ n, _& U% J( S3 \                BubbleSort(a,count);
        return 0;
+ R' m2 t# D, A}
: h9 ]: Z3 l" \) C, p% h. W. {
; o, Y+ s  k; i( x1 @) @
' U; G2 i" p8 Y' G1 B; A0 V; R" ?2 y. }到这冒泡算法就结束了吗，不可能，你在看看这一串
  Z5 \6 ]/ F! e2 3 4 5 6 7 8 1
% C9 S* ]+ c# i' T上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做
. e' F6 e3 f/ {
! V/ a/ Y, G& F2 n3 V' X4 [鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
5 [& I% F- [: p5 T第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下

' M8 a0 ~3 s! S# L
/ t/ X/ o$ Z8 Q: I0 J#include <iostream>
#include <string>
' G" k! H/ g  Y/ vusing namespace std;
6 V- y2 L5 ]3 C5 G+ Q1 e, c- bvoid BubbleSort(int a[], int n)
8 v+ ^' Y% ^" `2 o{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
3 T$ R! i( N9 M5 t4 u        {
                int flag=1;
# s% a" E( q' `+ S; c  }" \. G                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
                        if (a[j] > a[j + 1])
                        {
! {( g- F. a  F                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
2 _* H, D" ^& Q" @                                flag=0;               
                        }
                }
/ Y( q" p+ a: x$ P" T                if(flag)
                        break;
  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
6 D1 J) q$ q, X" L" p% X% E. J, h                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
3 x  W8 g; g- b8 l1 I                {
                        if (a[j] < a[j -1])
: W- o, x7 p  G# ^                        {
                                temp = a[j];
                                a[j] = a[j - 1];
. M: `- U8 Q- K; }                                a[j +-1] = temp;
* d5 ?+ T7 a2 U( r                                flag=0;               
- ^9 G/ k  V, F                        }
9 Y2 k; j* [5 {5 ~0 @                }
! u1 n* T% O, E1 w# S& d/ [4 @                if(flag)
6 k' ]4 z5 J* u                        break;
2 i' O, S, V, O$ K0 N; r        }
( I. d; l  S% X        for (i = 0; i < n; i++)
                cout << a << " ";
3 P$ q( b7 G6 s}
int main()
{
        int a[8] = { 3,4,2,1,5,6,7,8 };
/ r" ?0 m# l9 p: H. ^* I        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
" F! Y! h2 J$ |, o# P6 V' w        return 0;
}
  c! w2 M8 d* j' ^6 H4 S2 @9 h, Q

1 M) _$ Y  ?* E, c3 V/ K( l以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序

————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
5 T4 g  L. u& N' Z( p5 [$ O3 ?) L0 E
: ~' {1 c( h2 ?, i" z& q/ x6 V, m! r
* n, E5 N+ J; ]& \

---

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

Powered by Discuz! X2.5