排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
, D* N$ j$ q2 i& `* `% P了解冒泡排序是什么！
$ `0 \* Q' Z1 V2 [知道冒泡排序的思路
知道实例代码并且练习
有收获记得帮忙点个赞，有问题请指出。
% a- E. x3 S7 E0 @$ U& ?+ z一、冒泡排序基本介绍
1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。


  A& ^4 N0 z) B  d: M" n9 K2、冒泡排序的优化思路
因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。

" j4 Q: z3 A) d2 K% d+ [3 X
3、冒泡排序的图解思路

# y( Y* f/ u. t, W& ^8 m
( o& S5 `2 e/ R/ R9 \其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：
& u- T. p% L* ]: k  u
8 i$ E3 u" x* Y6 ~8 s
- P# W0 z$ |5 d: ]- A% J第一轮循环得到最大值
& o- |9 F- c' o& v9 Z2 J& U/ b第二轮循环得到第二大值
第三轮循环得到第三大值
; e9 U+ R2 L! ~9 k0 z第四轮循环得到第四大值
总的要进行数组大小减1的词循环
/ b5 M4 y/ T; `% ?! \, }
# j, [5 G% d4 D/ s  k- b
! T9 C; Q! u6 e- ]5 n& K二、冒泡排序代码实现package cn.mldn;
2 T6 l4 c7 j7 B2 x
# t8 w/ f# t0 Z  H$ h
2 r$ y( Z  r0 j2 V8 H2 C. X8 x& f5 h  nimport java.util.Arrays;
( }; H0 H+ ]! l& X, M' x7 H

& n) z* t/ C& v4 k6 Y/ mpublic class BubbleSort {
    public static void main(String[] args) {
% O- v3 r2 o" P# H! g2 k        int[] arr = {3,9,-1,10,-2};
        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
7 S5 x/ C$ G, m- e        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
7 x/ s0 {& Z) ~7 T0 i, Y        //            if (arr > arr[i+1]) {
/ o7 s' j  z- A: ?        //                temp = arr;
8 K5 ]# ]( J+ ^% T$ y( O& s( f        //                arr = arr[i + 1];
0 p8 h# E( a2 X        //                arr[i + 1] = temp;
        //            }
        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
8 z/ k1 r1 N. E- ?6 j0 f3 b        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
" n( v: [/ Z4 O7 b( d        //            }
7 v! v; d1 {- G& p7 [. d1 j* [        //        }
/ k" A' }3 ]" Y0 t* ]# t        //3、第三糖排序，以此内推
* \4 X& C" U& ?1 _( X! Y        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
5 ~/ x+ f( a( x: u$ t        //            if (arr > arr[i+1]) {
2 s% s2 I+ l% S( N; a+ \/ `  P        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
2 x0 H1 q: J; }; ]; J0 x6 E        //            }
        //        }
        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
: o1 |+ D" m* |+ S        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
- \/ e, p; w1 Q- d# k, ?        //        }
. u5 S+ ~; H9 |* R  B2 a  E8 s        int temp = 0;//零时变量，用来将最大的数值排在最后
* L& z' z0 c, w) X8 g& u& T+ _$ Z        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
& C. X0 [& e. F. p                arr = arr[i + 1];
                arr[i + 1] = temp;
8 w4 o! e( B: s& u& I+ W            }
        }
2 i; t9 h8 K; d) X  M
5 U% u- F1 N7 \' t( z; V& x
        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
  p1 q! Y' t: Y% B7 G                temp = arr;
8 X6 V) l& Z3 E) M6 H                arr = arr[i + 1];
                arr[i + 1] = temp;
1 y; K; N8 W/ i9 B* k, D            }
        }


- }7 |% D, D6 _7 n4 E8 ^& d# V        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
- i" X! W5 E2 D4 A9 k            if (arr > arr[i+1]) {
. u, f; H' N5 R7 T* z                temp = arr;
                arr = arr[i + 1];
! g/ }  v& M8 C$ F# B2 N                arr[i + 1] = temp;
4 ^5 `  |$ s; o2 y- v7 L, h2 M. Z            }
) H! V. ~0 {3 U( O9 b        }
; R. F2 I& x- \/ B( M- x/ j
, U' M3 `1 B# r& F8 P/ s
        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
& c9 g. N. E9 c, D            //如果前面的数比后面的数大，则交换
8 A' f8 y+ r4 n4 B' |% T. ~# ^            if (arr > arr[i+1]) {
0 I# ~  o8 {2 C2 `5 h. D% ^6 s                temp = arr;
                arr = arr[i + 1];
6 R% e% Q2 h* o3 o& _' R                arr[i + 1] = temp;
            }
        }


        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
* Q- ^! C% e1 K1 p/ B# g0 f; ^
* ]2 ~! K' E' A2 z2 \6 X


