排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
了解冒泡排序是什么！
! o& |- v0 n9 j+ t/ ^$ E知道冒泡排序的思路
知道实例代码并且练习
' D  B" i* O- q  m( w有收获记得帮忙点个赞，有问题请指出。
一、冒泡排序基本介绍
1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。
6 D/ A+ E& k4 S+ V
/ g4 P7 \# a7 p) `
5 |0 d) Y; s8 F" r1 m& J2、冒泡排序的优化思路
1 X' s$ l' g2 V8 o因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。


& K( H1 w; d$ r$ i3 d3、冒泡排序的图解思路


其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：
  f+ G- W- k" U0 u

" i! Y6 s7 D8 J5 {第一轮循环得到最大值
第二轮循环得到第二大值
第三轮循环得到第三大值
第四轮循环得到第四大值
总的要进行数组大小减1的词循环


二、冒泡排序代码实现package cn.mldn;


import java.util.Arrays;
& J$ ^' y& ?) q5 @9 G/ t# l+ A
: z9 C, n7 F) n  E2 C: h1 y
public class BubbleSort {
9 v+ B! s6 h; J4 B: @    public static void main(String[] args) {
+ ~& `  U/ w' z        int[] arr = {3,9,-1,10,-2};
) b! N8 E, j. L* e+ x        //大致过程
7 J3 h1 Y( [. `5 I        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
# k4 f. J1 \' a6 `2 C/ e        //                arr[i + 1] = temp;
        //            }
        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
' k8 k( v) f" ]& x        //            //如果前面的数比后面的数大，则交换
. c1 t: _1 Q- @8 o# D7 `- k        //            if (arr > arr[i+1]) {
! [+ }" }" v7 _& W        //                temp = arr;
: e7 Q' _9 N% A! C2 R9 [$ J8 T        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
) r. X/ L" U) I0 g# j9 l        //            }
        //        }
5 `% x) }% S8 J        //3、第三糖排序，以此内推
% q2 W0 C( x6 A        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
) @- O: d6 L1 x! }; F        //            //如果前面的数比后面的数大，则交换
4 D8 U  \4 S9 l  w& F        //            if (arr > arr[i+1]) {
) I9 p8 R2 K4 p+ i7 e1 Y  M        //                temp = arr;
3 ^1 [9 P! {# }( B' `7 f+ q        //                arr = arr[i + 1];
. _( W: T! U; u+ ^# Z$ ~5 B8 Y# ]( X        //                arr[i + 1] = temp;
        //            }
        //        }
        //4、第四次排序，以此内推
, s# D9 y& R# j5 D        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
1 H0 H! {/ a4 Q1 r$ C  W        //                arr = arr[i + 1];
( h; N- Q7 b) @0 ?5 [5 n5 w        //                arr[i + 1] = temp;
        //            }
( _2 g$ \$ W. _1 H3 K9 J        //        }
" T: V( ^  Z: j5 n, {% g) [$ ~* ?        int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
# I/ l6 L0 Y5 l9 Z            //如果前面的数比后面的数大，则交换
+ @0 K$ R, J( B! a0 v/ r5 \8 r            if (arr > arr[i+1]) {
  z4 F; f+ P; g0 n6 d! [                temp = arr;
1 ~9 |0 ]; a% y7 F( H0 B                arr = arr[i + 1];
                arr[i + 1] = temp;
( q, b5 [0 O4 g  _% T; U: N. C& w            }
        }
/ b7 P, M) ~) X) g6 o

        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
9 Y1 n4 p! f( g  u% k                temp = arr;
/ S; L  \5 b& H, P2 @                arr = arr[i + 1];
                arr[i + 1] = temp;
6 K% `9 S! n& `1 z4 j            }
        }

2 Y: b1 Z8 t" t* _0 g$ m
        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
* h9 T" m9 q, \2 L% u( I            //如果前面的数比后面的数大，则交换
2 S+ R# L9 h' m            if (arr > arr[i+1]) {
                temp = arr;
$ G  E) w0 G* T4 c0 a" H- c                arr = arr[i + 1];
                arr[i + 1] = temp;
1 i- s/ E& `4 v% O. {" o( ]            }
5 Y$ b$ H  z, b) m        }
6 k$ F5 P: u( M; Q  n$ U

        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
5 U+ W5 S% M9 O- V! q  v2 m            //如果前面的数比后面的数大，则交换
7 j: u3 D. F0 E+ f            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
7 F" X6 G8 U$ z' ^5 w& ?1 Q  [                arr[i + 1] = temp;
, u  M3 E# z4 m4 a            }
        }
5 Z9 u, Z; ~  p! [5 n

: [3 ?4 G0 j+ z& R4 }1 [        System.out.println("hello " + Arrays.toString(arr));
" u( x$ z" X% o8 E. Z9 {$ U" E+ V# R        //------------------------------------------------------------------------------------
5 u6 I) ~$ N7 v' T, q' t0 S: L        //根据上面的观察可以知道了撒，可以再用一套循环解决



* q3 j  ~6 E4 t4 H9 w9 l
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
$ a7 U& ~4 E* b1 d7 |# e            for (int i = 0; i < arr.length - 1 - j; i++) {
% Y1 Q) Y  J& W0 d                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
                    temp = arr;
                    arr = arr[i + 1];
8 Q$ X# \2 f* p. U& ]# c% _$ o                    arr[i + 1] = temp;
9 _: J% e7 `7 X4 a4 h                }
            }
4 `7 V- S; |% ?8 k* ?        }
    }
}
三、冒泡排序的优化

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

package cn.mldn;
, k9 O' a1 c2 _' `9 z
- [, h8 k0 E! w+ I
import java.util.Arrays;

" Y! x: R7 J! O. b8 j
public class BubbleSort {
    public static void main(String[] args) {
$ L. r2 }5 r, L8 z5 w& M        int[] arr = {3,9,-1,10,-2};
        //大致过程
  g% f1 @! e4 V1 p1 _9 [        //1、第一步就是第一轮排序得到最大值于最后
: e; n0 X8 q6 A9 F7 W1 _5 e        //  for (int i = 0; i < arr.length - ; i++) {
, O# G( Q! I# Z        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
% L3 _: r# f3 J. F8 Q( W; D1 x3 m        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
) ~3 g' |5 ^/ P. Q        //            }
        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
" b# O1 e" I. ?9 |        //            //如果前面的数比后面的数大，则交换
. U- l1 [! M2 E1 {  o4 R        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
8 t  z1 {- h0 `% ]2 \: m7 \        //                arr[i + 1] = temp;
9 R: z$ d  l$ K& F        //            }
        //        }
        //3、第三糖排序，以此内推
* H6 d( `) l, q        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
6 v7 C- p. ]  j  H$ T6 @( W! a        //            if (arr > arr[i+1]) {
: n; q2 }8 @( W/ A1 \        //                temp = arr;
) ^4 {$ z+ m* |, M6 X! J9 r6 K        //                arr = arr[i + 1];
% h3 U* s. U: A# U4 N( s( Q  K  J        //                arr[i + 1] = temp;
" n; {4 v* x' P1 ^! P        //            }
) F; h& J) m) m7 F- D3 M) V5 r( y9 o        //        }
        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
& L6 w2 a; p& r/ I) v* l+ ~: s        //            if (arr > arr[i+1]) {
2 X/ [2 r, u( H1 K, ], }4 D+ \; N        //                temp = arr;
$ }, N) H' V  H1 P        //                arr = arr[i + 1];
* r( Z7 P/ k8 K$ r1 W& r. v- C9 K        //                arr[i + 1] = temp;
) A0 Z7 H" `( ~- v- P+ \0 [        //            }
+ `' p% e1 E5 Z        //        }
3 G, N  ~6 ~% |0 |9 z" N        /*int temp = 0;//零时变量，用来将最大的数值排在最后
3 q- T7 {4 e) I6 o6 G        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }

3 k( t, c4 U7 e& v+ K$ ~+ I  u  B
  V' p8 @' V$ E        for (int i = 0; i < arr.length - 1 - 1; i++) {
. [  L! u: A1 r            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
- m; Y9 ]+ i. w% q+ n5 N: v& V) R                arr = arr[i + 1];
% R+ [% I* @1 e8 T: M+ v                arr[i + 1] = temp;
            }
/ b; ]1 X( u6 r! e3 h" n        }


        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
0 B, U$ e4 j' A0 s: V            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
8 z! j; y. r/ i+ V/ E9 q6 X        }


        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
7 G  ?0 P, m. M3 J6 T            //如果前面的数比后面的数大，则交换
  b- x/ d  u$ i            if (arr > arr[i+1]) {
                temp = arr;
( ^, p) v+ y$ ^( Y. ~9 C                arr = arr[i + 1];
! e! _& J/ \' C% |( w; l* T# N                arr[i + 1] = temp;
: N- _0 t5 ?0 U            }
+ Y) J6 B3 N- V) h% N        }*/
' l! ?& u$ o% s8 @  i: W
, [- u) I7 E! s: h7 X  J8 W. e
        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
) ~0 R6 q6 |- I$ L; w) Y" s
) h' y, P. l' o
5 i3 V' j4 J/ E
( q0 w6 _/ S; p4 p% F, ^* u% j
: E5 S9 Z9 z2 A# V8 _# {! D
8 z% z; k0 F  k. k
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
7 Y8 H4 g: l7 B0 y7 f        int temp = 0;


        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
" m4 Y7 C0 F- P( H, V            for (int i = 0; i < arr.length - 1 - j; i++) {
1 w) W: W5 G( T& R  r6 i7 i                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
+ z2 P4 J- E# h) ~9 c8 p9 T                    temp = arr;
                    arr = arr[i + 1];
% j0 R' s5 `' R2 b, _$ C6 q                    arr[i + 1] = temp;
  W  ~* P- P1 x  r                }
            }
