排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
! S7 \+ O- K) Y+ W+ z" }了解冒泡排序是什么！
9 K1 c7 K: w- x4 {- D知道冒泡排序的思路
知道实例代码并且练习
有收获记得帮忙点个赞，有问题请指出。
一、冒泡排序基本介绍
1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。
7 c( P  Q5 g4 {9 m

2、冒泡排序的优化思路
因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。
+ O5 d5 s- f2 p' h8 g+ s  d
$ ], p& s- a. H# a2 C" ?5 `$ M+ P
% D; f  t5 {% V/ P3、冒泡排序的图解思路
" P6 k; y" p7 Z% A# \% B* M
6 D$ d+ E8 @( X% {+ @
$ i- `% p* G+ Y/ ?* F: d" [7 ~; }其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：


第一轮循环得到最大值
第二轮循环得到第二大值
0 G, q* ]. V8 K* x( _第三轮循环得到第三大值
第四轮循环得到第四大值
总的要进行数组大小减1的词循环

- X" O: b2 Z- ]2 ]) o8 G
' Z/ H* r9 o4 E% k" x: h3 b二、冒泡排序代码实现package cn.mldn;


import java.util.Arrays;
( L' e0 \6 W* {0 {; T" X; K; F# B

' i( s8 R% M) [7 q- O- Rpublic class BubbleSort {
    public static void main(String[] args) {
& ?. @& j0 q' d        int[] arr = {3,9,-1,10,-2};
        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
: @6 U0 ]' `) Y5 {3 o        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
3 T$ z" j2 f8 G# O        //            }
        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
/ r) [7 x# g9 [3 Y        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
. C/ F" A6 _) Z7 U: {+ N9 a) q        //            //如果前面的数比后面的数大，则交换
; F1 f. F9 ^  M* v) {        //            if (arr > arr[i+1]) {
# Y' w& U- ?4 F4 _( w& @/ o6 @5 [        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
/ \0 A" E+ Q) ?3 X; C( P5 n1 o        //            }
: n0 v: X+ y" X9 ~2 X; g        //        }
        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
( E6 Y" c# z# |# l( o- v        //            if (arr > arr[i+1]) {
        //                temp = arr;
; [3 R# ~' E# P' ?! `/ o, s- p0 ]! v        //                arr = arr[i + 1];
# f# X; p& S, _2 p0 A% N7 l        //                arr[i + 1] = temp;
) s6 x& `/ d  G        //            }
  [) K9 ]$ A( i" _9 m  {        //        }
: j8 e8 v. I, L1 a5 I" ^( r+ ~, ]4 r        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
( x1 O9 _% k2 q5 I        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
, W  P0 y- P* l& ^0 d9 p; q$ z        //                arr = arr[i + 1];
2 k4 c0 t$ r. o5 Y" U; t        //                arr[i + 1] = temp;
, M) Q7 B- l7 c" ~( p& X        //            }
. l( _. D. m% ~' X, Z- n% n5 p        //        }
$ f$ S0 ~% y; ~! C5 a        int temp = 0;//零时变量，用来将最大的数值排在最后
7 E& b: Q: M2 s+ C6 J- a        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
8 {* H0 k2 B% ?/ b3 m" V) i/ L# ^                temp = arr;
1 S. r$ N9 b0 u- i. t% ~( c# J  n% }                arr = arr[i + 1];
                arr[i + 1] = temp;
* K% P& I) V$ |# ~# ~+ \6 `' ^            }
6 W' `* b, d8 }6 R. |        }


6 y6 }' H$ g4 N; u7 _4 s        for (int i = 0; i < arr.length - 1 - 1; i++) {
% J8 h" [# X* O4 z            //如果前面的数比后面的数大，则交换
2 \2 Z: C7 z# ^7 w$ }2 H+ i' m5 a: ^            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
9 F$ F6 ~7 \$ ^2 f            }
4 |4 d8 p2 u; S7 n1 l2 C        }

: t. l( k4 O( [
5 s: g$ F3 x' H  L% u        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
, @6 b3 F* @% S                temp = arr;
" A( \; ^0 O+ i# E; ^. Y% [4 z) a                arr = arr[i + 1];
7 N5 Q2 d0 M7 Z9 X$ B8 t, u& O                arr[i + 1] = temp;
0 W7 e4 ~6 b% e; D8 |7 C            }
( q0 e6 H) \8 B# m. L: H8 J  H3 ~        }
' P, P* M9 W, h/ @3 o  z3 G
0 {- E8 q0 L' Q1 ]1 m/ o2 t
        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
8 U0 ~+ t# K' h% n+ e) ]% W. \7 p            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
6 h4 v5 a  m1 Y8 D/ {6 q6 ]! B- Z6 r                temp = arr;
                arr = arr[i + 1];
0 x  x& W* ]" v, e4 B. Y  L                arr[i + 1] = temp;
            }
        }
# D! t: r7 a6 p% o) O

        System.out.println("hello " + Arrays.toString(arr));
5 F/ n6 |0 U7 h2 |  o2 O        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
/ g1 ~4 J; L. W& q; K
$ v% K; r0 h( w! f5 ]/ f

! e" O7 V4 s. }2 n* L  y
4 [; X6 s; x1 o) e1 T6 k7 y. J        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
1 i, C5 ]2 ]7 V1 w6 N; W                //如果前面的数比后面的数大，则交换
% i! m1 u4 p2 ^1 `% M                if (arr > arr[i+1]) {
9 \1 s8 e; i& r" Z6 f8 z1 s                    temp = arr;
- e4 T1 G* @) L5 _. ^                    arr = arr[i + 1];
+ G0 I# X, n- d; U& V/ ]% W                    arr[i + 1] = temp;
! b) h6 @* d0 ^1 B+ }$ B                }
! ]+ ^8 b% o# G( q4 ^            }
        }
3 h* A( ^; i+ c2 [, `    }
. C' U1 g4 m% s; r% x: ~/ S}
& @8 o' O# l- N2 P三、冒泡排序的优化

