排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
+ u) T; L4 a. {. l4 A了解冒泡排序是什么！
知道冒泡排序的思路
9 t$ I% k! w, I7 l0 c# k7 ^知道实例代码并且练习
有收获记得帮忙点个赞，有问题请指出。
一、冒泡排序基本介绍
1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。
4 X% F8 r: \, d/ c% {. P7 a( P1 s
) e4 W0 |% k% u+ x% p" Q  E( t
: p8 Z0 W  m+ o( r, z0 T8 ~2、冒泡排序的优化思路
因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。


# R5 p' H/ h( h" }. p2 b; E' h. x3、冒泡排序的图解思路
: C1 ~' K3 R  k+ E* I

. c* X# f# L8 S其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：


& y0 G  ?7 T3 Z第一轮循环得到最大值
5 \# s' H* N# \& X/ d第二轮循环得到第二大值
( k( r9 I+ X5 s6 j3 N/ a9 o% l, R第三轮循环得到第三大值
+ E6 I+ u; I/ b+ v3 G: H# r6 C4 f第四轮循环得到第四大值
总的要进行数组大小减1的词循环
$ y: ^: j5 J, U! h; V
. Z2 x" a& `% m" k$ K
二、冒泡排序代码实现package cn.mldn;
+ _! X5 F7 v+ h4 a( m; ^& Y3 h' X: J

# f& t' q0 U8 m$ L8 {, t0 R! i3 b. Qimport java.util.Arrays;
; m* [. b% P% q

/ N. s% }( Y' i/ d2 H6 }public class BubbleSort {
2 {2 Y& Y! F: ~) {    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
1 q! |8 q8 \8 N9 W5 l/ `" W" `        //            //如果前面的数比后面的数大，则交换
9 s* R6 ^- m" |- z' X. r( }& k        //            if (arr > arr[i+1]) {
- {# O, s  R5 h/ u' Z  F. }        //                temp = arr;
        //                arr = arr[i + 1];
. ~0 x  P$ y# W# F. D! O        //                arr[i + 1] = temp;
6 B! N9 F7 [: }7 A& x        //            }
9 O' t5 O0 D, k4 ?& ?- O        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
" R8 C8 s% b3 A        //            if (arr > arr[i+1]) {
        //                temp = arr;
7 C2 b2 n" ~! f0 l& Q1 X        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
' ]+ `' k( X5 C& i        //            }
        //        }
        //3、第三糖排序，以此内推
, r8 A$ s+ u8 V& i; y) x        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
5 A' O8 q! m% s+ G% R% L0 T% r7 V        //            if (arr > arr[i+1]) {
        //                temp = arr;
6 I" l9 g4 E) `( \9 L        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
2 Q$ s: f# Z& N7 L1 n2 I7 v        //            }
1 Y) y$ V5 Y1 n3 ~        //        }
        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
& y; o( |* `0 F: D% Y$ K' M        //            //如果前面的数比后面的数大，则交换
; C* R0 s: ]7 a7 C0 V        //            if (arr > arr[i+1]) {
7 e! p0 v/ E7 Q& d" g        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
        int temp = 0;//零时变量，用来将最大的数值排在最后
" a" H( N% ~- [& s# H        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
6 V, F0 ]" ?( I6 p                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
- j6 m2 j' s0 G! m' M            }
        }
' |5 M/ y4 M* A

        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
! T, j* m4 j2 b0 N5 U' D! P7 q3 @6 d            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
% L8 @* d. d7 v  P            }
, K' b( d3 a3 a2 |; r. N        }

% I  j2 K) Q- `" V& K% g
( h  _, I! p4 X4 ~% |8 W7 J        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
$ P( z; ]7 a6 f1 H# e0 c            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
9 }* T$ u4 d6 i, ~                temp = arr;
4 b% ^+ |4 _# f- I  w/ e                arr = arr[i + 1];
  d  ]: r2 e2 J                arr[i + 1] = temp;
            }
$ o) v( Z& m9 k4 p/ I        }
. V' T  P" `7 y+ {2 o4 K
$ R: R& w- Q, H) y% D- ]8 G$ C' j
6 P* \, n" l; ~! w1 ]7 M        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
- I& {4 ^0 R- B/ P+ X                temp = arr;
* l+ H( L, I  j  y: k3 D' V; N6 S- J                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
$ ]- m' a, V2 W  v, G* z  h, _
; }3 i; |% I/ P" E4 k. l
6 d+ o$ m9 r4 N$ P2 h" V        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
0 J7 M4 ?2 E4 M. M* q        //根据上面的观察可以知道了撒，可以再用一套循环解决
( [/ d  V9 m1 \7 f6 T8 N
+ L' p: Y# r, D" I+ c7 Z; @& E/ s


& U" m5 t( c- v# |" F3 Y        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
7 X1 F7 i6 q! l$ y  R% m- |, @                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
/ A. b& r3 X8 W# [                }
            }
        }
8 C" k9 b4 e6 |2 @' B: X2 x    }
}
三、冒泡排序的优化

1、思路
如果我们发现在某一糖过程中，没有进行一次交换，提前终止
1 Z# B! M" E+ T& _" L! Z  k8 k2、代码实现

package cn.mldn;
8 g) r( F/ @! i' R0 \* T* |9 f

% M# z; X6 [3 r$ o! f* pimport java.util.Arrays;
4 c, A2 }' I- J

% m# T: o) H, B+ y1 k# Y$ Apublic class BubbleSort {
/ i1 k: p6 b8 A  o9 f4 ]    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
        //大致过程
6 n, M. E. R& g) P+ `7 X- w        //1、第一步就是第一轮排序得到最大值于最后
4 C% V3 G0 a4 w" ]        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
# K( ^7 C$ L6 Z0 ~        //                temp = arr;
- f, B5 Y. E: i% e& C* |6 d/ Y        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
' {7 V' c4 ]' S% p: b" f1 ]" d        //            }
        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
8 K+ H! s) \% b4 ?! e  w7 t- |        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
# i( v: k' b9 ]* d' Z2 q1 ^        //                arr = arr[i + 1];
3 A1 u/ T' f9 X' k' J! W        //                arr[i + 1] = temp;
        //            }
7 P+ M% `* U3 Z7 v% q: c        //        }
0 m3 ?. f0 ]8 A9 ^% F; }+ R        //3、第三糖排序，以此内推
6 A% x4 j' s! {1 f: U        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
8 F; G9 [$ C2 Y6 e+ \        //            if (arr > arr[i+1]) {
9 u% F+ o( N, M; I        //                temp = arr;
        //                arr = arr[i + 1];
' l- X& W, ~( C0 z* i2 S# u        //                arr[i + 1] = temp;
        //            }
$ f6 u6 p2 x+ G( w( B. W        //        }
0 G+ Z; r, n% b9 e$ d% {: }4 p        //4、第四次排序，以此内推
- V2 P& t2 Y, j# [" T        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
& c/ X( }0 ?8 P; `1 o' p# O  o- p        //            //如果前面的数比后面的数大，则交换
. E: B& p% ^7 r8 s6 h" o        //            if (arr > arr[i+1]) {
- l; Z3 C8 i  p' d) M9 P        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
; K6 T8 s( j2 B0 @        //            }
        //        }
3 G2 p( _5 \9 y) a/ C        /*int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
7 B, u2 Q9 H2 @( n# [, }            //如果前面的数比后面的数大，则交换
8 p$ ]; {2 |2 P1 V            if (arr > arr[i+1]) {
                temp = arr;
9 @0 M+ t# L% ^/ B9 Z8 Z                arr = arr[i + 1];
                arr[i + 1] = temp;
, [" w- g3 d0 e1 l- Y$ x( x: v            }
+ z( {- P" Q: `! r) ?, y  [2 x- G        }
. g: `# W9 u2 X* X  L
! V$ K- l* M( B: x
        for (int i = 0; i < arr.length - 1 - 1; i++) {
" D6 [! Z1 n" e( ~# O' z; l. Y+ Z3 B            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
& m3 t! Y& E6 t: ~                temp = arr;
                arr = arr[i + 1];
6 f) y8 o9 N7 O1 Z9 _                arr[i + 1] = temp;
- I# ~' V* j6 D& p. l7 P2 M            }
  a/ `+ z2 ^! `4 o* s        }


        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
" C" ]# H% c1 A0 A# N) {& w$ b            if (arr > arr[i+1]) {
; c( u6 B& E/ v* ]6 Z% O- O2 l* w                temp = arr;
                arr = arr[i + 1];
& C) d( w' c4 k& ]  C" @; p                arr[i + 1] = temp;
            }
) B" r/ O1 \% r8 o; c8 J, I        }
3 E2 P, p+ z, m3 y$ [! z9 l( U
/ q' j; t  ?' q
9 U- R2 Q$ R  r9 }5 P" Q5 L        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
9 q$ _5 T# A0 |3 n0 x) @* o% J3 P            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
: s& s9 e7 j6 H" {0 j8 R! y9 A% Q        }*/

" o/ [- v- @' ~: V$ {  s
  b! `- @4 t# R7 L4 s  ^, ?/ v/ I        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
# b7 o  v! G, C" N* i# d

/ \3 E+ e, L2 L! G
" C$ o) K2 O/ m6 L: N* {9 c


        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;
8 _2 y2 d. N7 o5 O
2 `1 A) v9 b( K9 b" }9 D7 c5 @; j
2 n9 `3 N  \! C0 M8 L1 P3 r6 Z        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
* c, \9 N: s, k& A, i: t- T+ W            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
- r; ?3 K; L7 n5 g  m                    flag = true;//在这里把flag值为true
8 t% d5 g* ?$ Z" X                    temp = arr;
  l4 T9 `$ `1 \                    arr = arr[i + 1];
                    arr[i + 1] = temp;
: ?( H- q* {4 j2 ?7 ^1 V/ N3 d                }
2 Y: E3 Y- [1 U+ {# d) W" K            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
# ^' {/ R3 Q+ y. M                break;
$ u# i) d+ F' P            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
! }' n+ M  r& Y' o1 f( {            }
        }
, K* B* V' b# e! y9 X  X

. V6 [+ P4 o1 V        System.out.println("world " + Arrays.toString(arr));
8 W+ Y  ^* l1 Q4 {    }
}
* v) |3 |4 d3 }0 e四、将上面的代码封装为一个方法
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
6 T: X, ^  d. H( |
# D% a" j/ K( P
; \# V% _2 [) J! A! ]6 O5 _        bubbleSort(arr);
% e7 O5 \# M2 P( m  ]& a2 l6 p        System.out.println("world " + Arrays.toString(arr));
    }

  h8 B4 S4 G- f, v! H4 i
    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;
2 d0 c/ W" K9 B, q2 W

' @) m: s' t" {+ _8 @" E% r        boolean flag = false;
2 Q4 Z* J0 I9 m* Z9 i# F9 l+ u- m0 ?        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
, F0 p) t# R  _7 k0 B                if (arr > arr[i+1]) {
! c: t0 U' u* [0 E                    flag = true;//在这里把flag值为true
# K. V7 [5 J- L2 F, y8 ]8 i: o                    temp = arr;
( P% {% D9 ?7 t1 {                    arr = arr[i + 1];
: P4 A: K$ I& e+ z) }                    arr[i + 1] = temp;
: K5 T" Y, P: p4 m6 x                }
! V1 m" @7 E& D0 X! p            }
) A7 a. ]! [6 Z4 @% F) r  }            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
            } else {
- w5 z2 V+ g; G& f* \4 w' I  ^! {+ o                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
' A. Z8 j7 \' D7 k" w% `8 M, h8 E& N        }
    }
