关于冒泡算法的那些事儿

杨利霞

9 o2 z$ U+ ]. t1 O, [关于冒泡算法的那些事儿排序算法的复杂度



2 v/ g: e0 n0 l" V9 ~关于冒泡算法你了解多少：
首先我们规定数据如下
5 8 6 3 9 1 1 7
5 q6 `: @; h3 n7 P; s
3 e. T6 O' z( D/ v: ]( h- ~在对数组进行冒泡排序的前提下，首先求出数组是否为空
8 b* b+ {; m( P% \1 z方法一：
8 ?: @" m& Y8 E3 l+ s* f如果数组是用vector定义的,即：
vector nums;
! P* Q5 ^1 S4 ^//或
vector& nums;
+ F9 ~* u- A/ w  K( r( B  ?+ n% Y，则这样写：
; l( ]! Q' e) F) U2 iif nums.size() == 0:
return false
6 s7 W7 @! ]$ v  u7 f方法二：
; g0 S. C4 Q: g2 l! o. L6 ]如果数组是这样定义的，即：
int nums[] = {1,2,3};
先算下数组长度：
$ S/ e8 i/ l% w! o/ Snums_length = sizeof(nums)/sizeof(nums[0])
) s' I/ C2 v& s2 X" y8 E然后判断数组为空：
if nums_length == 0:
return false
原文链接：https://blog.csdn.net/qq_40977108/article/details/99290544

  `! O! R+ S2 O* Q. ~( t解决了上述问题以后，最原始的冒泡排序如下

' d: \6 |1 L8 l. r1 x4 a' i#include <iostream>
#include <string>
using namespace std;
$ ^$ u8 K6 d+ F2 c; Avoid BubbleSort(int a[], int n)
{
2 T3 y# b. e# l5 Q8 I" [- W% o3 o1 a        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
+ y  j+ r7 r% s( s  C3 ]$ g        for (i = 0; i < n; i++)
        {
5 U; K8 S2 A1 t9 O  H$ T  F7 S# t                for (j = 0; j < n - 1; j++)
                {
. O2 c1 f/ `4 I! r9 }+ z                        if (a[j] > a[j + 1])
                        {
6 Z' ?) ?0 }% _0 ?+ G; W                                temp = a[j];
                                a[j] = a[j + 1];
) T8 v$ I7 j# e, ]$ {1 e' l                                a[j + 1] = temp;
/ f7 A6 e5 V+ j, L; c+ W                        }
                }
        }
        for (i = 0; i < n; i++)
  z% t( |' Z- H- @                cout << a << " ";
}
int main()
{
4 ]9 ~( T: c0 t2 @" ^        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
% A# L  c" P* x! n: J' j                BubbleSort(a,count);
$ j: r7 R. B% d$ Y+ @4 K" [+ i& F        return 0;
}
  h5 Q$ G% E: a; {5 n
% b5 |/ H6 A" C上述的冒泡算法进一步思考，会有缺陷，例如在第五轮排序的时候他就已经是排好序的了，那么接下来的几轮会白白的进行比较，浪费时间
那么对上述代码进行改进一下，立一个flag。判断中途是否已经有序，如果已经有序的话就提前退出，那么改进的代码如下

+ y1 G& u6 N7 x#include <iostream>
#include <string>
using namespace std;
$ q, P, y% E5 Dvoid BubbleSort(int a[], int n)
6 J$ R9 |9 M! f. I) N- p{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n; i++)
        {
) f' v) y  r  v* @# H$ p                int flag=1;
                for (j = 0; j < n - 1; j++)
                {
9 m' `, j) n9 U                        if (a[j] > a[j + 1])
; F9 S' J# i- n' [4 ^6 W                        {
* l, z8 J4 [5 w  L" H$ n                                temp = a[j];
                                a[j] = a[j + 1];
' j7 u! Q/ C6 v% p2 w                                a[j + 1] = temp;
                                flag=0;
                        }
                }
+ L5 Z+ o/ o5 `, ?8 [4 Z                if(flag)
; [5 \& C  f+ P9 I  l                        break;
        }
7 S$ j1 ^9 F3 N2 S$ n        for (i = 0; i < n; i++)
+ y7 c- \3 n2 f2 J                cout << a << " ";
' {1 n# P- B( {6 |1 m5 C# s7 H}
int main()
$ ^" Y" N% C2 [9 O) a; l% |. ?) B{
        int a[8] = { 5,8,6,3,9,1,1,7 };
        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
  l- d# X0 g! f7 ?8 s& b* i        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
                BubbleSort(a,count);
) A8 z! O) q. |! v7 {        return 0;
( i4 a0 z! Z; |}
- c8 m8 N. `7 D
那么再以一个新的数列来判断上述冒泡算法 的优越性
. T+ j7 C6 O, z6 ?3 4 2 1 5 6 7 8
5 o1 W4 d; A9 s这个数列前半部分无序，后半部分有序，右半部分已然是有序的，可是每轮还要白白的比较那么多次，上述算法需要进一步改进
此时可以在每一轮的排序后，记录最后一次元素交换的位置，该位置就是无序数列的边界，再往后就是有序区的位置，因此改进后 的代码如下

" D2 j6 u  K+ a#include <iostream>
#include <string>
using namespace std;
# W9 }2 p2 u- x' k" |( ?0 pvoid BubbleSort(int a[], int n)
, k; j, X+ d9 \: \3 A, [{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        int last_exchange=0;
8 i  N* [  e( N- q        int Bubble_Sort_border=n-1;//无序数组比较的边界
        for (i = 0; i < n; i++)
        {
( p* H. u* n( V                int flag=1;
                for (j = 0; j<Bubble_Sort_border; j++)
                {
' v; V8 T5 s' K# H; E  t                        if (a[j] > a[j + 1])
* }' P+ x8 E7 e1 E8 E2 L! B# }                        {
- ]' I0 F  p) d( {( ~                                temp = a[j];
                                a[j] = a[j + 1];
; ]4 g7 y' N* O" g& m* F. z                                a[j + 1] = temp;
                                flag=0;
                last_exchange=j;
                        }
" Q* V! \' P- x$ ?                }
+ g4 F: K/ Y6 M* p) j' z% A8 ^% ^! @                Bubble_Sort_border=last_exchange;
                if(flag)
                        break;
$ c$ T$ ~! S# `7 i6 Y        }
. E& f& a' R4 f        for (i = 0; i < n; i++)
5 S1 u$ G/ I7 _/ u0 A4 n8 v/ z                cout << a << " ";
}
, P' y( W% k' Y1 a6 @5 rint main()
{
        int a[8] = { 3,4,2,1,5,6,7,8 };
' E) n5 v( V; ?        int b[4] = { 0,2,3,4 };
$ `% H6 q' ]# a        int count = 0, i = 0;
        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
; R/ O: Z" L0 p" R                BubbleSort(a,count);
        return 0;
}
! Z) H3 C% S0 k% J1 l% |5 |# y

& k8 m! }8 }8 z) U到这冒泡算法就结束了吗，不可能，你在看看这一串
2 3 4 5 6 7 8 1
- U" q* S- x2 L, F上述代码能否很好的解决问题，明明只调一个数字就可以完成排序，可是还要白白的比较七轮，那遇到这种问题改怎么解决呢
% B0 L$ c# a& v, H基于冒泡算法，延伸出一种算法叫做
: l3 m  C1 e, U/ S
鸡尾酒排序
6 J9 K6 t" ~. y9 A0 h鸡尾酒的排序过程是双向的具体怎么实现了
* n8 Y$ W5 n0 {. N% t& Z首先正向还是向冒泡算法一样的排序，
' b' N& r7 T3 z* M( \& I第一轮，1和8交换，
7 W6 t8 S! [  i/ u- K第二轮 反向比较，让1逐渐的向前，第二轮比较完成以后，实际上就有序了，然后进行第三轮的比较，第三轮比较完成以后已经有序，由于设置了flag所以我们此次比较只需三轮，是不是高效了很多呢，那么具体的代码实现如下

  W7 J2 c9 {" X2 E7 T
) W" J4 m& H/ q/ D! h% e#include <iostream>
#include <string>
using namespace std;
void BubbleSort(int a[], int n)
{
        int i, j, temp;//用来控制内外循环   temp作为临时变量交换
        for (i = 0; i < n/2; i++)//奇数轮
        {
                int flag=1;
                for (j = i; j<n-i-1; j++)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
                {
4 Y- i# I  I) C9 A( x/ Y9 y8 E( s+ }                        if (a[j] > a[j + 1])
                        {
% k, E1 U( B2 L5 n                                temp = a[j];
- S- u& e9 w% Q; @7 g1 A: T                                a[j] = a[j + 1];
$ Q1 l7 O; s$ i7 I" H                                a[j + 1] = temp;
                                flag=0;               
                        }
                }
                if(flag)
                        break;
: s- x$ z8 |5 s- }. p  // 偶数轮开始之前  flag 重新置为1
                 flag=1;
                for (j = n-i-1; j>i; j--)//这时候要注意此时  j的初值是i因为每次不管是奇数还是偶数轮，排序的最先位置一定是有序的
: B" a3 D& x: Z" I, Y" i# L                {
                        if (a[j] < a[j -1])
5 C/ J" x1 S1 `- j3 u1 ~# M3 j) `                        {
                                temp = a[j];
# M! i* P: ?; X/ n7 f                                a[j] = a[j - 1];
: o1 V" m  c; N' F                                a[j +-1] = temp;
                                flag=0;               
# a& ]7 \* O6 e3 t                        }
                }
                if(flag)
  ~+ p) M3 s1 E- y9 y8 B0 r7 e                        break;
0 P( ]! O; q- V9 O1 H& O( t7 a6 }        }
7 H' l% c0 N' ?. [        for (i = 0; i < n; i++)
# @+ c3 y0 O) M/ q* y                cout << a << " ";
' b9 v. ?/ `8 n, ^}
int main()
+ F1 c! g, h; q% B* y2 p9 T- @{
: T3 I% R4 R# R! y+ x3 g/ I+ D        int a[8] = { 3,4,2,1,5,6,7,8 };
" K8 L' X* G! {. G        int b[4] = { 0,2,3,4 };
        int count = 0, i = 0;
# C1 w8 m0 ~, \# n: Z9 G7 ]1 f8 V        count = sizeof(a) / sizeof(a[0]);//c++中没有直接提供求数组长度的函数，需要用这个方法获取数组长度
$ X% r/ X2 @" X. a5 z+ U                BubbleSort(a,count);
        return 0;
/ l3 H9 p6 W0 G/ U1 w7 T}
) M) L8 W  Q* v
8 D( I/ I' i+ s: ]. O
  p  ]2 Z4 p+ M! p. ~. S以上就是关于冒泡算法的全部优化方法。你get到没，下一次分享快速排序
* M- C2 k. L: z, x: y
( C& M, V8 v$ j! G9 G————————————————
" ~' o' j) U  p& C2 B( w版权声明：本文为CSDN博主「凌晨里的无聊人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/delete_bug/article/details/105928524
" v. D. Z$ i# i% V4 C. v% |