关于冒泡算法的那些事儿

杨利霞

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


7 K6 b# l. Y& Z/ L
关于冒泡算法你了解多少：
7 E( y! e; m% W/ R首先我们规定数据如下
5 8 6 3 9 1 1 7

& l$ M" b  M2 r! m) J在对数组进行冒泡排序的前提下，首先求出数组是否为空
方法一：
如果数组是用vector定义的,即：
- K. X- ~0 H% {4 Zvector nums;
//或
vector& nums;
，则这样写：
; j$ ^6 g( t  zif nums.size() == 0:
return false
: d# H& u- H/ ?8 _4 G( _方法二：
* |& X0 j# Y4 W2 F/ P2 v1 D如果数组是这样定义的，即：
int nums[] = {1,2,3};
+ F( H! a( t! X$ u$ A+ I& g4 O先算下数组长度：
nums_length = sizeof(nums)/sizeof(nums[0])
: f9 ~$ c& y- E然后判断数组为空：
7 g1 x# G  K& ~, j, S& |# O3 T$ pif nums_length == 0:
return false
! N5 S: D& Q9 ~2 x原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544
0 [8 Z/ l( u% [4 B4 [# p9 {
解决了上述问题以后，最原始的冒泡排序如下

#include <iostream>
, `) P6 S! }3 G#include <string>
* N* H( v0 D4 ?; @5 \7 u$ l+ Lusing namespace std;
% ^0 ?. b5 M3 N6 \7 p" Zvoid BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
- m) O7 s' W7 a4 W1 h! W        {
. h, ^' M' t3 L; ^8 @2 z) q9 s                for (j = 0; j < n - 1; j++)
$ l3 H7 n9 Z, m) k1 E/ w; [/ d                {
                        if (a[j] > a[j + 1])
" l2 A/ i' t9 K! r  ?# h                        {
2 I! E8 j: u( l  D                                temp = a[j];
                                a[j] = a[j + 1];
& M7 X4 e+ H9 f+ a" ~$ l                                a[j + 1] = temp;
3 x& H+ u: ?( p; o! O" w: o2 d                        }
                }
        }
( U  {! S4 y/ u* A( b        for (i = 0; i < n; i++)
6 G0 y- r& `% l8 v) Q                cout << a << " ";
0 U0 N- U. a  ?}
int main()
+ I6 L1 J9 S" `7 b# o{
1 b% v# ^( h: K$ t        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
* D9 I% x$ _% D7 A* O7 }. P0 W# r5 L        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
: P0 n, R/ h+ B8 z, H9 X- V}
# w+ c# v4 L2 }0 S' Y# b# I& E
上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
5 y: @' C9 z3 I( e1 E那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下
# @" x2 K, K. Y0 ^6 W& H
) l5 C$ u% ~8 I. Q#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
3 G; q' b: d: \  {2 o7 ^        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
- u1 Q. j+ c* N0 P  |2 P. K+ S        {
                int flag=1;
                for (j = 0; j < n - 1; j++)
: }3 a- Z! n9 ^  |: N% q                {
                        if (a[j] > a[j + 1])
/ f" S4 ?7 D, v5 C: z5 t                        {
                                temp = a[j];
: v# N$ S4 Q3 Y3 N* W" \8 ?                                a[j] = a[j + 1];
  w% U2 K3 f. g1 z) q$ a3 r                                a[j + 1] = temp;
/ R% ^1 H$ a  Q) w1 o                                flag=0;
. v1 t. L; I# f8 U2 }                        }
                }
* k5 l) S! X% q& q; F7 H  E# g                if(flag)
) `/ ~: a& ]3 R9 Q: W                        break;
! C, ^5 X4 A, k. ^  n% C        }
5 m/ }' M$ S6 a; Z% Q+ \        for (i = 0; i < n; i++)
                cout << a << " ";
}
5 x, a. e0 ]. d4 C2 D7 j2 C: [int main()
  `3 N; \* O: o' O: e; a8 L4 y* d) ]{
        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
  U8 X: f' v+ y7 M- z        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
}
) e" u: \, _; q3 h8 V1 K
6 d5 Z9 }' J  ]( B: i  _3 E那么再以一个新的数列来判断上述冒泡算法 的优越性
3 4 2 1 5 6 7 8
这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下
- M$ ~) g/ Q- N& }! X
( ~/ l( i) W6 b. E#include <iostream>
#include <string>
* c6 X* s% h$ c5 {using namespace std;
. J- {4 K5 f: m9 Bvoid BubbleSort(int a[], int n)
{
2 n- b" I: v0 E        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
) i' {, V1 ^8 q* b        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
' D$ K/ L' y/ Y) A; F3 @; T8 a                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
& t) u0 P0 v4 q' L9 ~* k                {
                        if (a[j] > a[j + 1])
2 i( {( v! S1 ]: M4 F                        {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
9 l* [& m, r0 i6 l/ A                                flag=0;
: {" `3 V6 e9 d; C% R# V                last_exchange=j;
                        }
                }
( s( A+ m: R! u; i7 U# `                Bubble_Sort_border=last_exchange;
                if(flag)
$ N' |$ l" W+ c: R( d                        break;
        }
        for (i = 0; i < n; i++)
: R# [/ ]4 U, i9 U                cout << a << " ";
+ p6 Q7 |+ D. m! ?# [2 x  G+ N}
2 ~9 r& l& e* Y' h/ y( |int main()
{
        int a[8] = { 3,4,2,1,5,6,7,8 };
7 i) {& d- [/ Y$ Z3 g        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
% o& e8 F5 k; p  T$ r1 I- l2 P6 o        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
! N2 U: O9 i( D! V9 K- h; ?                BubbleSort(a,count);
7 e# l; q, a& y$ _) C# x        return 0;
8 \$ h7 s; E* r  K* F5 P8 ^5 ]- B}
3 O3 X4 P2 L( Z7 E, z

5 l7 [* z: g! m: q到这冒泡算法就结束了吗，不可能，你在看看这一串
) o2 @5 P& u* [: M. x9 Q# {2 3 4 5 6 7 8 1
上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
8 d  i4 [; J0 C6 m8 Z基于冒泡算法，延伸出一种算法叫做

. b: t/ W9 n! b鸡尾酒排序
鸡尾酒的排序过程是双向的具体怎么实现了
首先正向还是向冒泡算法一样的排序，
第一轮，1和8交换，
. b' t! B, c5 P6 d) w& H第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下


#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
' G4 e# U8 s5 `/ X3 W7 C        for (i = 0; i < n/2; i++)//奇数轮
+ i, q& a% J; J        {
                int flag=1;
) f, C& n& c! @" P                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
. V9 A2 N% `* b) I% \: L                {
                        if (a[j] > a[j + 1])
                        {
                                temp = a[j];
  H( L7 r& A0 Y: P2 U                                a[j] = a[j + 1];
                                a[j + 1] = temp;
. z7 ]5 e* [7 A# `8 {; ?                                flag=0;               
                        }
- t: ~& }8 t1 `' \; H                }
$ P  _; q4 ?+ {# R, I# Y: R- d                if(flag)
                        break;
  // 偶数轮开始之前  flag 重新置为1
& L9 I& n( f7 p9 m! y                 flag=1;
$ w3 p5 ~7 a) V* g4 T6 D3 _  |                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
4 ]& Y+ D* L: p4 D' S                {
) [% m; ~, l" ?1 @7 T& c2 e                        if (a[j] < a[j -1])
6 w9 |% O, U- h* f5 l" g9 e                        {
+ h0 a  O. L/ L4 q$ N                                temp = a[j];
' a7 i% o2 [; w( N7 l1 T                                a[j] = a[j - 1];
6 G6 ~8 [, Y8 a+ m8 C2 s0 g. U$ Y                                a[j +-1] = temp;
                                flag=0;               
                        }
                }
1 ^2 W- ^/ X1 {2 }" O4 @/ d4 h# F/ s                if(flag)
; {+ g, k5 i! k6 a9 g                        break;
        }
: g0 o) ^# o6 a" y        for (i = 0; i < n; i++)
                cout << a << " ";
}
int main()
{
0 @/ i& S& `+ g" {  K/ h        int a[8] = { 3,4,2,1,5,6,7,8 };
. ]- b) r5 b- Y/ Z8 J- g) `% C        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
        return 0;
& S* q2 Y4 z; ]  Y}

3 m2 l5 Z& O7 t. @- o  \$ `' e
以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
1 Q# ~7 t4 i9 ^3 |- D. |
9 I  f$ |. V) @8 \' P/ p0 Z- D————————————————
版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524

- f( [9 h4 O3 a) B4 o) @4 ?
, C. j; R6 H* E. {, f; l# F