排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
2 P4 o( J" J# i; ^# K% B6 M了解冒泡排序是什么！
知道冒泡排序的思路
知道实例代码并且练习
# T+ n) K4 F1 J有收获记得帮忙点个赞，有问题请指出。
5 A7 \& R' _/ `* y' Z一、冒泡排序基本介绍
/ @: g) _! T2 K1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。


$ p& G8 h5 D1 l7 x6 w/ b" X2、冒泡排序的优化思路
' e2 K; z& J# h* e! s9 L) O因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。

$ p7 B3 H" Q: F! g* S7 x# a7 i
- e) j) F7 k; U8 w# C* C) Z1 L7 y3、冒泡排序的图解思路
, L$ P4 D2 }5 `) n6 ], T

9 I2 p2 H+ K$ M2 G, ]其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：
1 C: ?- @& m. D7 `0 O* z# B* x! {
5 N# o9 R- W" V* ?
第一轮循环得到最大值
! }9 g9 |; j4 t8 `第二轮循环得到第二大值
第三轮循环得到第三大值
2 i* Q; r* u+ E7 O+ [$ T: E( f第四轮循环得到第四大值
总的要进行数组大小减1的词循环
! K% m  ]7 ^; s' ]

0 R! j9 M( ?! }% _- n+ d二、冒泡排序代码实现package cn.mldn;

: L( N' ?9 |. x' e, W+ [
& k0 s% T. t3 f; c# l- X5 zimport java.util.Arrays;


public class BubbleSort {
, x! A0 F" L% K6 e' C    public static void main(String[] args) {
% ?/ I- l4 z. x( t6 r+ d4 p        int[] arr = {3,9,-1,10,-2};
        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
* [3 j2 Z; P3 K2 [3 u( Y        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
0 a2 w- y; e4 r* ?$ ]        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
  P6 Y: Y% [% }: y5 i) p        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
5 J6 f3 A5 I! u" w0 |        //                temp = arr;
        //                arr = arr[i + 1];
3 m" @; W8 Z& \* ]        //                arr[i + 1] = temp;
        //            }
& z/ M: Q- o% T7 C( m        //        }
# }& j9 a; B( h9 |        //3、第三糖排序，以此内推
  g8 b4 O: B0 S2 c7 `6 q        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
* C2 ]/ z' m$ l1 t; W! [/ c0 T! Y        //            //如果前面的数比后面的数大，则交换
- P+ R5 d% H* g7 o0 x        //            if (arr > arr[i+1]) {
+ F& C0 X! k) E8 g' r        //                temp = arr;
        //                arr = arr[i + 1];
8 m8 ~( w' D$ F7 B# H        //                arr[i + 1] = temp;
: r/ j# G2 l3 p; }/ f        //            }
        //        }
        //4、第四次排序，以此内推
8 B5 C# L5 G) ]3 W# W; m        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
0 _1 `# `4 A& }# ~        //                arr[i + 1] = temp;
        //            }
/ |5 M2 O& o- C6 n* d        //        }
( N. }$ Z8 v; s/ a9 A, B3 e        int temp = 0;//零时变量，用来将最大的数值排在最后
- L6 L2 o6 X. Y        for (int i = 0; i < arr.length - 1; i++) {
" z, ?  t" ~+ P/ o0 @            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
; I+ ~* x8 S/ z7 O0 P% S                arr = arr[i + 1];
* u# t* T# C) G4 t                arr[i + 1] = temp;
. A1 O4 a4 s9 ^$ v' C, Y            }
' ^) ]6 L7 Y; N        }
) }, z# |  u" E5 N+ u0 ~" f
  [% r4 D  ^4 r1 l2 |) Q
        for (int i = 0; i < arr.length - 1 - 1; i++) {
/ }2 @3 ^2 K1 I            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
$ G# m" ?2 F6 Q  ^; Q- S# ]/ W8 v                temp = arr;
+ y0 w/ z! h" n  {+ a, k                arr = arr[i + 1];
$ t6 Y' K5 B' B9 U/ s9 [# g                arr[i + 1] = temp;
. B; I: N8 Y  W1 a' h# s( E, e3 X            }
        }
! Z; @; G  \  w
# H+ d8 {) ]. o  s
        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
! M: @0 j& R2 n2 m3 x0 j2 @) S            //如果前面的数比后面的数大，则交换
" F4 n; [; I: }$ t1 G            if (arr > arr[i+1]) {
                temp = arr;
# m2 O) I% |6 N' d! _                arr = arr[i + 1];
' Q' u* O# k; Y( U& `: n5 K                arr[i + 1] = temp;
            }
        }
