关于冒泡算法的那些事儿

杨利霞

+ q* H" p+ K+ k; {+ T5 F关于冒泡算法的那些事儿排序算法的复杂度

, C& ]; c, [) p0 v6 P# L8 X) _
/ h& ]- I* T8 J* Q5 a/ N
关于冒泡算法你了解多少：
首先我们规定数据如下
" X5 |4 Y2 n: {5 8 6 3 9 1 1 7
' Y$ F( j9 T& g% ^0 I7 H
* x0 R; p& q6 t& ^在对数组进行冒泡排序的前提下，首先求出数组是否为空
) W6 a$ Y- H1 B! H- J5 w1 ?方法一：
/ C9 A% J1 {% c% Q  @如果数组是用vector定义的,即：
vector nums;
* ?8 f! S9 J5 w- T//或
1 b9 P. |1 G$ w6 A# B. Hvector& nums;
- y( R. i% p2 W% Z" L9 G2 m，则这样写：
: I9 W5 q% V6 w7 r0 }7 w. gif nums.size() == 0:
return false
3 @5 E' {$ a6 m" A7 G方法二：
5 m1 j* `; [! G1 k如果数组是这样定义的，即：
int nums[] = {1,2,3};
先算下数组长度：
7 A& \7 g1 |) Y5 |* w5 ~nums_length = sizeof(nums)/sizeof(nums[0])
然后判断数组为空：
if nums_length == 0:
+ J6 z& F- v$ a9 D. u9 |' dreturn false
" L* ]+ J! N& x, P1 @* L& P' L! t原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

* g8 I( E# y1 b; Y/ F  l解决了上述问题以后，最原始的冒泡排序如下

#include <iostream>
. _& a5 L, g  A, U9 Y3 X: s#include <string>
$ {7 Z: B# d: @# i: b, Susing namespace std;
void BubbleSort(int a[], int n)
{
$ W9 H/ A7 v, k8 b* J# j5 V        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
( Z& ~$ A* c1 x8 A$ B* ?        for (i = 0; i < n; i++)
; D8 b: l! q; _- J- u        {
                for (j = 0; j < n - 1; j++)
                {
                        if (a[j] > a[j + 1])
/ o  A. G+ t4 f: u0 ^9 p                        {
                                temp = a[j];
2 o7 L, ~: W0 x  E" u                                a[j] = a[j + 1];
                                a[j + 1] = temp;
/ b( A7 l5 ~0 o+ |0 [2 u/ {" G9 v1 x                        }
                }
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
! ~% N' e8 F9 A! W}
int main()
  b( m1 j6 }. ~% E6 H{
) p0 P) j# V( X1 M; z/ H" X8 [        int a[8] = { 5,8,6,3,9,1,1,7 };
4 H! `& K1 c; _9 L        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
  q: T3 T8 H7 q9 F        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}

1 ^9 H& H7 b2 a9 {/ e' x  e上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
/ Z3 h# ^, t% S0 Y& |
#include <iostream>
#include <string>
using namespace std;
; T8 s/ I7 m, x, a7 rvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
. v: v* X' P" p$ {0 D+ u9 k. _% C                int flag=1;
                for (j = 0; j < n - 1; j++)
3 l8 B/ O& `; r& X' z. @; F                {
                        if (a[j] > a[j + 1])
                        {
  L7 y9 O6 Q2 z: K" J                                temp = a[j];
                                a[j] = a[j + 1];
7 c1 o# J/ G3 q1 P- H                                a[j + 1] = temp;
1 M0 A$ D3 |. s6 B# _1 V                                flag=0;
                        }
& L3 g0 r& y! i" P                }
                if(flag)
5 W" _3 M% d  m6 y                        break;
  c" I1 a& o1 B$ X! d! Y        }
        for (i = 0; i < n; i++)
                cout << a << " ";
}
6 v# D# @- `8 D0 v! Q5 zint main()
- _) L' ?" h$ {, A! Q% D, b{
        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
% e0 f/ K2 s/ z        int count = 0, i = 0;
1 i' e, Y1 P9 g- _) X& c        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
+ |0 p6 g& @7 s" w9 |        return 0;
$ ~" y; }" H! {  I5 T}
; J& e; {) E5 g' e# `
& G3 ~" n+ O( B6 I# l* [那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

