排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
' d. w' Q. K, o  ?5 W, @1 n% W! v了解冒泡排序是什么！
知道冒泡排序的思路
知道实例代码并且练习
; D' o7 K; F& j9 q. ^& J有收获记得帮忙点个赞，有问题请指出。
一、冒泡排序基本介绍
' `$ g7 q# r7 B1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。
# [3 Y! p0 A; y
3 m* c* ]; n, L! \+ h5 k
2、冒泡排序的优化思路
  |/ d5 }* x# ^2 s" R+ M因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。

: S. z% k- q+ Z' ~( n2 s% v* e
; J7 G5 Y( I" Y. S# @3、冒泡排序的图解思路


其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：
. u! X/ F; F* F. s9 {
7 h. H) J, @8 Z) ?) ]
第一轮循环得到最大值
0 V* Y# I  F" z5 C& N& @; @- q第二轮循环得到第二大值
第三轮循环得到第三大值
1 m8 d. {& Z! c1 ^; w/ G! ^# V, O2 [第四轮循环得到第四大值
- X4 n: w3 w+ S- D! E总的要进行数组大小减1的词循环
1 ?; J" Z" X. g& w7 @! Q& e
2 u' F6 ~, h0 e8 D3 u, _
6 V( j+ i2 I" Y2 J二、冒泡排序代码实现package cn.mldn;
& ^, \1 t/ ^# z' Q" f- v9 T

import java.util.Arrays;

; `5 g4 ]) @" u" f" |. O
public class BubbleSort {
    public static void main(String[] args) {
' I6 U. ?  X" S2 ]7 M6 ^2 b3 Y2 v% [0 ~        int[] arr = {3,9,-1,10,-2};
, L. T7 d9 u  B1 C        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
% i% b; D2 p2 d        //            //如果前面的数比后面的数大，则交换
% e# e) C, @( ?$ e3 p7 d, ?        //            if (arr > arr[i+1]) {
1 X- r) O* ?% o8 P2 N        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
9 X, [5 Y* \# R9 ]( h4 y% o        //            //如果前面的数比后面的数大，则交换
1 ^# {. Z/ Y7 P  B5 \9 t$ j7 [        //            if (arr > arr[i+1]) {
        //                temp = arr;
- v) c. w4 w  e7 B5 ]        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
        //3、第三糖排序，以此内推
3 z5 Q9 Z1 v" B* j        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
8 i5 N; Z  U2 @, Q, H7 {4 q/ G        //            if (arr > arr[i+1]) {
) E0 `- D- ]+ D$ g        //                temp = arr;
        //                arr = arr[i + 1];
7 r8 _; \# q9 r9 k; N: g; e( v2 \        //                arr[i + 1] = temp;
        //            }
. W) h  {. _! o' \1 g  G) X        //        }
        //4、第四次排序，以此内推
' C5 u8 o' F$ ~- I6 p9 X+ |        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
7 M1 R5 P2 b$ b+ T+ V6 j' L7 q        //            //如果前面的数比后面的数大，则交换
2 {/ d! k) _1 C& M$ w: a1 d        //            if (arr > arr[i+1]) {
        //                temp = arr;
% L& \, W1 x( `5 z        //                arr = arr[i + 1];
9 X  m# Y3 f! B  L" s; g! l8 R        //                arr[i + 1] = temp;
( C8 Y- C+ J  R" [0 F+ ?; |        //            }
        //        }
        int temp = 0;//零时变量，用来将最大的数值排在最后
5 O4 b% ^' O7 K% l" O        for (int i = 0; i < arr.length - 1; i++) {
/ Y& i8 p7 z( Q3 u7 }9 U            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
& S& E) l3 d) P& B( I                temp = arr;
1 T8 b; J/ y8 C) F  \                arr = arr[i + 1];
" @0 N6 w2 ]- {' Z+ w0 e" x                arr[i + 1] = temp;
- Q( T6 o$ K+ W* r- ^            }
' l  g$ ^- M6 K8 `% c4 I8 Q        }
: M/ h5 c0 u/ ^7 i" ?4 }  U+ \
6 y6 d/ p# P: P1 k
        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
1 v/ w% _& r9 S) C* }            if (arr > arr[i+1]) {
                temp = arr;
8 S1 A! _5 y. v% L7 O2 Q, Q7 a7 O: Y2 n                arr = arr[i + 1];
                arr[i + 1] = temp;
, d0 O. S% ^" @/ R6 g            }
9 m' o! O$ f: c7 C! j+ t) _        }
  Q) [1 ]3 z3 U; \! }; l

        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
* M- y+ @' S& X. l                temp = arr;
9 Z1 p* C7 f& i; G- H8 u                arr = arr[i + 1];
- V( e1 U+ k8 H# h/ M5 _                arr[i + 1] = temp;
8 s6 h& c) g0 k, E7 O: l! k$ ^            }
        }