1、思路
如果我们发现在某一糖过程中，没有进行一次交换，提前终止
  j  K) F3 s/ v, v2、代码实现

package cn.mldn;
3 }1 c, c- \/ e! K4 s2 W  l

import java.util.Arrays;
2 i6 _* g1 D: q8 ~! g& R8 Y7 j3 Y
% E* Y3 L) x8 B7 W5 G: \: f1 T7 ~
& e: s4 t- l! L% j  ^7 X1 d6 Epublic class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
        //大致过程
& G/ x8 u2 q! |4 x+ [        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
+ T2 ?% Q. z2 N1 r# E# }% \9 s        //            if (arr > arr[i+1]) {
        //                temp = arr;
/ e" c4 }  w, D+ U4 L        //                arr = arr[i + 1];
) C7 b% o: X. @; g  m        //                arr[i + 1] = temp;
" ^  r- v5 Y! N        //            }
9 \5 P! D1 k7 p( ?8 ?5 \" t        //        }
7 c7 q: T* ]3 W9 g. d        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
4 y# X& y6 \& N        //                arr[i + 1] = temp;
; S3 Z6 e$ z# U$ v        //            }
        //        }
        //3、第三糖排序，以此内推
0 A' \' d6 h$ [( C. y        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
+ t2 s$ e" w' l  x+ w+ T        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
- l: Z, _8 B0 T; B2 ~! G        //                arr = arr[i + 1];
! t- H: C; H& ^* ^* J" L* q# V2 ~        //                arr[i + 1] = temp;
        //            }
        //        }
        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
+ M5 e8 K3 e3 `* C5 d. {5 P1 I        //            //如果前面的数比后面的数大，则交换
6 y/ Q3 _( }/ a        //            if (arr > arr[i+1]) {
        //                temp = arr;
8 P* z0 G* n' b/ J; r, o+ J9 M# `6 U        //                arr = arr[i + 1];
0 h, D& z9 N  T2 B# c- d        //                arr[i + 1] = temp;
2 ~6 C$ k8 M4 p# Z4 ?. @        //            }
: [' p. ]: x0 K! N        //        }
7 Z; {2 Q* V& T  h3 R8 Y/ k0 _        /*int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
3 x: I0 Q+ G1 p6 |            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
$ j  b3 u7 u9 |6 |+ `+ V                temp = arr;
                arr = arr[i + 1];
  g% h% j2 ^# w4 {$ f' E2 o                arr[i + 1] = temp;
1 F+ i( _5 A9 e' m' u9 c            }
% h- l/ X) B! V! Q        }

  a) n! A# r2 A2 b: v" x
        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
% Z9 Z  f& c+ x# d; `            if (arr > arr[i+1]) {
                temp = arr;
7 Q; e; R8 d2 q# Q8 h                arr = arr[i + 1];
* I& Q3 I$ k3 G( h3 l                arr[i + 1] = temp;
            }
        }


( @$ ^4 T& c( v- T9 v0 L        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
9 x. ]0 d6 @* ]6 h            //如果前面的数比后面的数大，则交换
% L! g. w! ^3 i6 \7 [            if (arr > arr[i+1]) {
0 X+ E( f1 G- W& E1 A1 B                temp = arr;
                arr = arr[i + 1];
, a2 p3 \' Q7 q/ }' u                arr[i + 1] = temp;
            }
        }


        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
0 g' Z# N9 \$ a                temp = arr;
2 r  W! B  w0 H: C  a2 H& J# K                arr = arr[i + 1];
/ L( V: q$ a  N& ?! M                arr[i + 1] = temp;
8 D9 `" T+ A/ B1 c+ c- q            }
6 H' U+ P# {) g4 x5 l5 E        }*/
4 P% w/ C" P' o! B

        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
& L! w0 \% Z; K2 B2 Y/ j* M        //根据上面的观察可以知道了撒，可以再用一套循环解决






        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
8 T' y1 R. w; a; \1 K& v+ G+ @        int temp = 0;
% E, M4 u7 _# S: {
7 H) }) D3 i4 }1 W# j1 Y
$ c1 ?& ]" u# z6 j: k8 C        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
9 C9 H- X# a+ u& B/ a                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
" {3 v9 ~, L- L6 k1 ~- q                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
" o) v! P9 s9 Y# M3 C6 ^* F( ]                }
: ~% }! d2 H7 v- Y! l% n            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
) {+ J' |) q2 k8 n            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
* p9 L5 ^# t+ a            }
        }
