排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
8 Z* e8 {4 Y& ]) k4 J" N0 h了解冒泡排序是什么！
4 `& F4 W: F: C" n+ G- t知道冒泡排序的思路
8 g7 c3 \8 a( K* o! P知道实例代码并且练习
# [: p# b  T. y' q有收获记得帮忙点个赞，有问题请指出。
一、冒泡排序基本介绍
1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。

9 s! \8 {" B, P& F# u
2、冒泡排序的优化思路
因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。
7 X# w6 Y; _7 i& ]9 v, g
5 H# O" a4 j" l/ j% d! D/ z+ I
3、冒泡排序的图解思路
" ^7 f5 k& b6 E2 R7 m8 i- q1 z
1 ^3 n6 ?1 j6 q; @) }1 O6 \- d
其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：
8 f' c) u8 t6 A% `& a

- B) Y0 f' h% G2 f6 V第一轮循环得到最大值
# D. a- D. y5 G& B. P第二轮循环得到第二大值
第三轮循环得到第三大值
第四轮循环得到第四大值
1 ^; c1 @1 Q1 b1 Z总的要进行数组大小减1的词循环
2 G- e: G0 \! Y2 U! L5 W4 T) S

( b' j1 @5 B9 i# x% R# ^! N- x5 |二、冒泡排序代码实现package cn.mldn;

- Q0 z, }9 {* D. O) v+ b
' g1 Q; b( B' P, Q, n4 k1 Himport java.util.Arrays;

2 W$ T% Q: a0 M1 j- H
% m, _+ ~! ?0 B  H' R) f& X* x( [2 Zpublic class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
4 B! E7 F+ J2 x. J: h' ]        //大致过程
, \# C$ J; T: ^  `        //1、第一步就是第一轮排序得到最大值于最后
+ \! [& E0 t# X+ ?6 B$ a        //  for (int i = 0; i < arr.length - ; i++) {
: d' j3 f/ {6 z8 ~3 D8 H- K        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
; x: N. H7 a) ^% o' ]) K        //                temp = arr;
- R4 u5 z; E% ]* v) K# E# ?8 p        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
& ]6 |9 G  o2 [0 d8 h& L# X: X        //            }
5 T# }: d9 `" J. g9 k        //        }
$ \  H- b1 q; T        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
2 R" W8 F7 q4 |4 q. j        //            //如果前面的数比后面的数大，则交换
* M+ k6 x' a* Y        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
+ G' [8 Y. b/ c, u/ ]* x% {        //        }
+ v) X2 A$ T! U( g6 y3 z1 ]        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
6 e% e1 u9 q( \1 Q# z        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
3 U2 ^# G9 P5 l2 k2 V( L- E6 y        //                arr[i + 1] = temp;
9 M# y8 v! Y, e4 j9 e        //            }
' D8 w1 x) ?0 o, y        //        }
, a- p  A& h) N7 E& h0 {        //4、第四次排序，以此内推
, h" E) o+ [8 g5 g9 [$ K6 a        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
6 d3 m  [, K& X' v9 C) p6 V9 ~4 j. o( p        //                arr[i + 1] = temp;
+ b. b, R" O( }- ~- a% W  i% c4 p        //            }
9 o2 [+ ?$ R) }# u5 g5 r. h6 I% n        //        }
; ^1 z4 x1 Z1 Q4 p) q        int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
/ E& d4 h  {3 J" L            //如果前面的数比后面的数大，则交换
8 y6 p+ R1 g8 E5 k/ ?* E4 _4 w            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
. E( {8 x1 z. m/ E1 `- l            }
        }


        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
5 S' L" T. B; n1 G                arr[i + 1] = temp;
# y1 F# Q/ \/ V6 ~7 y            }
        }

6 r% x/ m+ d$ Q  E% {+ {) P6 J2 t
9 [9 a; Q0 M2 P3 j' V        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
' g: F& E6 l) [: V% ^$ h            //如果前面的数比后面的数大，则交换
9 Q- {* x7 `! g8 L7 _$ ^0 R9 n            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
' v4 }  e% |& N" s& F5 ~# `1 n            }
        }


0 a8 j( ?+ J! g- W/ _, Y1 e        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
+ I% p( v% e$ Q) C* _            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
# s) A  z  f& X        }
. B7 S+ }- l* j+ z! x$ \: N
3 w7 [1 c- |; U: Z0 q' t- }, H
        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决

; x' K. s- F6 B# O


2 U. w" M6 s) Q+ o: _& Y# e& B        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
! T* e+ L0 P! C+ B, H            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
6 {/ L# ], k  @                if (arr > arr[i+1]) {
                    temp = arr;
6 h) c2 H1 I2 g9 k6 ]/ w! A                    arr = arr[i + 1];
& J. l  j* ~1 S2 C3 K( ^; m* Y  Z                    arr[i + 1] = temp;
                }
3 }7 b0 H3 s) y0 L. s6 d% D$ E# X            }
! B! I/ g9 N2 B8 l        }
7 a3 P2 T& @" H3 h% a  Q7 q    }
}
三、冒泡排序的优化

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

