排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
了解冒泡排序是什么！
/ S/ D! e4 U. k! M! K知道冒泡排序的思路
! o) `( N' i5 y* G2 q4 a: |知道实例代码并且练习
- S4 }/ y$ U8 z* T% `  C$ Y" w有收获记得帮忙点个赞，有问题请指出。
* E6 `0 c' j% ?* l4 [5 _一、冒泡排序基本介绍
" H$ W# O% @4 b. I/ Z1 ?6 x1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。
& M" ^& I" R! B5 V% w$ ?2 l

2、冒泡排序的优化思路
因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。
; u7 O) E  S- C3 m: x( Z

3、冒泡排序的图解思路


其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：

% L' o7 y+ \4 _; s$ T% X
第一轮循环得到最大值
! M1 \$ N+ ~. T/ Z' a! s第二轮循环得到第二大值
第三轮循环得到第三大值
第四轮循环得到第四大值
! S, e2 s4 D- d; g总的要进行数组大小减1的词循环
' D/ B) D# u3 h
- O- q& A3 m. i& d7 z$ m
" W  s  }- L* O二、冒泡排序代码实现package cn.mldn;


* `2 p# x; y$ i  u2 G: ]) @import java.util.Arrays;


0 ?  k' l" L/ q7 t# E% f$ |0 y! Lpublic class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
7 N# D6 ^3 ?# [1 m) h        //大致过程
3 J) B  O7 A2 W: u' p( D) P, k& z        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
; n6 o1 @/ K! C        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
4 f" J5 H/ u: y* M1 u        //                arr[i + 1] = temp;
        //            }
6 Z1 U1 t( L' y6 Z        //        }
9 T# d: U' r; u, K        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
% c3 M7 v# U0 d+ l1 q# X        //                temp = arr;
2 D# k* m* H% l1 f. R7 e* }        //                arr = arr[i + 1];
6 t( a, ^3 u! S6 p/ R; d3 e        //                arr[i + 1] = temp;
: b; r9 V1 j4 I; X: o        //            }
        //        }
        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
3 k  W0 r! z( m" [; q0 s9 g# b        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
5 B9 e8 j9 c0 w. l        //                temp = arr;
        //                arr = arr[i + 1];
! C/ d/ E& f# j; z        //                arr[i + 1] = temp;
/ q0 `5 l& r# `. U& K9 ?        //            }
% j$ r, u& E) L9 k+ t* z        //        }
" X# [- m% {! K5 z; ]) _        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
3 D( Z, e' M4 P; J* ^- r) Q( o8 G        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
. `8 w7 F: O8 e) r' q$ S6 g. _        //                arr[i + 1] = temp;
8 o% e4 i) T7 j' x        //            }
        //        }
        int temp = 0;//零时变量，用来将最大的数值排在最后
, f  y; Q2 J. n5 x/ K- E+ B! Y& u        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
  M9 N# R- O# |" z3 C# D                temp = arr;
9 R8 S' c- @! X4 z  P4 l: {                arr = arr[i + 1];
2 j: L7 T. P+ T) [4 Z5 C                arr[i + 1] = temp;
& }( ~. Y# W5 o7 C. g+ h            }
        }

6 c$ |# V2 z! F: z2 k1 h
        for (int i = 0; i < arr.length - 1 - 1; i++) {
8 @7 w$ ], K& ]            //如果前面的数比后面的数大，则交换
  N; U- D. p- y6 z            if (arr > arr[i+1]) {
3 j8 z5 ]% S6 B: O0 v% G                temp = arr;
6 j0 O( v1 O; T                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
# ]/ n& e$ h2 r
. m6 m. Q( l2 H( _$ S2 P1 Q5 g) E" x6 @
        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
2 ]. z/ {7 s! O            //如果前面的数比后面的数大，则交换
0 K1 Q) u* n) x" X            if (arr > arr[i+1]) {
  m% P+ f& y8 n& u                temp = arr;
                arr = arr[i + 1];
# E+ U8 }  ]; [5 r# x                arr[i + 1] = temp;
            }
# x' ]" X: C  v, ~2 y        }
5 k; p2 x; S9 Q) Z% l* ]
) x4 [0 B* Q& m* Q
/ Z( R% i, L: O1 g% x# x) L( z        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;
            }
" j: J! D( _5 ~9 ~        }


        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
: L5 N- T2 ]: D4 ]* C


" _- y) y* P3 e# e5 {, t; X( v
0 P: `) u1 L% K/ j/ h        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
  `6 o! s( L) q4 R5 w& F' Z7 H        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
                    temp = arr;
                    arr = arr[i + 1];
5 g0 e: V3 X7 n  H: q, T) l                    arr[i + 1] = temp;
/ K* `) V4 J$ [5 L8 m. c/ _8 K) o                }
+ w3 B! h( b. k3 r, i' n& C            }
        }
7 Z1 O! a- L& h# W. b/ }    }
}
三、冒泡排序的优化

