排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
了解冒泡排序是什么！
知道冒泡排序的思路
; Z6 g) i& ?3 v; f4 `( e) J知道实例代码并且练习
) ]8 N. I1 v% v% p有收获记得帮忙点个赞，有问题请指出。
一、冒泡排序基本介绍
& F$ V. b* \5 w6 X' x- A1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。
4 m" o3 z+ h' c, B# D
$ b) T5 Q0 r5 ^# l: [
2、冒泡排序的优化思路
因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。


" ~* ^$ z! U) U$ B0 z9 j* @6 [3、冒泡排序的图解思路
( Y: W/ R3 \1 {8 I
7 b/ _% ]! c5 _1 ?; Y4 k
其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：
* V+ K) b) V8 i' m2 |, {( N
2 E' L7 k4 V2 A
/ C- K5 F2 ^$ K/ r6 Q第一轮循环得到最大值
第二轮循环得到第二大值
第三轮循环得到第三大值
第四轮循环得到第四大值
; G8 M+ f$ u' l) W总的要进行数组大小减1的词循环
0 g. R/ c: {$ m' R* a

; c& w, g" Z; i二、冒泡排序代码实现package cn.mldn;

; _1 l1 B0 `+ y& s: n( J. k9 Z
6 ^6 O+ y) v2 I2 j# l- nimport java.util.Arrays;


) @, z/ l5 M% \% v6 Upublic class BubbleSort {
    public static void main(String[] args) {
8 W/ |) s3 W* O8 O! X; t" l$ X        int[] arr = {3,9,-1,10,-2};
7 L- C0 N) C4 W) {1 [: c        //大致过程
( z, k) e$ P, I0 d! ]% r+ c        //1、第一步就是第一轮排序得到最大值于最后
5 c# Y. G1 X! K: Q9 w! J8 T        //  for (int i = 0; i < arr.length - ; i++) {
- x# k* X; o, c9 s        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
: i) m2 H5 f# m3 `- M; ^, w        //                temp = arr;
$ g* [5 R6 T" G2 q3 U+ ?1 v        //                arr = arr[i + 1];
3 X9 C' Q8 `  O2 |! r/ _        //                arr[i + 1] = temp;
2 C9 M: C: d. p+ a, k% H        //            }
% C/ {0 b: V7 B% w7 \6 \& |9 q3 X- A7 Y        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
- J; \- l6 M; q4 J) f        //                arr = arr[i + 1];
1 e& h; A# U/ O5 M$ z        //                arr[i + 1] = temp;
; a) ~/ J( V3 {  [, s4 ]        //            }
        //        }
5 t' k6 @# {* C( E: f) a# Y        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
5 w8 A: _, m: C' |( L        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
* W% w( v3 j" s$ a+ h        //                arr = arr[i + 1];
# }4 s' ~" I& a+ K        //                arr[i + 1] = temp;
! r6 u) M  z8 _+ X. ]) z; u" L: R& n3 J        //            }
) t9 e& r# g9 Q  t7 o        //        }
% y( E1 U# d" {        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
( W  W* i; m$ A        //            //如果前面的数比后面的数大，则交换
) x; r- R, }6 d1 y2 q        //            if (arr > arr[i+1]) {
. f8 C; o+ G/ m        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
3 s! ]5 Q; [" E& o8 W        //            }
/ i$ u- @# Z- V        //        }
        int temp = 0;//零时变量，用来将最大的数值排在最后
$ u$ {/ f& r: T6 h- q        for (int i = 0; i < arr.length - 1; i++) {
' e* e3 o2 ~8 l' l            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
0 U7 o& a4 o& T: }& B                arr = arr[i + 1];
                arr[i + 1] = temp;
5 [5 x, j$ O, ^; j4 p) B% L            }
        }

1 w* c' v4 J' U! W6 x
$ i7 @5 P9 A0 N6 W" j5 K3 Q* \" s/ g        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
/ e$ I5 G) a- w$ v  X            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
# R1 q& s: j* x                arr[i + 1] = temp;
            }
" U" Q% w( t( L7 \4 t4 A  n        }
/ b5 P& R2 C1 S5 D" X
7 l# x3 {' Q9 [) j# b1 t% y
+ r! O. b" W2 N" _! O6 j+ L( j        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
9 C/ o: @- W6 U+ k' B            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
# }0 z6 U; h0 [5 o                arr = arr[i + 1];
                arr[i + 1] = temp;
  D: b1 }8 ?% J( r6 B            }
: v, e4 o! E, B8 c( l! m        }
% z4 X+ ]) a. u3 J) ^

8 B, ~" i& W% a4 U/ v3 T9 P/ J        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
  U: y9 @9 X" Z            //如果前面的数比后面的数大，则交换