% o' t) R! o8 T; k: w2 Z$ }        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
; \( Y+ V0 m' W  W( \: {                if (arr > arr[i+1]) {
                    temp = arr;
3 o, {; c5 h$ @- l                    arr = arr[i + 1];
                    arr[i + 1] = temp;
' D/ o' y" u5 K/ |                }
- h' v# l8 x% N6 U  G% \            }
        }
. ^7 L  p7 O8 j! Y    }
}
三、冒泡排序的优化

1、思路
如果我们发现在某一糖过程中，没有进行一次交换，提前终止
2、代码实现

package cn.mldn;


3 W9 S0 y0 b. n" G; dimport java.util.Arrays;


public class BubbleSort {
    public static void main(String[] args) {
) q8 T' {0 |9 A$ A% ?3 D        int[] arr = {3,9,-1,10,-2};
        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
* @+ k! [: V4 K$ \% A9 {        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
, A, C6 a4 }4 e1 I7 W" {4 O        //                temp = arr;
" D; w3 M' |7 G0 U- R/ L8 g* U        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
2 [; [7 @4 ]% P. {; v  C        //            }
' J0 O' m9 V9 h7 ]. O, |4 u% m        //        }
5 p, h& J0 {; I1 u6 ~% f        //2、第二糖就是把倒数第二大的排到倒数第二位
5 B! @8 f: T6 O1 |) {/ M& x        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
5 e$ E$ [" x, O3 R        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
5 _* i! D. t/ C' t        //                arr[i + 1] = temp;
        //            }
; g/ s* b8 _1 P3 B( y0 t( E. y        //        }
' ~) z, q: ~1 T. q# R        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
7 S2 ^" W+ C  F        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
3 o1 f" a7 q* B( W8 F5 v        //                arr[i + 1] = temp;
6 h! l" R: c1 X& k9 p        //            }
$ f! k7 K0 I! N; E9 l        //        }
        //4、第四次排序，以此内推
, K9 a7 ~% H% y1 I: c" O8 I        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
! d0 q- v8 H# o' O. @: W2 d        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
4 L1 k& y* C/ ?% m; K/ P        //                arr = arr[i + 1];
) }# A7 q$ A3 _8 j$ Q8 Y- x        //                arr[i + 1] = temp;
        //            }
  y5 w9 n- e- _+ c& n4 \        //        }
' d2 @& [. `5 \7 _/ r6 V5 R0 y        /*int temp = 0;//零时变量，用来将最大的数值排在最后
) g, f& Q' s! p7 N. d8 s% ?        for (int i = 0; i < arr.length - 1; i++) {
9 U3 B( D& b* q( o  l$ t$ f            //如果前面的数比后面的数大，则交换
7 k6 Q3 S# ~; s/ H) ]4 `            if (arr > arr[i+1]) {
( l4 l# U- n2 ~& |% R8 R                temp = arr;
                arr = arr[i + 1];
1 d. L0 n1 V/ `5 Z8 ]$ ^3 k: u                arr[i + 1] = temp;
" v( `& d8 p8 d5 W; q1 n% K+ n            }
        }

/ |& [( R, `$ ~' J+ D. \+ N% N
        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
4 J0 y, e+ G0 w# G                temp = arr;
( \$ G0 }& [( Y' U/ o. T                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
  [0 z+ J& G! ^+ l6 x6 B" U: h        }


, c/ s* n2 w: s; X5 R/ U3 ^. j        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
7 K8 y9 _+ v- i, h4 I            //如果前面的数比后面的数大，则交换
3 v+ w; ?  U  C4 P, {( q            if (arr > arr[i+1]) {
- P- s1 E- z4 Z) }                temp = arr;
* l8 Z; ?9 A+ [# _9 u* M$ X4 D                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
; P* N5 Z2 l/ j8 O5 [1 g7 [        }

4 S6 S% S7 f4 e" \5 y" W; J
: V5 j- c# i2 _0 ~( e7 J& n; m' k        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
3 v  _- c# {8 n, B- B0 |            if (arr > arr[i+1]) {
                temp = arr;
! d* F- t5 b; N. Y! r                arr = arr[i + 1];
                arr[i + 1] = temp;
( _- F% X! c( |2 C. j% z            }
! m5 u1 X2 h. E2 j        }*/

+ L# ?$ h, N9 n6 S; i* Y9 y
# e8 f5 L6 S1 v5 C0 V9 N9 R        System.out.println("hello " + Arrays.toString(arr));
8 ^" t& R2 I5 j2 i9 }        //------------------------------------------------------------------------------------
  j6 o- I0 k( p( ?$ p1 L8 ]1 @% j        //根据上面的观察可以知道了撒，可以再用一套循环解决
7 h( F9 J! g3 H





        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
% f  |6 ]5 d" r        int temp = 0;
( f3 K8 f/ f( ?  ~

, [; A" m0 U$ x        boolean flag = false;
( n8 E- A$ {1 J2 s        for (int j = 0; j < arr.length - 1; j++) {
9 O) D' Z% b7 w% g( {; ^            for (int i = 0; i < arr.length - 1 - j; i++) {
! n  N* r' E1 w3 X% o' X0 R# A! r                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
% |2 F6 t2 j* A$ |* G$ p7 K' A( N                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
1 H, [# u; O+ D( q5 f4 a9 G                }
            }
2 C" W% ]& I8 V( F$ p  f            //在内部循环的时候进行查询
3 |0 ]# L* g0 r4 |( n. h            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
9 t( V# j9 e# p            } else {
3 D3 ^$ ?- J( d3 u                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
% G2 [& M9 a- S4 H9 z            }
        }
& o: S) m; ]' Q+ N# z! Y3 Z/ p, t
1 J* ]. H$ H5 h% e" e
9 t6 N- M% K: d# V  B        System.out.println("world " + Arrays.toString(arr));
3 \& ~& w2 g# I+ z% W; s    }
}
& D8 K! `  N) C2 b  t1 Q9 l$ H3 ~& a四、将上面的代码封装为一个方法
public class BubbleSort {
1 g$ D' g: ]' r' f    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
! k" ]4 {8 c- N) R

        bubbleSort(arr);
. \) f7 y1 h5 A        System.out.println("world " + Arrays.toString(arr));
5 R8 |) G$ w5 u. ]6 x& ^0 t; @9 x8 j; |    }
0 k. x7 _' M) Y; _
  g6 W4 @; h1 H. J6 h9 ^" n) e/ ]
; x1 a6 l% D3 }' c3 T+ h    public static void bubbleSort(int[] arr) {
" @, m1 Q. \5 L        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
/ ~$ R+ M* o) u        int temp = 0;


3 O- v9 j' r1 ^( H" i! _% K7 `        boolean flag = false;
. L! J: `/ u2 a3 W4 d( w( 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]) {
                    flag = true;//在这里把flag值为true
                    temp = arr;
9 u# m* c+ F! Q                    arr = arr[i + 1];
/ H" _4 c: q+ M0 ]8 d8 V% C) t0 V                    arr[i + 1] = temp;
0 T4 e# q$ r3 i+ V% u                }
            }
, f, g# I* E1 |0 B& V, q            //在内部循环的时候进行查询
* ^  [) @& l# ]/ l6 X+ W% ~' F            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
6 F. i: L; I8 ~" v7 N8 {. D" g                break;
, z/ @( b0 P9 K4 N2 R% {$ v            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
- z# P8 `' }. ~, t6 Y8 H- P  r+ ^            }
1 t( _, i. ]& x3 \/ ^2 T7 \        }
% {3 e8 K' s5 Z. G: z, G    }
}
五、测试一下冒泡排序的时间复杂度