* O6 `/ {" E( s
/ T. G  C* x# \; x  k
        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
5 u" z2 a" o" c1 ?  k6 Z1 i" ^            if (arr > arr[i+1]) {
                temp = arr;
. Q, T) t" u5 s% \, K+ A                arr = arr[i + 1];
) J) e7 n+ @( I  G                arr[i + 1] = temp;
            }
        }

' c- B- x. i, W. ~/ ]" R! [
% [9 K5 e* D/ t2 I9 R        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
& e* w4 a  w: O& ~+ f7 x$ Z        //根据上面的观察可以知道了撒，可以再用一套循环解决




: x3 U, e9 E$ X& M) c% e- e        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
7 e4 s: O3 G( Q            for (int i = 0; i < arr.length - 1 - j; i++) {
  a- `2 r2 @( D9 Y                //如果前面的数比后面的数大，则交换
4 q4 ^9 l( {; A& N. ]                if (arr > arr[i+1]) {
: r. A9 q2 m: C$ F# @                    temp = arr;
                    arr = arr[i + 1];
* I9 l2 _8 o8 c$ m0 ]                    arr[i + 1] = temp;
: I9 h% p" m3 m# U6 m4 O  C$ Z                }
            }
        }
    }
0 p' z0 U/ s( Y6 n: t}
三、冒泡排序的优化

1、思路
7 ^! e( r- g: J( M; _, a如果我们发现在某一糖过程中，没有进行一次交换，提前终止
9 @& z+ K5 ^+ j0 y2、代码实现

package cn.mldn;
& r* q) C) ?* E$ I  x, j; c
6 u* q% r  @9 o# P( F. B
import java.util.Arrays;


public class BubbleSort {
6 f7 g5 W' i; o    public static void main(String[] args) {
- J0 H; U2 _  L; v# p2 n        int[] arr = {3,9,-1,10,-2};
        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
4 F) S- X# ^5 P! h6 n  ~        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
5 Z0 C/ m% |" C* P/ H        //                temp = arr;
; N6 S# `/ O" v7 f) Q) p        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
. b+ z3 `1 N! p2 |- T# ~        //            }
        //        }
) |9 S6 D; K0 J% _) g; w        //2、第二糖就是把倒数第二大的排到倒数第二位
0 l8 `5 n8 k$ f" H8 L& }        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
! {. i+ H5 l5 ]" O$ P* e        //            if (arr > arr[i+1]) {
6 x3 n  ?( K. K1 G: d, s+ E0 k. o        //                temp = arr;
' s, O" t# G' V% j6 z        //                arr = arr[i + 1];
0 k5 r( z1 `% {" \8 ~        //                arr[i + 1] = temp;
        //            }
        //        }
        //3、第三糖排序，以此内推
! w2 P3 D- N4 q$ e5 z$ F: p) y        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
7 x! m0 v( C$ c& W8 [$ t        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
! k# P3 i! c0 D; L# m5 C        //                arr[i + 1] = temp;
        //            }
        //        }
        //4、第四次排序，以此内推
- x1 k% s5 ^  u        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
/ u3 ^( O0 [- I0 x5 q0 P) p        //            //如果前面的数比后面的数大，则交换
2 _1 a+ [3 v4 s        //            if (arr > arr[i+1]) {
        //                temp = arr;
- ^8 c# F6 x6 X2 l% Y5 I3 a! ]& P! i5 p        //                arr = arr[i + 1];
/ t& S1 ?5 n1 q' _: K        //                arr[i + 1] = temp;
        //            }
6 d; i' `& h& T& q. J+ `        //        }
3 @* m, ^4 D: a& w" q) |        /*int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
4 h7 P2 {7 H: o9 m* }% i            if (arr > arr[i+1]) {
                temp = arr;
5 _8 t( k+ L3 x  Z+ u% U' F- f                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
5 k: v7 E2 i% D+ v# I- U4 m        }

! y2 j" }2 S: r' M' x! H- }( {
, V4 o7 c( o) q        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
  h" C5 \5 |* _7 ]/ D" ^; C4 t' S# u            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }

" h% r- ^' [( s2 l! q
        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
+ I5 a9 t) s' C            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }

+ X0 p- Y/ D0 W" B1 U2 q; l5 c8 |" y
5 e8 j8 G. t1 ?/ W" x/ s        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
. F1 H$ \+ y! E7 b3 x1 _                temp = arr;
7 }7 e, n$ w' {6 n# Z1 t                arr = arr[i + 1];
                arr[i + 1] = temp;
' ^1 l1 S. z8 U3 I, b/ C            }
        }*/
" N  _4 Y2 _3 H* e0 q: Y3 g

        System.out.println("hello " + Arrays.toString(arr));
/ |, L8 F/ t5 B) q" k- }! m        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
# r* |- b, L3 K5 p
- i$ \) B( v4 X

; z! G, l5 ^6 f  R- N0 z
, P0 B! A0 }0 n3 M2 N# C0 Z
: }# C, x( o7 ]- d1 y+ y
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;

# V0 J8 y! ^3 V, t
* t$ Z- R0 Y! Q$ b2 y        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
! {2 }; y8 a, [5 J9 T7 E) O            for (int i = 0; i < arr.length - 1 - j; i++) {
. q/ E9 M2 J! H* |6 T                //如果前面的数比后面的数大，则交换
+ _$ w$ Y- y2 W  r2 x- Z                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
0 |8 B/ P& }. |0 z                    temp = arr;
" _7 m  d% w: [$ P7 X# g0 a% T2 q                    arr = arr[i + 1];
( ?1 v9 W. A9 s+ k3 m3 D: Q6 ?7 t0 W                    arr[i + 1] = temp;
                }
            }
/ c' e- e! b& O. ]. |: H+ g            //在内部循环的时候进行查询
" T4 i( C$ M0 d$ r            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
/ P* A& Q$ e- B3 U# p                break;
7 {. T  }& I# K) M            } else {
" D, c- p8 l; f# E: ]                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
) v) E- D* t! P" F  g1 x" S" }            }
+ s3 T4 X1 @1 n3 e        }
% P1 c. b7 }/ _2 J  A4 u
7 \$ q3 ^" M  w7 e
8 p1 F/ Z* G' I# x+ O        System.out.println("world " + Arrays.toString(arr));
& \: c4 u! Q/ d0 g# h    }
}
四、将上面的代码封装为一个方法
public class BubbleSort {
    public static void main(String[] args) {
8 i, V! p; M$ o8 o# M+ J        int[] arr = {3,9,-1,10,-2};
6 E* q. N, f+ r& H! s) i! s" \

        bubbleSort(arr);
        System.out.println("world " + Arrays.toString(arr));
    }
7 o6 |4 q" o5 p5 V

2 Z; l8 c7 F" U( q3 c& @    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
/ D, W. d1 @8 P        int temp = 0;

1 q/ n7 q( z9 r" _/ T# y: e4 A# G. D
; Q, F% o* r8 \$ w9 j0 p: }' I        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
# K% ]& l' f2 W& f/ E8 f8 z" |4 W            for (int i = 0; i < arr.length - 1 - j; i++) {
- L+ `$ M+ T" t+ C) u% o6 i: Q, t4 h                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
. p# j6 Y" B3 r$ X7 b. j                    flag = true;//在这里把flag值为true
                    temp = arr;
( ?8 S* C" t& ]7 k6 a: A& Y                    arr = arr[i + 1];
0 M% p0 U1 D3 g0 r* x$ x                    arr[i + 1] = temp;
                }
            }
$ A. {" B$ S2 _0 F9 H            //在内部循环的时候进行查询
1 B9 O  h7 N& p            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
: {5 @6 ?; U* c* ]                break;
            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
  c5 \2 r9 j5 e8 B% ?3 G        }
, w' P1 q* X$ t6 D6 O    }
}
五、测试一下冒泡排序的时间复杂度

