排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
了解冒泡排序是什么！
知道冒泡排序的思路
知道实例代码并且练习
/ |5 y  q8 S( f4 f# o有收获记得帮忙点个赞，有问题请指出。
一、冒泡排序基本介绍
1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。


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


3、冒泡排序的图解思路

9 D$ }) B" m( Z' O
$ Q$ `; Y& d! r9 A9 ^; N其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：
3 ~2 L7 Q4 L1 j9 V6 w# E

$ T2 d6 e7 T7 ~第一轮循环得到最大值
  D0 I9 ]" l: i6 P: N第二轮循环得到第二大值
第三轮循环得到第三大值
第四轮循环得到第四大值
4 G/ `( p6 `# [  H0 u- x6 d- c总的要进行数组大小减1的词循环
  p$ M! r/ v$ C
+ R* ^# K# o5 j; ?0 G
二、冒泡排序代码实现package cn.mldn;
, t- C/ Q) n2 f6 T; s! R
  O" ^) |( U3 y( L; Z$ F: }- E4 G
3 Q& c0 N5 J" Cimport java.util.Arrays;

; k! o5 H4 ~. C* l  M/ c; @5 l# w
public class BubbleSort {
, C0 }6 ?/ E& O6 y  V    public static void main(String[] args) {
2 O7 X2 W( d9 y% e% y9 M        int[] arr = {3,9,-1,10,-2};
        //大致过程
* x& M* r! ~) y: _- d% m5 x- E# G        //1、第一步就是第一轮排序得到最大值于最后
5 i+ f0 }  v) @+ `+ q        //  for (int i = 0; i < arr.length - ; i++) {
$ H  m  H6 T: V; u7 e7 W5 t        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
" _% I& O& I  {, q! Q2 t        //                arr[i + 1] = temp;
9 y3 L4 A& k, T( c        //            }
        //        }
' ?0 D4 H' [$ x' H: {. a5 s. M        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
* ^# D$ _2 X% h% [1 b        //                arr = arr[i + 1];
! y" c) i# N% ?$ P( _        //                arr[i + 1] = temp;
. }1 S6 M' e; j' C9 e! d% }        //            }
. O- F1 T  G% k8 Q5 [5 o3 A        //        }
% N* t  o. ~4 e  Y1 q8 C        //3、第三糖排序，以此内推
0 K4 w  Q5 u( D9 {        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
5 W( X& d9 w" f$ r' }6 o8 O* a% A        //            if (arr > arr[i+1]) {
) B; V, ^1 h/ U  F' G+ C! g        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
0 `7 f) g8 H& j6 k8 w7 o        //        }
; |) v3 Q- ~* }) d$ Y" L        //4、第四次排序，以此内推
) _/ `+ s: ~; `        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
$ n$ l9 {0 U! J" E        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
! r" M1 M1 e1 i# z+ j$ h* j; h/ O1 N        //            }
        //        }
        int temp = 0;//零时变量，用来将最大的数值排在最后
( x; h/ w  s9 P$ u7 ~- O        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
8 o+ X* |; H, J# z            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
" M2 Z& U4 c7 l, s% H# W                arr[i + 1] = temp;
            }
        }

9 z' s- l4 e/ V5 Z8 k1 g
6 `( o5 }" K9 W        for (int i = 0; i < arr.length - 1 - 1; i++) {
. z* a. ]$ a0 L: q7 P) K/ z4 T            //如果前面的数比后面的数大，则交换
6 Y) p1 y1 c+ @2 N8 p, x+ E0 X            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
/ f' A1 k4 r( P: D7 z# \            }
2 G, Q0 D5 K  }3 m+ y        }
7 D+ R8 T8 Y. d
# s1 k* P& A5 \5 H4 X( u0 z% X5 O
* ?6 `! F3 x' ^6 n, A" R        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
, H6 i; E6 ~' F, Z            if (arr > arr[i+1]) {
                temp = arr;
0 X# q4 i3 Z* {: z* g& x6 B" V                arr = arr[i + 1];
                arr[i + 1] = temp;
5 X# i# `4 G/ A1 {            }
        }