, q. k* P. W# X' e8 W7 e/ R            if (arr > arr[i+1]) {
                temp = arr;
; h, r5 C8 }7 e" i                arr = arr[i + 1];
/ h: p) D: Y  h3 j" O5 q8 X: J                arr[i + 1] = temp;
            }
        }


        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
0 J# q; G* g6 I( U
0 Y/ _* z$ P0 Y* H+ J
' l7 _* }: H- c! p- I

        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
0 o: e$ N% H; D, a2 a& w  n        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
$ w/ e. }6 r  w/ T7 i: J5 c5 {                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
                    temp = arr;
% ^" z( J0 ?, P/ r+ m. o6 ]                    arr = arr[i + 1];
                    arr[i + 1] = temp;
7 a" D# O% ]3 G1 d4 I- F/ P                }
. o) U' {0 p0 d8 c/ F* ^            }
        }
( m( P/ M6 o: g) u! |7 z- y2 K1 p- C    }
  E7 s2 P- r/ a( c# k% [/ j1 T}
" n* Y3 l& h- ^+ k& a三、冒泡排序的优化

1、思路
如果我们发现在某一糖过程中，没有进行一次交换，提前终止
( E9 z; x$ J3 b/ W! h2、代码实现

package cn.mldn;


import java.util.Arrays;


public class BubbleSort {
$ n) t( x" Y' T6 g- T) o5 S- N- m) K    public static void main(String[] args) {
/ t6 S: o% o; t, Q+ m0 m5 w6 R- `- Q        int[] arr = {3,9,-1,10,-2};
) E+ Q# [4 Y3 a; Q3 U        //大致过程
$ u  ?- y* Q) f7 J2 e8 n0 f        //1、第一步就是第一轮排序得到最大值于最后
( a* T/ Q9 d2 _6 a4 ?8 c        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
9 W, M$ J# \( |+ K        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
. c# F: A  N& s0 r7 ?        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
! V4 a$ u. N# d4 g) p        //            }
        //        }
        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
" [0 `! c+ z3 [% A9 r2 p8 _        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
( N& w0 D+ i6 _+ K0 J        //            }
        //        }
$ a0 }& R3 E6 Y3 E0 Y2 P9 e/ k        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
. P& t! f: \3 V% g; Y        //            //如果前面的数比后面的数大，则交换
$ H+ c2 w: i; ^0 a. b        //            if (arr > arr[i+1]) {
" t" ?6 f7 V# N% P% y$ ^        //                temp = arr;
) C# v- h& v1 h, @5 C        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
! S) M! U# }: x2 ]        //            }
1 e( C- H) `6 G/ S. q        //        }
        /*int temp = 0;//零时变量，用来将最大的数值排在最后
! d( }3 i1 ]5 K1 c$ w        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
; V3 N" r3 p/ [5 y& f9 x            if (arr > arr[i+1]) {
; R2 P4 N8 e- N( T3 h                temp = arr;
- b5 y) b' f5 U1 `                arr = arr[i + 1];
                arr[i + 1] = temp;
/ b1 j3 P: z' }: d: K! z            }
        }


; \, J, E5 u5 a) B1 m        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
+ l4 S+ q0 \1 `" k5 z' @* {1 f) e            if (arr > arr[i+1]) {
                temp = arr;
7 \+ w* l- Q5 c3 [3 n: b6 s, M                arr = arr[i + 1];
                arr[i + 1] = temp;
8 [8 z3 v2 V% L. ]            }
        }


        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
- h# `: J& V' f0 `5 \. x            //如果前面的数比后面的数大，则交换
! F" |; ^% A! }+ k% _            if (arr > arr[i+1]) {
! _! k; J8 q+ w" [                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
7 I# m: l0 T, O4 t! b
+ _8 `$ L3 @, t& X1 z" x/ D
        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
* K% v( ^' ~; B8 P+ Z3 K  j" i                arr = arr[i + 1];
; O6 q, i, I! `1 x7 w                arr[i + 1] = temp;
( g* X1 C* w8 [# Y  Y            }
% n. d4 e1 T7 l$ x$ m# B        }*/


, ~4 U7 X1 }+ X. b6 a7 B8 n        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
1 l6 W9 p; q' G5 g$ j; n

- d) x; _' k& ]5 _3 v2 n



        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;


        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