, S& q& l3 U, ~% v# ^
- e# K0 v+ l, U5 {6 x/ l
        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
! {9 Z1 t' E+ H8 a5 H        }
( N& k) T# W3 [4 o# a5 W$ G

        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
7 u4 A: K- n6 Q, B4 w. b( A4 d        //根据上面的观察可以知道了撒，可以再用一套循环解决


7 E! R% l* W, l- D4 b1 Y

        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
& F+ P/ F* [1 A! A+ E* d  C            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
7 \, E/ `% |: w4 b1 n( N+ j' K4 M3 x                if (arr > arr[i+1]) {
4 [0 k4 q9 b& \) d# X! r/ n& g# Z                    temp = arr;
( V9 x4 H4 U5 |2 `1 s1 {                    arr = arr[i + 1];
                    arr[i + 1] = temp;
# F1 Y9 |+ K: [7 o, n6 N0 c                }
            }
        }
3 v2 q0 Z2 |- V) k, X5 D6 i    }
! D9 e' i4 E* r9 O- `6 A% P}
三、冒泡排序的优化

1、思路
, i/ B: G. ]2 d" [/ r  W9 q7 l如果我们发现在某一糖过程中，没有进行一次交换，提前终止
2、代码实现

package cn.mldn;

3 h( m; m1 u+ P2 ]2 u! V# Q
import java.util.Arrays;
* ?5 I* b2 [9 ]
# m* ]: r& O3 i" c2 `
: K8 l- f6 o  o: w" @2 m  Z. Xpublic class BubbleSort {
2 j' `2 p0 M/ j, t2 _6 f  d+ O    public static void main(String[] args) {
2 t! j- f* L: i        int[] arr = {3,9,-1,10,-2};
        //大致过程
% B4 I- }5 H: v& Z+ _2 V6 H! m        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
# ~9 U! s; A, z' G        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
  b! b1 `& A: C        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
5 M+ C1 `- X+ k& U- V        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
( _4 Y; G$ \% Y9 b8 P; @! Q, L0 w        //            //如果前面的数比后面的数大，则交换
  {$ k8 a  V1 \8 R9 D        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
" h) s! Q! E5 T* f6 k        //                arr[i + 1] = temp;
        //            }
2 j5 y! U+ L, \* }        //        }
        //3、第三糖排序，以此内推
) E% b6 _: \! A& V0 r        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
$ m5 g. c, q* l. S" R$ L8 T        //            //如果前面的数比后面的数大，则交换
! \& H. |) F* F( k        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
7 y. `! q1 f" e6 E$ |+ u' L( _0 o        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
7 X5 V9 ^1 a( v' a4 X  x" `: z        //                arr[i + 1] = temp;
        //            }
' A6 M) `2 V, C        //        }
  B! q$ |3 Y; [) o( R0 o        /*int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
/ w+ \/ a/ Q3 o+ Q$ |! }8 H, |            //如果前面的数比后面的数大，则交换
8 Z( u2 ], j2 c5 ~3 L! O- w            if (arr > arr[i+1]) {
7 ]. s% e* e/ h7 F5 i( Z  E                temp = arr;
7 N6 w. u6 x) Y0 s4 |                arr = arr[i + 1];
( Z; j- i( ^9 Z7 R8 \' p# W0 p                arr[i + 1] = temp;
% E) x' r) |) O1 f# ?8 H1 K            }
- Y. |. O) e2 q3 s& S, q        }

2 P$ P1 S5 b3 {# t1 c
6 h0 e5 U- \, Y6 k$ t3 g; F        for (int i = 0; i < arr.length - 1 - 1; i++) {
( o8 @9 |# j5 B, T& E" s            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
" j9 v& i- j5 f                arr[i + 1] = temp;
7 ?8 r# u: f  w$ ~$ H' Q9 B6 `            }
/ t; |1 Z* H4 d$ s$ P" j5 r        }


        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
+ P8 H! g. a3 s: N            //如果前面的数比后面的数大，则交换
. ^9 D1 f$ W+ O6 V: v. H: W4 [1 k            if (arr > arr[i+1]) {
/ d4 Z2 |0 L+ W                temp = arr;
1 Q4 e/ o: G: t. k                arr = arr[i + 1];
                arr[i + 1] = temp;
+ J3 C* Y0 j4 A, b            }
        }


        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
* w9 Q: V+ W' V            //如果前面的数比后面的数大，则交换
2 e' q3 d9 R: _/ H; i# p            if (arr > arr[i+1]) {
                temp = arr;
0 g( Z: Y( k7 H' }                arr = arr[i + 1];
2 f4 f0 Q: R- T                arr[i + 1] = temp;
            }
( A4 h: v/ ]( N) _        }*/


5 d6 W7 N5 K0 b+ ], R  t1 w& }        System.out.println("hello " + Arrays.toString(arr));
$ g- L$ B) C/ M3 Y- x        //------------------------------------------------------------------------------------
* r* `0 B; h; k" u5 |        //根据上面的观察可以知道了撒，可以再用一套循环解决
1 k3 K% u* P/ Z/ w; i. q# q( M


: ]) ~5 s6 i  X4 n  D' B6 \


        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
% n. P6 {- o1 j2 i: w& n        int temp = 0;
9 p& L. p8 Q8 h5 O5 s) ?" o  p

8 R8 e2 n* F* K0 j        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
: y$ I  b8 y/ M            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
                    temp = arr;
/ {0 B4 |+ Q+ [6 V- G  s                    arr = arr[i + 1];
" F  w+ v2 C$ [8 j; O* R8 F  ~                    arr[i + 1] = temp;
0 y8 \4 j' Z' B" [0 Y* h( g% F                }
            }
            //在内部循环的时候进行查询
$ S/ C- K6 f( Z; A            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
            } else {
/ `) n4 D' y- e1 u. v                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
. x+ ?# J3 K* A3 @  A            }
, L. s. U/ i; B. k) o/ g        }