1、代码是实现

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

3 E- [2 f/ r8 a$ G+ V  w
public class BubbleSort {
" h- b2 t2 U9 k9 T2 Q1 B6 _    public static void main(String[] args) {
# E) c, N4 L  E5 b7 ?3 `        //1、创建80000个数据来测试一下我们的性能
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr = (int)(Math.random()*80000);//生成0到80000的数
        }
        //2、输出时间
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
8 d: ^! x6 N' V6 Y0 ~% Q3 ~; _/ G        String date1Str = simpleDateFormat.format(date1);
( N6 b+ A- J2 C6 E/ `# }        System.out.println("排序前的时间" + date1Str);
        bubbleSort(arr);
        Date date2 = new Date();
3 ~4 J4 _( o, x$ d        String date2Str = simpleDateFormat.format(date2);
# }7 l4 r* W/ Q6 p. |% V2 m( G% Y2 F        System.out.println("排序后的时间" + date2Str);



, ?% s; G4 G+ I& y3 s
+ c& D, ^4 f9 o0 o    }

/ y% _) F! C2 ~
    public static void bubbleSort(int[] arr) {
1 C1 X- E; s" d1 i6 O. a1 X8 k& `        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;
* v( N: C8 r( ^
. T+ D+ x6 z, j& b. M2 ?5 S
3 d0 i- l. O; d4 E        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
% L! Z+ K8 a+ n                //如果前面的数比后面的数大，则交换
3 i' ]5 P5 a: Y3 d7 s1 @7 ~  g                if (arr > arr[i+1]) {
8 h/ e" @5 k# o0 V/ {                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
# E* Z2 I2 J1 |8 @  \                    arr[i + 1] = temp;
4 a5 N+ d& T- n1 r0 W                }
9 U4 z( s% P4 G. e            }
            //在内部循环的时候进行查询
* W' J! i* O1 Z1 W$ V            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
( Q6 G" t" _) d) F% A    }
) K7 F* B8 N0 ^% {}

- |4 ^. {8 F9 ~
+ C6 H% n5 e7 b+ ~% \- S( k
2、效果
0 r# L  e( p& m- X


( l+ i/ l+ G. b$ c
$ L, g+ Q  p/ Q6 c$ u7 o6 W+ m) k

470557092

顶。。。。。。
6 z4 m* T9 M2 y( g% }. Z  a: [  K1 t
6 p2 E  q% I/ [: x& n