1、思路
如果我们发现在某一糖过程中，没有进行一次交换，提前终止
. k7 K% D' \* t3 Y& v( @2、代码实现

package cn.mldn;
' p+ D6 x" N8 ]+ W( Y

import java.util.Arrays;
5 o% d; I, g$ g# H& ~5 s- B
2 \5 }2 O% H/ l1 u& _5 x4 u- |
public class BubbleSort {
+ {) U9 z8 Q6 x* x' |" x6 p+ S6 e    public static void main(String[] args) {
! X* L9 E+ j5 S, B4 e1 X) G4 [        int[] arr = {3,9,-1,10,-2};
) x: j% b7 e6 E; d6 R        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
/ ^% ]7 g+ k8 Q# i% W8 G        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
$ R2 ^: y0 d7 p. [: ^* e        //            if (arr > arr[i+1]) {
        //                temp = arr;
' p: n6 f" n* _) J( `! c) e        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
9 u3 q* _+ ]( o8 @$ Y4 Z        //            }
        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
4 ?' ~6 A; _1 k        //            if (arr > arr[i+1]) {
% V6 Q1 G# `1 V3 r5 G        //                temp = arr;
: v; g! S* t, r- \; k        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
) s$ L9 U8 t9 Z        //        }
9 o9 R$ }7 M- r* f5 P        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
. L4 r8 \+ D) p" X6 O  W# Q, Y) v+ P        //            //如果前面的数比后面的数大，则交换
2 [( G1 X. q/ C  K7 E) |        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
& u% k/ f% j9 a6 B/ I        //        }
        //4、第四次排序，以此内推
$ _  z9 l  B# j5 l        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
6 }; `- W& y0 E* l2 ~" h- [8 y, x& ^        //                temp = arr;
3 C3 K/ C1 B/ A  F        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
1 c* p* [; ~- w1 ?' ^  `7 c        //        }
+ ^  P: h$ r* E% e& j$ o! F, X, }        /*int temp = 0;//零时变量，用来将最大的数值排在最后
! @" Y4 P& q( }( m/ ]% x) B        for (int i = 0; i < arr.length - 1; i++) {
) Z4 P3 [' n; x% b1 w* r1 n  \            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
5 d! {& s: L* w7 s                temp = arr;
6 k( R! C* [, A  a* R                arr = arr[i + 1];
9 _) s% G* L% B2 b( j                arr[i + 1] = temp;
            }
        }
  R: j/ J" \1 \* R" G7 i9 F2 H
* @4 R, h9 W+ d' t. `: w
& o( S$ o# U& V  u: v: ?  Z( s3 j        for (int i = 0; i < arr.length - 1 - 1; i++) {
5 x$ X" {, q/ v/ B( l            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
& N8 j7 f: n1 r$ |- J, N- T                arr[i + 1] = temp;
            }
% W" V# i" E4 m& ?( U7 i1 f        }
% r8 w# x) w* g' _+ H) X3 Z2 R
6 Y2 Y- x3 a9 W% ^4 P
- h$ e: t  q- o        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
1 G! n, h: ~1 ]. `5 P* B            //如果前面的数比后面的数大，则交换
5 Q# S1 T7 @/ ?& ?, B- h1 W            if (arr > arr[i+1]) {
                temp = arr;
% l5 F6 R- {  `, M, V                arr = arr[i + 1];
                arr[i + 1] = temp;
# I# R7 C2 I% J" W8 A5 A            }
        }


        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
7 W$ A2 ]1 Q, s& S            //如果前面的数比后面的数大，则交换
/ ]# _% X. S3 k3 ^& P            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
4 P% O6 d, F( R                arr[i + 1] = temp;
            }
        }*/
- b# k7 G0 R; D* r* Q1 I. P. z
& c0 v7 ^7 U( V' b" {8 P5 N% R
* N; K$ w! Y: F6 \# h        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决

: P. u! f4 ?. I# H; k


( K# |2 `" H+ ?0 M
1 B& q6 O8 O0 m! n- H4 O. j
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
6 [! {) B9 e4 J        int temp = 0;
  I$ m2 i/ x* V' G0 @9 x% y
) L1 s: c4 S: F: R
        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
' o( A3 {  L# [- I. q            for (int i = 0; i < arr.length - 1 - j; i++) {
+ m; C  U$ Q' x) l; A                //如果前面的数比后面的数大，则交换
2 {' _" v. [' @$ Z2 @8 z                if (arr > arr[i+1]) {
# c6 ]) @9 }: ?+ n2 I8 K$ W; V# t                    flag = true;//在这里把flag值为true
                    temp = arr;
$ n3 X4 i) y4 i: A: r" H% ~                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
9 R$ r0 H1 X  E1 a( T: p& C            }
0 d5 y* ^+ I" [  ?            //在内部循环的时候进行查询
" Z5 S" T2 |( {. _) I2 M1 y            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
6 v4 x- }7 ?. B: N; A3 k                break;
            } else {
# c2 a8 h7 I( }6 D+ t) W                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
: \: |4 t5 ^3 Q) Q* v' G  d            }
7 A% i, V$ g/ m+ I        }
7 j0 j+ C% n$ r& q/ O6 h( N

        System.out.println("world " + Arrays.toString(arr));
4 H+ E6 \( o! U    }
# M2 A* e% p1 [' x}
四、将上面的代码封装为一个方法
5 D. D- z" U( hpublic class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};


        bubbleSort(arr);
        System.out.println("world " + Arrays.toString(arr));
9 w: }1 i3 m8 v* ?& |    }