: f$ Y9 J5 H+ k, {; C; n
9 r9 l5 Y9 v( J- v0 f
% K/ W% {/ H7 y% |5 F( ]# O        System.out.println("world " + Arrays.toString(arr));
    }
}
四、将上面的代码封装为一个方法
1 @0 |0 ~6 a6 Opublic class BubbleSort {
6 g; F: x7 J: ^; H    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};

% X- D$ C* h6 v8 k2 x. g
% m% |$ l. {/ ~9 \        bubbleSort(arr);
        System.out.println("world " + Arrays.toString(arr));
  q0 Q/ B) t' p, o    }

) S4 b  N9 I. c7 U
    public static void bubbleSort(int[] arr) {
; h, h/ D: ^- a; x        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
6 Z; K) Q' v: p( l1 f) c$ e. ]        int temp = 0;

) C) p& P7 j/ d9 G
        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
: b9 l4 r& F  }$ e- F2 H1 r. J9 s            for (int i = 0; i < arr.length - 1 - j; i++) {
* i! C: l: B$ m4 m) E2 ^4 m/ C                //如果前面的数比后面的数大，则交换
- o2 w( v$ P' y2 y* |9 v0 L% @5 N                if (arr > arr[i+1]) {
0 f3 W4 C, |0 J# G) h  F2 a                    flag = true;//在这里把flag值为true
                    temp = arr;
. S- ~# U$ ?# q9 i. f9 M$ w) ?                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
) k8 Z6 ?! n! B  k' g            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
/ N8 G1 F' s1 ]4 [6 A/ M  Q            }
        }
    }
}
五、测试一下冒泡排序的时间复杂度

1、代码是实现

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


public class BubbleSort {
) s+ b4 t$ ~0 T    public static void main(String[] args) {
6 Y7 P$ u  u. R8 _, q/ z4 p        //1、创建80000个数据来测试一下我们的性能
" }" Z5 ]4 G  j6 }( f9 ?2 {3 M        int[] arr = new int[80000];
# J2 Q! ?. h8 Y; W' S        for (int i = 0; i < 80000; i++) {
            arr = (int)(Math.random()*80000);//生成0到80000的数
( Z2 r' e6 l, l- @( Q/ [' b        }
        //2、输出时间
        Date date1 = new Date();
  @+ t6 I) w7 i        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
        String date1Str = simpleDateFormat.format(date1);
  o5 Z# F0 s- a& ]+ @& H        System.out.println("排序前的时间" + date1Str);
/ N8 v: A8 r. S1 f% }1 s        bubbleSort(arr);
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
8 b+ y! x" O( `6 o" L        System.out.println("排序后的时间" + date2Str);




. J6 _3 G8 U+ N" T0 Q    }
( M8 _: e- n, u# Q1 i- L
9 c! j4 A& @& L0 k; [# R! c- j" U
    public static void bubbleSort(int[] arr) {
; [4 q3 Y9 Y; S$ L5 f0 A: N. y/ W        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
! `! G5 @2 h, W$ h' h# Z0 _        int temp = 0;


        boolean flag = false;
3 x7 g" P) Z% F2 p' C. ~        for (int j = 0; j < arr.length - 1; j++) {
/ {4 h- @% s/ G; Q% v  q            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
* z+ ^( \2 N2 w+ v1 ?                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
                    temp = arr;
; O7 W8 n1 v! Z5 n8 \                    arr = arr[i + 1];
                    arr[i + 1] = temp;
8 t2 u( y9 w5 x/ u                }
            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
: K0 A. o2 r7 ~  T- c2 u- Q! Q                break;
/ o4 Z$ O# j9 X% G            } else {
9 {. B" H: J3 F+ l, a8 M) D) N, E                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
    }
) C9 l5 n  Q) T; V$ P4 ]+ k}
7 l) ^8 i, E! z' d0 D
& i$ A6 R3 ?0 ?6 [. |

2、效果


: ^& t9 X, ~1 T, \9 ?7 b* ~
; F5 n$ @. O3 b/ s. }

470557092

顶。。。。。。
# O9 ]' }. a* J& Q3 P! h