( D$ }8 i3 z4 s( U0 c' w0 l                //如果前面的数比后面的数大，则交换
: Q/ \5 B# D+ E                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
/ H  c% b1 C, D9 ~$ `                    arr[i + 1] = temp;
                }
            }
            //在内部循环的时候进行查询
# \" S8 W$ {3 w3 M6 S0 g& u            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
$ ?+ _9 ~) \7 E' v8 W6 b            } else {
2 K# X1 [4 i8 d9 E8 n                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
7 z  X, S8 e4 r! Q2 a  k9 p, I            }
3 Q6 E: C/ U% t: l- @* g# C        }
9 l8 D3 M8 N* W8 k5 F

        System.out.println("world " + Arrays.toString(arr));
    }
}
四、将上面的代码封装为一个方法
  A+ O0 ^' P8 r* R  m6 `public class BubbleSort {
0 T& B. b- H8 m3 q( F4 G) E, w    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};


        bubbleSort(arr);
4 p$ c4 r. v: {        System.out.println("world " + Arrays.toString(arr));
& d* @4 y6 F, [6 @    }
8 ?; g/ |# c3 i+ w
5 P- L" P8 Y" O9 A3 K: w' g$ c
  f) w+ ~  y1 J/ p+ ?3 k    public static void bubbleSort(int[] arr) {
8 b) @! K" i2 t2 k$ _) g        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
3 E0 A! S# R& e3 [        int temp = 0;
- D* v$ `: u) @/ t/ E: b5 y
* K8 m3 W3 v# [: }
% V& c9 {1 ~& ^3 }- a        boolean flag = false;
' l9 t: h1 t4 E0 L        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
6 H4 T4 U3 a: M1 Z& d                //如果前面的数比后面的数大，则交换
. n! i* N# `0 r# V5 n3 R                if (arr > arr[i+1]) {
9 K  {8 K4 x6 s" U5 W                    flag = true;//在这里把flag值为true
- C& K* U' @4 R; ?/ ]1 n) ]                    temp = arr;
; z& w3 r! Z& Z! F9 G                    arr = arr[i + 1];
                    arr[i + 1] = temp;
" _, _, W( H6 z( J                }
            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
9 F2 m* U" S- ~0 |2 [0 b/ J- Q                break;
2 L% Y5 `* ]4 ?- R; P            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
* h% n& h( u; Z5 w! x6 c  I        }
) r% Z: q7 I$ W. G    }
}
五、测试一下冒泡排序的时间复杂度

1、代码是实现

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


' Y3 y. G3 O! B1 U+ A( `1 f. O, g7 Xpublic class BubbleSort {
    public static void main(String[] args) {
- Q  w& t3 O5 E1 t        //1、创建80000个数据来测试一下我们的性能
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr = (int)(Math.random()*80000);//生成0到80000的数
2 v% O% Z$ U2 _1 S0 A  ]8 a        }
& o3 q+ o8 f+ V. g7 f7 Y        //2、输出时间
4 w3 Y4 H& a* }/ E2 w        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
. p  B! A* O- a$ C1 j4 e2 N        String date1Str = simpleDateFormat.format(date1);
% Z) x* C6 W7 l' r* w. t0 h        System.out.println("排序前的时间" + date1Str);
0 C6 R- Y! ]% M) |7 p" x" R$ y        bubbleSort(arr);
        Date date2 = new Date();
8 D; y  v8 m* G3 U' Y$ e        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间" + date2Str);
; o) q: `# Y0 S$ L. j
- |" @8 F# X2 r: Z9 V* ^! L
6 k5 W' |1 Q  i, W
. l8 A0 \% f$ Q- n0 O( Y8 c$ |
    }
& Q. A# A& l( x$ X

    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
4 |, k- s; f4 U( ]( ^- d, |        int temp = 0;

+ y7 K; n' ~6 R$ m! @+ m& q0 h
        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
* T/ U* `7 i' i            for (int i = 0; i < arr.length - 1 - j; i++) {
& p4 T; L- w% b                //如果前面的数比后面的数大，则交换
9 i& l" |+ K$ [3 l) v: C                if (arr > arr[i+1]) {
* X& t! d2 g+ r2 |" o& I                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
; o; B/ _$ Y* Z8 k- W' m: {% q% F            }
' A9 T2 v2 D( Z1 [3 }9 U            //在内部循环的时候进行查询
+ y  d' k+ F0 U4 j1 {            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
9 f3 ~9 e- _& D1 P; @7 D                break;
4 e( g3 x5 @# H7 H" o8 e2 G) B) \            } else {
3 m; q1 D, I5 D* b2 ?3 ^6 T6 |( W                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
) m& _7 U1 A8 W3 y$ _& T            }
$ s' T: t. Z: J; Y9 V0 j        }
    }
2 e1 B$ O/ g* S, x! V}

8 [* `3 t# n4 l! r2 `' y
- u% `3 L  r) P1 Q$ q; D+ n; {
0 l. n4 ^) w+ }6 y. f) S6 B, R2、效果


" I' P9 s$ \, O' k7 S' d2 y

" K0 Y; t4 I( ~# I5 M

470557092

顶。。。。。。
9 j- a( ~1 X4 I' U& ]
% c8 h' |9 }5 O! r# d( k. \