6 }% [' v1 A) a+ Y' M9 L& v# |0 L}
五、测试一下冒泡排序的时间复杂度

1、代码是实现

import java.text.SimpleDateFormat;
import java.util.Arrays;
0 `; j& R$ n( a8 S$ l' r2 [  q9 Aimport java.util.Date;


2 i) q8 v# _( Z0 k7 n# _! E! m2 h- jpublic class BubbleSort {
    public static void main(String[] args) {
6 C; Q3 ^: L; K        //1、创建80000个数据来测试一下我们的性能
8 V2 F" s2 Y' I& m        int[] arr = new int[80000];
  r: m) u0 B. q7 w$ d        for (int i = 0; i < 80000; i++) {
            arr = (int)(Math.random()*80000);//生成0到80000的数
; @+ e  s1 f: w# H& n' T8 B) G        }
        //2、输出时间
- Y0 c: y" k9 \$ V0 k        Date date1 = new Date();
  d! L3 U9 q* }0 e( O$ v; w        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间" + date1Str);
4 j# o# W1 o) W. ?7 {1 v  F8 Z        bubbleSort(arr);
        Date date2 = new Date();
: G' S+ F0 u# Y' r        String date2Str = simpleDateFormat.format(date2);
7 b0 P, h: Z4 c8 ~        System.out.println("排序后的时间" + date2Str);
/ @$ |0 ^. r% k0 C



    }

. X0 b2 W" q/ t* k8 T# L: F  ]) d" c
    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
5 X# \0 Q8 ^$ y+ H; M        int temp = 0;

) c3 q0 H7 u5 Z" z# X
        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
) i1 i2 Z: |2 j! ?: ?/ {            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
' L* N* K- \; c7 `                if (arr > arr[i+1]) {
, C4 d3 x+ x8 x4 y4 h. b! D                    flag = true;//在这里把flag值为true
                    temp = arr;
6 C. o+ S9 Y% \# b9 k. W+ w2 l                    arr = arr[i + 1];
5 b& m0 Y9 c! u; o                    arr[i + 1] = temp;
$ e, P7 Z( L( A* k9 b( E. I                }
# \9 }4 [0 N7 |& f/ g7 L            }
            //在内部循环的时候进行查询
/ F1 ?; P5 Z3 B$ H0 l" B            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
: z% o7 G8 N; f% k6 R/ r: W            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
) H: U" b" d9 H- n            }
        }
    }
+ d: b$ d, d2 {; W6 o8 `}
3 p1 [& g! d+ b/ U( p" n( G6 Q; `

* X+ @5 G! ]& D
2、效果
) T$ _0 F) E2 j. _: {; `
/ g5 W( O* \- z6 o
/ L0 o$ w1 \2 [1 d

! e& q, s4 f. S# q% r( h; D
, B( M. \: S9 A. H6 j  t; @: X

470557092

顶。。。。。。

% w& n/ R5 h2 f' }: ~2 W2 J