5 \# k& t+ N1 d* R; U
( l+ [/ K9 A# v, T! g' _3 e        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
1 o1 n- D9 j' z4 P            //如果前面的数比后面的数大，则交换
; B8 s, {% y1 _& [' M4 M; u$ F            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
0 o. m8 M4 G. M; e                arr[i + 1] = temp;
            }
        }
( Q! ]6 f# f' z( k) ^! E' H
- w9 c  p2 W# N7 _7 v7 L
        System.out.println("hello " + Arrays.toString(arr));
/ B% g/ m. j. n# h" q/ z0 G        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决




+ r& p. c1 }$ s" A7 r6 F. s0 b        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
' d+ q5 J$ [7 ]                //如果前面的数比后面的数大，则交换
2 B' V4 B& G1 h9 G' d$ s                if (arr > arr[i+1]) {
( F' ^8 G/ g1 ~( a5 o                    temp = arr;
) T( x+ y5 n; h1 |$ P0 `                    arr = arr[i + 1];
8 F1 u4 j) O( d                    arr[i + 1] = temp;
( ]+ ~( `( b9 N' E1 P                }
( y- Y+ l* Q0 {0 X9 J            }
8 J& j6 H4 j2 t  t7 o        }
: p2 T$ r9 S5 V+ I( e- ~    }
}
' k: M( a) b* ?) ]( S8 p$ r三、冒泡排序的优化

1、思路
如果我们发现在某一糖过程中，没有进行一次交换，提前终止
# q) Q7 m# R4 O. c0 H, W2、代码实现

package cn.mldn;


import java.util.Arrays;


public class BubbleSort {
    public static void main(String[] args) {
( X# ~" o5 o1 P' e" E9 k        int[] arr = {3,9,-1,10,-2};
        //大致过程
- t0 S/ P# _- P  b" W" q9 k        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
6 A* J* R. [( S: Z" o, \        //            //如果前面的数比后面的数大，则交换
" l/ a$ }, a: F+ [/ A        //            if (arr > arr[i+1]) {
& `9 p* _3 J$ o* D2 L% ^3 P) F        //                temp = arr;
3 |; q( O7 Z7 n- h5 G5 U        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
  n- G4 N+ E: R        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
- t5 z) \$ ^9 i/ R% G        //            //如果前面的数比后面的数大，则交换
" P- d5 i; d5 C& L  ?' V        //            if (arr > arr[i+1]) {
        //                temp = arr;
' _6 B6 T' X8 k: ~% x/ _. q        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
: ]. ?0 w- E2 Z        //            }
) J& A& Q* G- t2 ]        //        }
        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
9 z- E* `" E' ^) e- K: @        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
3 [; N; h# C! K6 F        //                arr[i + 1] = temp;
        //            }
        //        }
        //4、第四次排序，以此内推
: Q4 }- T7 q2 G$ G% c( J8 w        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
- z. [9 O# ?  I/ y5 f        //            if (arr > arr[i+1]) {
3 f3 g' a; B6 D* W0 R2 m        //                temp = arr;
5 z$ t. @3 J) }; `        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
        /*int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
& _, n9 M. w' u( }0 V6 C            //如果前面的数比后面的数大，则交换
3 z+ j$ }2 r2 k2 b1 t$ P) w            if (arr > arr[i+1]) {
- V7 Y" j' x6 E: x! @% t4 C                temp = arr;
  U7 H* i" j. v% M/ c! M                arr = arr[i + 1];
& x+ e% U" Z: v8 U                arr[i + 1] = temp;
            }
" H) ^% n/ x& Y: W        }


        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
, k8 d. w. @. {- L) M/ Y3 t            if (arr > arr[i+1]) {
: x0 y  \6 ^; o9 _  u8 Q$ m: U                temp = arr;
                arr = arr[i + 1];
1 q8 B' G- N& {" r2 c: `                arr[i + 1] = temp;
" p  I- h8 G% m7 T0 q' Z5 t            }
        }


        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
- o! p, W% V1 q( H3 I% ]& `4 G            if (arr > arr[i+1]) {
                temp = arr;
0 t# d: u! V; R; k0 e                arr = arr[i + 1];
                arr[i + 1] = temp;
/ s2 y- U" ]1 w# [            }
        }
* W$ k$ s+ `$ w! X2 u7 u: D+ a
' |1 m$ Q" _- h  }- o  n$ l
" _; {4 e. f" z: K, x1 A& u        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
' @0 m# I& h9 t0 `1 L2 \& M            //如果前面的数比后面的数大，则交换
# T1 o: c$ w" \            if (arr > arr[i+1]) {
4 Q. c( S: p" s1 c9 P- ~                temp = arr;
, u/ ?# ^. r# Y& r  N# g$ i3 z4 R* W" N                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
3 R3 G) R) c5 V" d1 Y        }*/
& ~" C; f8 v% e; C4 A9 n
. Y2 p$ a3 G5 A; ~' c* l8 c
; S. ?$ C# D. C. [2 r& H, k        System.out.println("hello " + Arrays.toString(arr));
6 Y6 ^. t) a3 f- d0 ]        //------------------------------------------------------------------------------------
1 d/ t/ h. U0 ?        //根据上面的观察可以知道了撒，可以再用一套循环解决

0 w4 J8 H6 N5 U9 V* p- ^
4 ^1 H% z9 Z. A. ?) c

1 M2 ?. x. r+ ]4 A; S

; y9 j, |/ `0 b2 ~0 @# ]        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
0 ~  x1 o9 H- L# g) \. \+ q: c        int temp = 0;
7 i3 Q! t1 w% T1 e- k- r/ O

        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
4 E9 S+ R1 J8 W' ^            for (int i = 0; i < arr.length - 1 - j; i++) {
& s  n$ I0 h: A1 j2 }0 \7 b3 V0 d                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
& x) b, Z7 n2 p: }2 i% T5 I                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
: k. c; Y+ v5 l; P. U* O- _& I            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
+ B# N; q$ z9 g% b: r2 i                break;
7 ?# G5 D! z2 b1 a5 J- P; p            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
. X2 y5 {* ~& O. X# q/ F4 @            }
9 R; X+ ^: m* |3 x( E6 v        }


        System.out.println("world " + Arrays.toString(arr));
    }
}
8 X, H: i9 {: p* f: G四、将上面的代码封装为一个方法
; N! m+ P: u- Q6 F! m/ D/ `+ Zpublic class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};

4 I- a! y) c7 W' f& v
        bubbleSort(arr);
        System.out.println("world " + Arrays.toString(arr));