1、代码是实现

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
# R4 K7 g! B# J8 Z
% l1 n. c. j7 g& f4 @
% \/ B6 s- x  v( S% `public class BubbleSort {
- B& n- m1 |* H; n8 G3 g    public static void main(String[] args) {
        //1、创建80000个数据来测试一下我们的性能
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr = (int)(Math.random()*80000);//生成0到80000的数
9 l7 q/ Y2 O, z        }
        //2、输出时间
        Date date1 = new Date();
3 s5 ?/ G% Y! y+ I% N5 b        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
        String date1Str = simpleDateFormat.format(date1);
; b; i2 O9 w# S2 z3 A+ Q        System.out.println("排序前的时间" + date1Str);
) `5 N1 n4 ?6 a. [        bubbleSort(arr);
+ H% t+ ]/ e5 ^2 Q        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间" + date2Str);

: a0 S# Y" ]3 l8 T4 ~7 h2 }
1 W$ O9 P  W3 g  L3 o) g5 `6 X
8 y( n4 \8 V9 E: b- H) V, I' v
& L8 x+ J) q  |% r  [7 Y9 E7 L    }

; V$ q: I/ ^1 l: [
+ ^4 c) d' R" U- G# W9 \. B! ?& J& G    public static void bubbleSort(int[] arr) {
4 `6 _- S  Q" ]7 x* X        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;


        boolean flag = false;
# }+ S0 a/ |+ |2 o        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
& g. [$ P8 Z9 q1 b                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
: r! S# |! ~- {( C6 @: x                }
4 t2 l2 |6 G. D( U# l7 {. l5 Q9 ~            }
            //在内部循环的时候进行查询
: d* W, a% v& E  |; @            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
# I. P3 ~5 @  {' K/ P            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
% o7 S6 F" h- w1 A2 u! ]8 n' Y0 J& N            }
        }
    }
- S1 V- a: j, I. I8 R$ L- R}
- T* |7 y5 M% k- Y# `. d+ M
1 P2 a: S: ~/ u& G' G# u

2、效果
6 s, v6 Z9 o/ D4 I% U

470557092

顶。。。。。。
/ K+ i2 s  G$ m, O
( L' I( X0 i9 J8 S) E7 Z1 {; C5 W