9 B/ Y+ F9 g4 y( C. ~/ I) F
+ N) [) ~$ k+ V  C/ o6 w8 u        System.out.println("world " + Arrays.toString(arr));
    }
" G& W5 \5 [2 {+ j. h' T}
- D. m8 Z% u0 \( B& G/ m* ^四、将上面的代码封装为一个方法
public class BubbleSort {
# ]4 K2 `  b# b    public static void main(String[] args) {
: z# R: U. ~5 ?8 c* @4 G        int[] arr = {3,9,-1,10,-2};


        bubbleSort(arr);
# k7 {% Y9 ?. }7 ^+ Q# O  Q0 o3 t1 p! x        System.out.println("world " + Arrays.toString(arr));
. I) B- X2 u4 P' P# D    }
3 {* p& N: z, a7 a, u6 L8 l8 ]/ e; U

" k% C6 `3 q' _! ~" k. F7 r6 w    public static void bubbleSort(int[] arr) {
) j+ a& e$ R9 x5 R; g        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;
) P8 \! y: M1 f
5 Q9 s) _' U6 I/ j- C+ \' Y' U
        boolean flag = false;
" ?* H* t  M. x) D' u4 Q        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
5 p1 y7 l6 ^9 e/ L5 n: h. t  D                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
' Z6 v+ P3 d: t/ O+ L; {        }
3 P& w  T* J6 x; K    }
$ c+ Q! ^1 h9 M- H" N+ c}
五、测试一下冒泡排序的时间复杂度

1、代码是实现

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

' @4 t1 X% s$ y0 C, Y- s: j+ a
0 C. Y- P0 r9 V! x7 Cpublic class BubbleSort {
: Z# l3 Q! [6 W4 W9 F    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 @4 ]; S9 [& ~5 V6 v) G  r        }
        //2、输出时间
4 P$ A6 f) C0 \9 z- k+ x        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
        String date1Str = simpleDateFormat.format(date1);
7 i! Z  F6 F4 g        System.out.println("排序前的时间" + date1Str);
0 j/ @3 ?$ ~5 D' w# j/ W        bubbleSort(arr);
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
6 n/ M" n; Q- Z2 P5 t- G6 e        System.out.println("排序后的时间" + date2Str);




4 V) W- f3 j8 y% s9 D' y    }


, S1 z; _3 B4 o! o. D0 d    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;
' C: z! Y% t6 b6 F0 b, S

        boolean flag = false;
9 c; O& z4 G$ _! l        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
" f) e6 I  E# L) m# U4 U# k                if (arr > arr[i+1]) {
5 _/ g- V  f* o  ~* V                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
# ]$ a0 H8 V! ^8 p3 I                    arr[i + 1] = temp;
9 I, T" A5 [7 f: \1 _8 F4 g% t                }
            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
0 \; Z" s! h3 u8 ]                break;
' `# }: M$ N5 }/ j( R% P( A  d            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
2 u+ w! S. S& Q6 Q            }
4 ], z) F" b' t' P2 e        }
    }
$ c4 ~, o& F: H% G3 T. K+ A# J3 r6 g}
, `7 @: X: i# G* o& x' e) z: Q
7 b, \0 z# J* U& c! f+ F

2、效果

, c! E( m% Y  ^8 K" u- P

* i% q& }$ `: }) P: k: D* C

4 u7 d  c/ R! ^" _+ `1 q: H! @$ e

470557092

顶。。。。。。