排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
了解冒泡排序是什么！
知道冒泡排序的思路
8 m8 L$ E7 b$ V9 M+ ^知道实例代码并且练习
7 B$ O2 R9 ^2 [+ e3 y有收获记得帮忙点个赞，有问题请指出。
一、冒泡排序基本介绍
1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。
+ D6 d4 z! d& c% m0 a
' \) l8 e+ y2 N$ W6 g, ]
2、冒泡排序的优化思路
8 b  ?) K) |; @) z8 T: {因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。
% R" i$ \" h5 o7 h2 b7 A
& i( M6 m3 a2 n9 [/ h
3 J2 K5 K" X( Z( _9 P3、冒泡排序的图解思路
8 X/ K# w9 F- }( n. G3 R" V( r
3 o) C- V0 i. Q& f0 d
其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：


# A8 T' @2 R1 x; n& @6 H' W第一轮循环得到最大值
第二轮循环得到第二大值
第三轮循环得到第三大值
第四轮循环得到第四大值
- D( l+ W6 b! d- [' g总的要进行数组大小减1的词循环
/ P# ?6 g! U7 A* E0 S; v

二、冒泡排序代码实现package cn.mldn;
: ~+ d) N: r, x! X

import java.util.Arrays;


3 [( o: m- O/ R5 p+ e3 spublic class BubbleSort {
7 c' f; \! b+ f; e# S    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
. `- m' r7 @: Q& t# d        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
( @0 h) }* N) i9 [        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
% @- T! N  x$ k4 N6 o8 ?# H* S( C        //                arr[i + 1] = temp;
  m$ Q4 l9 {- Y; C. L) ^        //            }
        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
3 d% B2 _$ q" w, k/ l        //            //如果前面的数比后面的数大，则交换
4 M0 @0 q6 g7 r        //            if (arr > arr[i+1]) {
; R+ F: c% _* `( _! D* L9 e/ h        //                temp = arr;
, C; [% N6 H8 U* b6 v- ~8 `# o5 D        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
& E. |! f# l& ]6 q/ N* b        //3、第三糖排序，以此内推
/ R. o7 }) M9 |/ S" b( t1 t5 v        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
2 T  u- F- o0 n$ F+ O3 S( J7 T" R        //            //如果前面的数比后面的数大，则交换
: B! m1 [& u  y$ p        //            if (arr > arr[i+1]) {
; J1 ?7 o: y  f- U' \7 t# {4 A        //                temp = arr;
        //                arr = arr[i + 1];
; w# I0 ], _9 F( M        //                arr[i + 1] = temp;
        //            }
5 e0 j" f- \0 K) X% P- n' a        //        }
        //4、第四次排序，以此内推
  h- `; G; R& b# O/ ^# V" l        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
+ O. r, c' ?6 J        //            //如果前面的数比后面的数大，则交换
0 M2 _( {; |" _4 Y! Y        //            if (arr > arr[i+1]) {
, Z) M1 T+ F! {4 V) A3 i- i* Q" {        //                temp = arr;
' q' j& ~& x; L! g        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
( B! j  Z1 [8 H- G        //            }
        //        }
        int temp = 0;//零时变量，用来将最大的数值排在最后
( \8 f- i4 j0 e7 @7 G" M# }        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
0 X* h9 k: r, Z/ u7 ]            if (arr > arr[i+1]) {
                temp = arr;
+ z. Y, r3 f# ?- K& T                arr = arr[i + 1];
' e5 u* W, d' g6 A' n; |                arr[i + 1] = temp;
            }
" r  Y, D1 z3 ~0 X0 e  S        }
9 p! `; F& `5 U, m7 t, _9 B" K

! A) _- O8 U$ s; m4 t        for (int i = 0; i < arr.length - 1 - 1; i++) {
, m4 G2 j" Y/ S) [$ r% j% L2 T            //如果前面的数比后面的数大，则交换
: W# F7 ]+ i8 Y8 h            if (arr > arr[i+1]) {
" ^9 ~: M5 q# \! N0 Z' ?8 x                temp = arr;
' @6 E; v9 ?2 D8 I                arr = arr[i + 1];
                arr[i + 1] = temp;
+ V) j5 {8 i7 F1 b9 @8 O: ~7 V# d) e            }
        }


5 e) ?* u+ Y$ }) X- u        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
* P- L0 E( H  @            //如果前面的数比后面的数大，则交换
# T1 T. }$ W) a) z            if (arr > arr[i+1]) {
                temp = arr;
( b. Y  f, u; h/ S                arr = arr[i + 1];
                arr[i + 1] = temp;
# U8 ~* i- a7 M; u, I! Y, ^            }
5 |/ i- t  V$ L        }

# D; Y  Z7 d3 R! k# ~& ^* I% ^
        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
: L! w. Z5 S0 t$ i  t" R  N7 P            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
9 K4 N5 b" u% c: V# y- V/ y                temp = arr;
4 {1 b" x1 S! L; S5 @8 g( V5 K                arr = arr[i + 1];
  \4 `0 c5 O. E7 F5 Z  ~4 n                arr[i + 1] = temp;
2 M0 ?4 W1 i/ b& W            }
        }


- \" {' I9 N0 [0 K- i) n/ Y        System.out.println("hello " + Arrays.toString(arr));
3 ], [; u  @, t" ]- a3 t" c. _        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
4 d4 @' O! c9 s" I2 b0 B& P( O


; K, T* N# h8 E
' t9 F/ G4 f7 W3 _1 w6 l5 c& `        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
( s8 c$ M8 f& [- U7 q        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
, n$ G( q, p' K; d' C+ T  g3 |                if (arr > arr[i+1]) {
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
. p& {* v. i8 h; ?  j                }
" n0 s6 p* H6 \, `            }
        }
    }
6 Z+ R4 k* Y  |/ Y" z. u. _0 }; o/ H}
三、冒泡排序的优化

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

package cn.mldn;

. c5 N. O8 ]  ^1 a
* C/ ~! m, I- m; ?( i( Uimport java.util.Arrays;
" ~& r; A1 O) v) O+ C$ o; A7 m  O. x

public class BubbleSort {
( T/ z% y, V! W, y8 t) B+ K: g, W    public static void main(String[] args) {
: f: b0 {& B9 j8 }; {/ {4 _        int[] arr = {3,9,-1,10,-2};
        //大致过程
1 e+ g& V, [% B3 ~" ?) ~4 Y        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
& x8 ]* L5 e! L2 Q        //            if (arr > arr[i+1]) {
' Y9 q) ~  _1 \        //                temp = arr;
        //                arr = arr[i + 1];
+ @7 W# M+ Y+ w$ v; Y& i" `        //                arr[i + 1] = temp;
        //            }
        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
! G/ k1 Y$ q) n+ @. p+ E( [        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
! |/ G' B$ t$ a        //                temp = arr;
) M, U) g- j9 K- o9 s% Y1 s5 i        //                arr = arr[i + 1];
" Y( c& w1 b8 \: z& B1 x/ S        //                arr[i + 1] = temp;
        //            }
- f. p+ f/ z/ x. ]/ j, y        //        }
        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
" b' d" S8 J- ?# }        //            if (arr > arr[i+1]) {
        //                temp = arr;
- z3 M5 q8 R9 D; X" R* N% O        //                arr = arr[i + 1];
6 D& L1 C# u5 x5 @. c1 W9 z        //                arr[i + 1] = temp;
* i9 x; G) G) o) @, I        //            }
! Y  K& m1 g6 x4 M        //        }
        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
, L: h7 v; d$ z        //            //如果前面的数比后面的数大，则交换
: |0 a3 Z8 }6 n/ l        //            if (arr > arr[i+1]) {
. {, p1 `# g3 |% F. T& m( Y        //                temp = arr;
; i6 T* U3 f* ~# _- Q( o% F0 S        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
) [, r3 v+ _4 T        //        }
        /*int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
$ n8 U! C! ]! K" O1 c            if (arr > arr[i+1]) {
2 _# N& ?( g0 w: q# d+ E                temp = arr;
: G4 Y- E0 P7 {2 E5 d1 u                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }


0 @" Y1 f% E- S6 c1 t2 J4 C        for (int i = 0; i < arr.length - 1 - 1; i++) {
  ]# h4 s" j7 r" E& g! Q            //如果前面的数比后面的数大，则交换
% @  Z. n4 ?3 V7 p% o/ V! r$ a            if (arr > arr[i+1]) {
                temp = arr;
" k" i8 m) u5 D7 {% K, i                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
* a8 U2 `" s, C- Z+ t

        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
; [$ G- i- z; D1 h; N            //如果前面的数比后面的数大，则交换
3 w& N9 N) h5 Z0 _+ g7 E            if (arr > arr[i+1]) {
, \9 i8 W: y# W! q* U6 |3 H                temp = arr;
) ^' u/ F. i! Q; U+ c, x                arr = arr[i + 1];
                arr[i + 1] = temp;
2 _4 F& w0 {% g$ x/ l* |' p            }
7 k0 i/ C! P) {3 C( ~+ f        }
* K( Y% V) }8 N* L- K
2 {3 h, {) u& Y$ q5 U" I) ]
0 r  V( t) W/ P) C9 A        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
7 G. _# [( ~2 @            if (arr > arr[i+1]) {
) c' \* _) ^5 [3 j' h" z" X                temp = arr;
, \4 K8 _. Z8 V/ ~                arr = arr[i + 1];
2 A$ s9 m9 x# A                arr[i + 1] = temp;
* G9 u; L3 n, y% o  H4 ]            }
        }*/
3 x$ F, C9 L% q. j

        System.out.println("hello " + Arrays.toString(arr));
1 |+ z# ^5 j) j( u* U3 A8 x        //------------------------------------------------------------------------------------
& n1 o; }( t+ T4 W4 p8 n" \  h        //根据上面的观察可以知道了撒，可以再用一套循环解决

/ f5 @( f6 u: v5 `0 K0 t4 d



/ i, U# o/ {4 C8 A* s2 l
* w0 ?4 a2 c1 d' Q& ~/ k        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;

. C+ S  o0 ~4 N8 x$ o* V2 N
        boolean flag = false;
1 _0 L7 n; ^1 J4 ]9 C+ T        for (int j = 0; j < arr.length - 1; j++) {
; p* [' v* t: I/ Y# P1 M            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
( }6 U- i4 @  }. q                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
" R8 c+ F$ A4 ^( a                }
            }
* r7 S; Y$ z/ g/ Z5 {+ S            //在内部循环的时候进行查询
' ?" T; Q2 F2 d( f+ t: M            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
- @+ R3 f2 {# j. J' T                break;
* T" Z9 _, F& P$ _            } else {
7 K+ N2 d/ g; d' G% X2 ]                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
$ u5 o" r( g  R- d( X            }
        }


        System.out.println("world " + Arrays.toString(arr));
, w8 s) t- O9 `" R    }
% Z* t* i  J8 J7 e' D0 f+ @}
四、将上面的代码封装为一个方法
3 W* r$ e! f9 j, npublic class BubbleSort {
% P- G7 l; m% x. U    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
- |! F" v- j+ j. C, [& A

: g$ f+ _" P% B+ |8 ~9 a        bubbleSort(arr);
# `: L% x. {8 u, X6 E" w  i9 t        System.out.println("world " + Arrays.toString(arr));
    }

+ U9 D  P% ^7 p  ?
1 _% c; `- D+ Q7 |4 v# U    public static void bubbleSort(int[] arr) {
7 E* {% X: ]; q! ~! W        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;
% v& W3 f/ U  z- g/ [" Y/ A# y& P
/ g2 U3 q" C% r; q% n6 ~& ]
        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
, W7 D. L# J6 v4 k: `                if (arr > arr[i+1]) {
# x/ g9 }9 E4 Y2 K                    flag = true;//在这里把flag值为true
, i, K3 C7 Q5 X' ?: f+ p) J                    temp = arr;
                    arr = arr[i + 1];
1 O$ C: L4 j  b$ {0 q& e9 a                    arr[i + 1] = temp;
' C9 K* [, ?; O                }
8 q: }# z) q) ~, h* B1 T- e            }
; `/ h1 x: {1 y6 d/ W2 ~            //在内部循环的时候进行查询
# Z4 P$ |# r/ ~            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
7 T  h+ e7 s% _1 Q0 ~" Z8 e3 b2 y, `            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
  L5 \% y9 K  J6 H            }
/ h, p: n3 D; d4 z) L# B9 Q6 k6 H        }
9 `4 U; s& m9 L0 F. f2 a; t& t$ f    }
}
五、测试一下冒泡排序的时间复杂度

1、代码是实现

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

/ \4 I  x5 o$ {
public class BubbleSort {
    public static void main(String[] args) {
        //1、创建80000个数据来测试一下我们的性能
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
3 f' C% G( |9 T' u& i3 A& S            arr = (int)(Math.random()*80000);//生成0到80000的数
        }
        //2、输出时间
/ H" I+ c: `  H+ l$ E4 P0 P1 w        Date date1 = new Date();
- q: n: Z3 J& i4 \9 v. C" C        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
        String date1Str = simpleDateFormat.format(date1);
, G, V: ?7 @4 U. P. L, O' z        System.out.println("排序前的时间" + date1Str);
        bubbleSort(arr);
& d( `# U. p8 L. G        Date date2 = new Date();
" T: q0 w$ Y! G1 t: c; a0 z" Q        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间" + date2Str);
- A( {- v" w3 x) U

, |* q/ N  `3 n# a. [, h; U' F
/ [0 b7 x" I8 ~9 B0 ]3 f' H
( D+ J5 O" e/ m) w    }

& Q) D$ z' [% }1 Q7 }) W
  X$ h0 C9 F1 B7 M    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
9 {5 E* g8 ]* R        int temp = 0;
. J. S) k) H; K* [- T# k

# k7 F4 s( @8 D$ I' P        boolean flag = false;
' V: b% H. B' R7 e% h' t# q0 Z        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
7 `5 {# r' F8 k- V$ s6 [                    flag = true;//在这里把flag值为true
9 ^  G- E2 K& X: x4 z$ L6 @, I                    temp = arr;
" l$ y, b0 t/ t! x' }3 y                    arr = arr[i + 1];
6 Y; M2 j) P/ u, S, B: F, t- `) A                    arr[i + 1] = temp;
                }
            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
( s; C6 L% L# Q1 p  y                break;
3 A. G) V5 d' `  |            } else {
9 c6 t: T' g" Y. a( P: z                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
8 K, y( l& x  {1 f4 s$ o            }
        }
    }
}
' `/ w( J0 \4 G! b9 X

6 ^! s" e5 C7 U: Y- N; W6 B# E
2、效果
4 |+ i8 i6 ]) D# ?! h% P, ^  r

* Q# Y- h  u' u+ O* ?

470557092

顶。。。。。。
! A$ N: G8 @3 E5 z0 S: m: J7 B
9 X/ Y& r4 y$ D