package cn.mldn;
; K' |6 i- d/ Z9 ]7 X1 f: ?- F2 i

  C5 J( U; u1 N6 L- G1 h( dimport java.util.Arrays;
4 `  G! C0 X0 w6 I% I6 d4 A

) ?, G; [3 q( C4 u; v, Lpublic class BubbleSort {
    public static void main(String[] args) {
: T  T8 m2 m* G- B3 Y- a. h        int[] arr = {3,9,-1,10,-2};
        //大致过程
' `6 b8 j, b& j) L. h. f        //1、第一步就是第一轮排序得到最大值于最后
6 @& S4 A. k4 d  r! D        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
$ t* B3 a5 g" E( s        //                temp = arr;
8 L" r5 g6 `) b( g1 g7 Q        //                arr = arr[i + 1];
0 i  J7 b! x9 d5 e, @        //                arr[i + 1] = temp;
- T! U1 a& r( A* v) b        //            }
        //        }
' a% R; v# G9 q  O* v% x        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
+ L' x8 Z# \3 u: O* ^        //        }
        //3、第三糖排序，以此内推
: i! V( q% X. i- I+ H& H* r        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
9 g2 k4 c* b* p        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
1 c6 j% P* g; G# l' h  }" m        //                temp = arr;
$ n" X& B, N9 p, k( G3 o        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
        //4、第四次排序，以此内推
9 B, T7 }% |5 h. W  u        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
+ p8 \% W3 C( H, m. D        //            //如果前面的数比后面的数大，则交换
2 B. [4 X0 f' k3 }        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
        /*int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
, m0 ?& N% v7 H2 J( v            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
1 S) a, q0 i; A4 Y# X, V                temp = arr;
  @" n9 r9 f* n* _" F                arr = arr[i + 1];
- `5 O) R5 }3 D; J5 z$ y  t- F  }) x                arr[i + 1] = temp;
            }
$ l9 n- R6 K& {        }
& R6 J7 _* O% q* V( b8 O
% M0 g* ]) n) ]2 Y6 |( u
7 m  U& [5 x( g        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
1 \; @6 e) h: I' v" ~- [( _            }
4 n. r  q' X" J+ f: p! f1 t, a8 C3 H        }
% J% v' w  H1 n* s

+ A* c5 A2 p5 M7 V% G& N        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
# Q& S$ n' l$ F/ l. o                temp = arr;
                arr = arr[i + 1];
4 m+ @. v6 U6 }# i% I  l# h0 r4 g* N                arr[i + 1] = temp;
            }
        }
' z2 u6 |) m  J/ i) @/ ?
8 a: X( b0 N# C, {7 K2 Z
, O5 Q/ g7 T7 b1 L( z' A! p2 V        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
/ u! h  h- s) ?4 s  e2 \1 k            //如果前面的数比后面的数大，则交换
$ H! r+ b; {$ k4 M            if (arr > arr[i+1]) {
. z2 W, [/ Z6 p8 S! w1 b                temp = arr;
, o& Y" Q/ w1 b8 J                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
. D: k& O, N" n6 {        }*/
& h. _* Q/ E* w& K) w
" g- ?8 j1 A2 D- n* j6 b3 ^, i
. J% ]1 d7 w6 q; n        System.out.println("hello " + Arrays.toString(arr));
+ a5 i$ z8 g+ W, s8 X2 I" }; I; y        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
6 o" B0 D& U0 _( e/ H




+ H) l# G% ^1 n3 o  X7 p: X
" N$ m" e* I2 E' u        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
5 F6 A" B: a, P0 ^) N% W5 J! b        int temp = 0;

& N' s* h& @7 u6 c0 ?6 B" l
        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 D. o2 s3 W% N* R                    flag = true;//在这里把flag值为true
                    temp = arr;