. B4 c# _; o8 [8 D5 H8 ~    }
. K8 g0 z; J- S% @

. I& M- D& B9 X+ J4 b3 ^    public static void bubbleSort(int[] arr) {
* [0 X, w$ Y$ C, c+ w8 h" a) {        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
" H$ N4 z- u) R        int temp = 0;


% n, N; F) Q+ R$ [" _9 s        boolean flag = false;
2 `7 R7 p7 y# ~3 w; l7 O        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
! L6 r% \! G! {3 Z1 Z8 v                //如果前面的数比后面的数大，则交换
" Z- R9 x3 p4 R3 K+ k6 J! h                if (arr > arr[i+1]) {
1 W4 K! U7 F' y- N; ^" X& v3 I7 l: z3 N                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
& ]" T" Q4 V. {1 r7 m: X                }
2 d& K& @# \. q' D( P+ s5 a* r  Y/ p            }
6 o% J+ n/ j4 ~9 h            //在内部循环的时候进行查询
9 y! n) W* S- C" W            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
" W5 ^( L( G6 X. {                break;
            } else {
& t' Q* [! j/ g( i/ _( ?$ ?                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
& P! v0 t8 {+ H: p' \            }
        }
5 ~" P8 x6 q6 C    }
}
% l$ ]  P% d7 y  j五、测试一下冒泡排序的时间复杂度

1、代码是实现

import java.text.SimpleDateFormat;
+ b+ t6 F, b" j9 Himport java.util.Arrays;
9 s) g. V, Q5 x1 u, Bimport java.util.Date;
5 h4 ~6 k! q1 X8 D, e
' Q& J7 G7 k, ?- p  @
/ i! I" T$ L0 {  f: Q$ cpublic class BubbleSort {
    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的数
3 g1 Z$ V: S0 X6 }% @# T8 v        }
) n: v  Z* G1 w1 i        //2、输出时间
: J. m. J* U. m4 }$ ~% K        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
2 T3 \/ ]3 w! O        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间" + date1Str);
  y# s2 ?! m3 T0 j! B) p0 t        bubbleSort(arr);
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间" + date2Str);


) j( J* Y+ n: f
* t4 l( ?" V: g: z9 Y! l
    }
! S4 G4 x4 [! b8 F7 P' _

    public static void bubbleSort(int[] arr) {
. H: `* |6 ^0 J: c2 r        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;

. k6 ^, D6 J) l
        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
6 u0 Z% [5 j& F! }' k0 J, R- t            for (int i = 0; i < arr.length - 1 - j; i++) {
/ k/ V1 s2 G3 `! h4 r) n) O* m                //如果前面的数比后面的数大，则交换
" `2 ^( G' a5 h5 b4 Y                if (arr > arr[i+1]) {
5 L9 [2 c+ T( b- j+ y! \7 }, N2 s                    flag = true;//在这里把flag值为true
; E7 Q. H; Q5 z; R4 t  |                    temp = arr;
' v4 n4 ?: ?5 X! H2 G( s% }                    arr = arr[i + 1];
                    arr[i + 1] = temp;
$ n' S" D, q7 v8 C1 d$ J                }
            }
0 Y7 y3 c$ V4 J( [7 x            //在内部循环的时候进行查询
/ a# I& f) g/ p+ L+ \            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
4 E1 D$ \* K3 p: b6 R9 X8 |                break;
+ P. R' w0 [1 F' w/ U            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
' B3 v  M: [) N# y; u. ]) \+ a            }
        }
    }
# A2 A( ~3 `6 I3 p9 g* p: K}
! n* q1 Y1 }% O2 N/ G0 I
! d4 E! K3 X. ^8 Z0 X  u7 w

2、效果

; s( e" J1 @; G9 W' t

7 C+ X' R. X' [/ _8 R0 W' V

5 f1 O" ~" }5 |% G& K* Z

470557092

顶。。。。。。
$ D* w7 S0 B/ Q; f! }