0 E& j! \1 ~. C' a    public static void bubbleSort(int[] arr) {
# d; x+ E% I3 [& T9 U  I7 F7 ~        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
/ [) j# U8 b) B( s1 B; b/ u        int temp = 0;


+ k+ R1 u% y5 [" A" H        boolean flag = false;
+ H  `* L) D# W        for (int j = 0; j < arr.length - 1; j++) {
0 |+ a* I$ U, A5 ]) m" u% U4 w            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
6 @& k" o$ b  I                    flag = true;//在这里把flag值为true
. z- a  n) m0 w: l                    temp = arr;
# O$ X- f' a6 |/ n% z5 i5 @2 _) t' e                    arr = arr[i + 1];
/ P( g) m: y- j9 U* N2 W                    arr[i + 1] = temp;
                }
            }
6 C5 B: z1 j' p( H( P! k. R8 X6 X            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
; ^# k2 C' J3 }) m7 x. |3 {1 U                break;
0 U) @0 T. N' ~' g. |: ^8 W            } else {
1 R$ l+ S. k0 R$ E1 @                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
$ o( Q/ k1 k2 Y, `  x        }
    }
}
2 }- \5 N4 ^3 g2 X8 r4 i9 a五、测试一下冒泡排序的时间复杂度

1、代码是实现

import java.text.SimpleDateFormat;
import java.util.Arrays;
: ~9 _% b3 S( s$ V! ximport java.util.Date;

" @& Z3 J7 H1 R( d9 B) s
. G. `# ~: {  k( Epublic class BubbleSort {
+ R$ C" f6 i! |% d7 `8 Y( R3 w    public static void main(String[] args) {
3 K! f, a" \$ s& d% u. }$ @        //1、创建80000个数据来测试一下我们的性能
        int[] arr = new int[80000];
) @, b' v+ e2 R  ?5 c        for (int i = 0; i < 80000; i++) {
            arr = (int)(Math.random()*80000);//生成0到80000的数
4 a# |6 t3 n" ?% G1 w( M6 j        }
2 ?6 Z  e, o5 W        //2、输出时间
        Date date1 = new Date();
. ]* E5 o- U5 m2 x2 I        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间" + date1Str);
* d$ B5 ~4 U3 s        bubbleSort(arr);
4 H  Q$ ?4 N3 D% f2 C$ R2 w7 v        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
& T- I% F  h5 B' s0 Z        System.out.println("排序后的时间" + date2Str);
, ^# F# D! o8 L! J


' a# a0 N. Q( y& G/ K  M
    }
- L& X" a. q, h2 q$ ^4 i
' {  S7 }/ x; c8 Z9 U
    public static void bubbleSort(int[] arr) {
( U$ M4 X- y6 N! ]        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;

" z! @# V# h& _& @
        boolean flag = false;
0 w+ F7 H  k% _2 I% W, S) `+ X' Y        for (int j = 0; j < arr.length - 1; j++) {
* s8 M% k$ r# V  {3 q' Z+ L# K2 ~            for (int i = 0; i < arr.length - 1 - j; i++) {
- a4 l  T: \. P, i  P; Z  T                //如果前面的数比后面的数大，则交换
% _0 l- b: }. Z9 Z5 T3 m4 q' n$ R% V                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
7 P0 J4 u4 ^  I% a' }3 M* ^( c                    temp = arr;
% V. ~  i2 P6 l                    arr = arr[i + 1];
                    arr[i + 1] = temp;
% u- [0 \4 D  c. |* w$ Z7 t                }
  Q2 m3 J) p) @: D. V. B. d9 {            }
* ~2 X- P2 G. S1 @! t" y0 s            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
( D# |- h+ _/ Z) v+ y; l, i            } else {
* A8 o; o5 b6 B% ?; H& e2 t                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
8 _9 S" p. L, a" r4 f            }
7 j$ @# |2 f- H) o* G        }
    }
& e1 u# \( s4 S9 N) {/ {$ a: b/ H}

! ?/ ^8 ~/ \$ B' A) O

6 ^: n! C+ o; A2、效果


8 H1 T1 [6 E& _7 j1 a" t( Y

" y! \; k3 j7 h

470557092

顶。。。。。。
8 Y8 X  Q# E& U