6 U" C  g% q2 c. `; c# e                    arr = arr[i + 1];
0 q3 Q" y0 t. j7 Z4 H, t$ R/ R                    arr[i + 1] = temp;
* N0 M- s1 }( \$ \& F* ~4 G, L( J                }
            }
8 Z. N6 _& f( r            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
7 W; _+ j, _; n& M+ w: n% W" Z                break;
9 @. @9 m* U- N            } else {
- N6 k. L: e- @0 p: W- j0 \                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
" z2 e8 m0 O9 B

! J5 [2 O9 Z8 l6 j: y1 A        System.out.println("world " + Arrays.toString(arr));
" _( s; x) m' w, D    }
9 q1 z5 f, ]5 f+ _/ f" O}
四、将上面的代码封装为一个方法
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};

6 K' P! [# c4 V8 M6 s8 s
9 N( u+ l$ j3 ~& u3 t0 e" ^: A        bubbleSort(arr);
1 ~5 L: f/ y. m" o) |        System.out.println("world " + Arrays.toString(arr));
    }

& Z( G& N5 V) X8 G& w
    public static void bubbleSort(int[] arr) {
0 F8 W" l% d% c# Z( l5 H! w        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;

# h* A  s; g4 B! e( M8 |& n8 `
$ n4 e- U$ f; n) p% A% @        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
8 D% a; E: |3 Y, q4 \6 J            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
4 ~: E( ^) J, P5 j  b                    flag = true;//在这里把flag值为true
) ^) }# J% ^+ Y1 A: }5 F                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
% I/ s/ B# c7 \$ Q+ p) Q3 [                }
            }
( B; j6 j& a. h$ S. g# C0 o7 g9 j0 D            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
9 G4 P0 z/ }  f4 v            } else {
, x4 D! ~, P; I. P+ j5 E7 `$ U                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
- }/ n: t& o: o' e) L$ Q- r# S    }
}
9 N7 ~" Z. {9 @3 j5 J% w$ k/ Y五、测试一下冒泡排序的时间复杂度

1、代码是实现

import java.text.SimpleDateFormat;
* T& M8 o' z/ c9 O! i0 timport java.util.Arrays;
import java.util.Date;
, A* R  c2 {: r" v; ?; f/ G% s9 W
; Z! P. p7 G  I/ h  X
public class BubbleSort {
6 O$ p) r: Z5 ~' }    public static void main(String[] args) {
        //1、创建80000个数据来测试一下我们的性能
        int[] arr = new int[80000];
$ j: W( y) [/ x1 C/ A: Z& ]        for (int i = 0; i < 80000; i++) {
' M/ Q% S5 h, ]: ~$ r            arr = (int)(Math.random()*80000);//生成0到80000的数
        }
% ]- Q* H/ W: M        //2、输出时间
) Y2 r& T* F# Q4 J+ u        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
        String date1Str = simpleDateFormat.format(date1);
0 i+ {# q4 {; x( K  m        System.out.println("排序前的时间" + date1Str);
        bubbleSort(arr);
8 w; x7 l+ k7 w5 o0 u        Date date2 = new Date();
2 V2 o; c+ p) C9 F- t, J  K2 S        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间" + date2Str);



0 G% |' l' a8 P9 S- W! k7 R
    }

& {6 L/ y! |& [! z: o0 J) P# Z" X) ?7 S
    public static void bubbleSort(int[] arr) {
" O' P' }2 k0 W0 O8 F. E        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
* a# K! k7 ?9 f        int temp = 0;
; K( A1 n- g) I$ e. |2 ^
' d$ J+ o0 H* r0 M0 I) Y
        boolean flag = false;
0 J/ ?$ I7 p7 v1 p, L# H        for (int j = 0; j < arr.length - 1; j++) {
( J9 @  X+ g$ }" I- S            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
                    temp = arr;
5 T2 r) z  R; _5 W; F                    arr = arr[i + 1];
  E7 p: @$ [- J. \  E4 l  C                    arr[i + 1] = temp;
                }
            }
9 H. l9 N0 W- d9 ?/ P1 {            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
' k0 ]7 K0 c3 h                break;
            } else {
6 [7 m. Q0 {5 P3 A. f                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
( K/ r4 q0 T; Y        }
    }
" \9 U, i2 ]9 v}

; \% q0 D$ l& l# e

4 n( n' a  j5 U2、效果

% p9 ]) V, a1 D; N6 A4 [
9 c+ ]# M! {2 z: m1 a- |

470557092

顶。。。。。。