7 A8 w7 _5 b% [# }            //在内部循环的时候进行查询
( s2 R# y. L6 E; u1 N. }) L            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
- x- n# B7 N: ?. R1 h) n/ Z" K                break;
            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }


        System.out.println("world " + Arrays.toString(arr));
$ g9 l. D4 z9 b, m/ r    }
: b' y4 d6 V/ q! s( U}
, ~6 e' f% q8 @5 [, C4 Y+ j四、将上面的代码封装为一个方法
public class BubbleSort {
; L* o/ v+ q; c: }5 D( ?) G    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};

) x- K& y% m7 U' L1 @, [4 ?$ w
        bubbleSort(arr);
        System.out.println("world " + Arrays.toString(arr));
    }
# \4 m! T! ?2 L

( k& y( y$ v5 W1 }  `$ y    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
8 P+ r- ], n% k8 b+ @' E        int temp = 0;
- X; a1 r0 o9 c8 m5 \: B

6 W- a% ~3 ^. Q/ X" p2 d        boolean flag = false;
9 F- A* o) v2 |( r        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
9 j1 h6 ?4 b" R9 Z                //如果前面的数比后面的数大，则交换
9 z# @# i; ^$ w* }; R: P0 V& A                if (arr > arr[i+1]) {
( ^/ S0 B3 I, D( s                    flag = true;//在这里把flag值为true
7 A( d6 v9 t. l3 R- r                    temp = arr;
- w) O, I' k7 s  ?                    arr = arr[i + 1];
8 |$ M# o% M8 U9 V( K/ F                    arr[i + 1] = temp;
                }
& k4 K1 L+ A' J' Y9 w% }' e# I8 ~# }            }
            //在内部循环的时候进行查询
5 B' e( B3 Z4 S- u5 w& a            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
/ w& S: }6 o; f                break;
# W6 h) R, w3 |, U) j% @+ o            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
: O; ]+ N2 p0 g            }
        }
9 G. T6 H+ a# I6 B, B. x    }
}
五、测试一下冒泡排序的时间复杂度

1、代码是实现

import java.text.SimpleDateFormat;
! t; [0 d2 ]. z; k2 U- {3 i# gimport java.util.Arrays;
7 X6 d9 r8 ~  r& `4 b' B3 Aimport java.util.Date;
2 x; r: ~4 j6 \8 P* V: D" M

public class BubbleSort {
    public static void main(String[] args) {
        //1、创建80000个数据来测试一下我们的性能
/ t2 u9 ~9 E; ?1 {7 M        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
2 _0 }2 J6 h1 u  m            arr = (int)(Math.random()*80000);//生成0到80000的数
        }
        //2、输出时间
2 h( L4 M! {$ W, W        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
( E! N! T( a1 T5 a        String date1Str = simpleDateFormat.format(date1);
9 E4 ]0 Q6 t" ^  j$ T        System.out.println("排序前的时间" + date1Str);
& F3 B8 F3 P4 H# k1 p9 O  s, e        bubbleSort(arr);
, {  Q8 {3 P4 ~  S+ W        Date date2 = new Date();
" @9 y2 |# s7 b: E7 {5 I' l        String date2Str = simpleDateFormat.format(date2);
; f8 }! K! J/ d* y        System.out.println("排序后的时间" + date2Str);


# Z' Y0 S7 Y* t$ _/ d. ^4 H0 Q, F6 @7 z

    }

: I( O) a; K3 i- j4 d
1 V% R7 `/ b1 J2 N/ h6 W' [    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
4 ^: Z5 \6 E& M, Y- e4 _) {  a' p        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++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
0 g9 J7 _& L- p6 O6 o1 G4 v- i+ a                    flag = true;//在这里把flag值为true
                    temp = arr;
7 Q8 y! p2 t+ ]7 Z                    arr = arr[i + 1];
. _0 L4 @/ h1 x2 X5 G2 V0 R                    arr[i + 1] = temp;
                }
6 a4 ~' u% H1 r! ~! s, N2 B( i            }
0 O8 E( p, E: e            //在内部循环的时候进行查询
9 L: }6 @# F: G$ ]/ ^            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
3 q. n- \# j+ A4 f        }
    }
}


9 v5 y0 }$ I% {
2、效果


- u$ ^6 A! L, H
  [& l. f; q2 C

470557092

顶。。。。。。
$ w3 t3 c- B7 ?4 h6 [% X0 i5 k
; u- Q4 `0 j6 |1 y: Y  h3 L) @