#include <iostream>
#include <string>
using namespace std;
3 w' [8 U: U% O& avoid BubbleSort(int a[], int n)
{
0 i9 @5 _. a. X# k2 D7 }* b* q/ }        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
+ _7 ]2 M, }0 N7 V- a        int last_exchange=0;
/ s6 _9 ]2 ?/ b, A& ~% F+ A        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
( e9 W+ y( L. g0 S        {
                int flag=1;
6 N; ~8 f3 r- k0 m                for (j = 0; j<Bubble_Sort_border; j++)
8 H) P6 x% `# W  ]5 j                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
& ^2 t! t2 V& s6 p7 E! g8 N, g# N                                flag=0;
                last_exchange=j;
                        }
                }
; I, s8 F, A2 }- B+ O8 B                Bubble_Sort_border=last_exchange;
* O3 b  C# E) O  U3 @# ?& w9 s                if(flag)
                        break;
( U4 l. Z9 o1 M        }
7 F$ r( t/ M4 v* R4 j3 B0 k        for (i = 0; i < n; i++)
5 I, ~2 X' l& e& y. N                cout << a << " ";
}
int main()
{
( Y; J8 ~) Y5 u' c        int a[8] = { 3,4,2,1,5,6,7,8 };
; {( c" Y+ J2 t+ C8 d0 ~( w        int b[4] = { 0,2,3,4 };
( R2 {% U/ k& f( \/ C        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
. G4 K' S1 [8 C$ ]7 R1 u8 V" K) v                BubbleSort(a,count);
        return 0;
}
* |. [9 k: @' q2 C6 X; ^' S9 ~: w

5 U1 F3 i1 e/ `3 W到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
基于冒泡算法，延伸出一种算法叫做
' r8 b' U7 J( N- K3 ]
1 c/ \2 T& x; i8 t4 D) c鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
/ G7 }* g$ F* o& Z1 u. q第一轮，1和8交换，
* N: K! k# s; i- l/ R第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下


* @& f. L0 g7 y, J7 Y. W#include <iostream>
! O3 n; z% ^. V. u3 u: N8 I: ]#include <string>
using namespace std;
" w8 A  |) G. r7 uvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
        {
                int flag=1;
4 G- [! [, d7 v! {2 o                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
% k6 ^2 q' P" S5 J                {
                        if (a[j] > a[j + 1])
; ~0 y+ Q" f& \. W" U) T& z/ @+ o                        {
3 A$ z% p" D7 `/ D& d- W; Z                                temp = a[j];
                                a[j] = a[j + 1];
9 o1 }" [- C. c5 c# c* L* @                                a[j + 1] = temp;
6 ^# f) V0 v' m* B                                flag=0;               
                        }
& ?; k# w$ Y# `' H                }
                if(flag)
                        break;
  // 偶数轮开始之前  flag 重新置为1
% F1 F9 E1 _2 O: ^) f. {6 @+ ]                 flag=1;
                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
2 e3 K1 }- n# M5 w! g                {
                        if (a[j] < a[j -1])
                        {
( g* L; w' F+ J8 P% d3 _& R                                temp = a[j];
6 `# U6 j) u5 N* s7 q                                a[j] = a[j - 1];
                                a[j +-1] = temp;
                                flag=0;               
                        }
/ |7 P4 j/ }7 U( K- w# Y                }
8 b  m# I- D  Z  J( _                if(flag)
/ V  E* H- L* a7 C2 v# _0 N                        break;
        }
        for (i = 0; i < n; i++)
                cout << a << " ";
$ v' B1 B7 b, G, N}
int main()
{
        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++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
: W4 p) v7 n9 [) O* n5 c$ A. G        return 0;
  H3 Q9 N" p* v}
# h: W+ t# D0 f8 g5 H
8 T/ l/ O' D* v" {8 u4 i( r- c4 M$ H7 M
以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
3 v: ^$ H/ P3 Y# x0 a0 i/ a2 T
' j, ^4 w4 l" O8 M  r; K————————————————
3 O4 ~. F2 o8 `3 |0 u版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. m! f0 L/ \$ [; @6 b原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
. ]. J: h5 _# U, @3 O
" y$ p6 E, c5 W, w9 @4 @  M