排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
! n3 P+ c  M1 @4 Q* [* ?* L4 e了解冒泡排序是什么！
, O& ^. k2 u; b  y4 ?/ C  X知道冒泡排序的思路
7 T7 _( o! Z& `4 f知道实例代码并且练习
1 P4 l5 E0 y0 i! V6 e( C/ v有收获记得帮忙点个赞，有问题请指出。
, s3 a6 d! s. y" I& I+ n) a一、冒泡排序基本介绍
8 U0 m, ~6 t( I0 F# ^" ?1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。
, W5 @& P* J+ h# q5 d9 l) v2 q

/ d# G4 u$ N/ u2、冒泡排序的优化思路
9 N  A' M. o" K: _因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。
3 n  z0 B! B% r# A0 V" _5 q$ \
/ p$ u0 J2 t5 q3 o
3、冒泡排序的图解思路
9 o. c! a5 c$ A2 Y( X
3 ~" ~" ]% |% M* Z2 h1 |
" P* ?2 S. X2 I% S" G其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：
- [; L1 O# r8 t( R
! v0 R5 C: ~4 J- E& A. a+ L
" @/ [% E4 w0 b) m, s! Q第一轮循环得到最大值
第二轮循环得到第二大值
第三轮循环得到第三大值
第四轮循环得到第四大值
0 N. J; L* ~/ o* W" `" W! a总的要进行数组大小减1的词循环

1 S$ E- G5 P- M$ P8 a- K
二、冒泡排序代码实现package cn.mldn;

; J. U& u, }1 ^5 U. g
import java.util.Arrays;
5 w/ n/ S" m$ a& L# U, o: C

) D! d& {+ x& \- |* c4 f# Bpublic class BubbleSort {
) h& [; b$ E8 [9 H    public static void main(String[] args) {
8 Z: h; i3 x, P) A6 z        int[] arr = {3,9,-1,10,-2};
) J# |7 ^4 d' t. F        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
, |! _; e, F: p0 }9 X        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
8 M" k. Z# h) L6 a, G& W# }        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
  j0 n7 y+ ?! C3 f        //                arr[i + 1] = temp;
0 G: K' I/ o, m        //            }
        //        }
8 ?3 Z, \  X2 ]- R( _+ J) E4 a        //2、第二糖就是把倒数第二大的排到倒数第二位
9 u3 z" Z$ Z+ i# H5 u; J. S# n        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
" Z1 b  \* M1 }* J5 n  l! {/ I        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
% l/ E9 y- Y. v2 D3 n7 U  s        //            }
        //        }
8 {' E, E0 A$ {5 H        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
# ]# K: C7 ^! ]        //            //如果前面的数比后面的数大，则交换
- M) f, e: d0 ]& k1 d# {& ~. }        //            if (arr > arr[i+1]) {
2 f6 A5 `. J  y' Z7 Q2 t        //                temp = arr;
9 w* f0 r3 ]3 x        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
4 ^2 A5 m. ?8 X* p( t+ O1 ^5 W        //            }
        //        }
1 y& J0 s' I! t& ?        //4、第四次排序，以此内推
' ?& ]* b* o# F        //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;
        //            }
* k$ F6 q: p4 H' l        //        }
        int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
, ^- X. ~9 q$ [  [1 m7 \: t            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
: L, C( l' M' G  B- k1 _                arr = arr[i + 1];
& e, E- I$ w' T4 v8 T. j                arr[i + 1] = temp;
            }
        }

: D) N! r# c- @6 {
# W! x+ Q6 }* Q! q/ X1 T8 K        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
0 ], r1 l8 A: j* f7 t  k# k            if (arr > arr[i+1]) {
' u. H6 d; g. y  h2 h                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
( I' M: c5 `" j6 ~6 Z/ T            }
        }
! ~3 ~3 G$ ^; v
; u, K$ P: m6 y) ^. w
        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
( m5 Q  J+ k, V            //如果前面的数比后面的数大，则交换
5 z2 ?& Q6 h5 f. P6 D- ~  F2 l            if (arr > arr[i+1]) {
% j: O: a- H  _$ R5 V8 z& e                temp = arr;
1 ~; l7 x% M! H                arr = arr[i + 1];
                arr[i + 1] = temp;
( S. [+ T, e4 v# o5 x2 X, y% C- E3 r            }
        }
0 l# t$ P- l/ k

  y! R, N" q1 P6 {: p  \        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
; l5 |* d: b% \- C                arr[i + 1] = temp;
            }
        }
4 v) Y8 X8 q2 f/ L+ R
8 L; h/ I  M" k) |0 d; L. L
        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
/ g3 p5 x: v; V8 P' n" d        //根据上面的观察可以知道了撒，可以再用一套循环解决

5 [' \( \, |* g# [6 [

; ?3 Y9 h7 f8 _
. P9 s2 k4 z5 Q7 P6 T        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
' {0 m3 u( ?9 O. |5 e            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
7 u7 G7 |% ]0 ^1 h0 g                if (arr > arr[i+1]) {
  s+ E6 ~% j: l* u" Q                    temp = arr;
                    arr = arr[i + 1];
# X+ a' G  D8 d( H6 N3 L" a                    arr[i + 1] = temp;
3 f* s/ k3 ^6 Y) @1 ]                }
; t; C3 Q+ b0 I  z# [+ E            }
% e4 [. N$ t1 i; a* M        }
    }
}
% @7 R. W+ C; v. g三、冒泡排序的优化

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

package cn.mldn;
. |' k& X$ r" u( o; Y" T7 A
# g+ r- c% C( J( k: `/ Z
4 W8 u3 U* R5 N9 W8 a; \import java.util.Arrays;

& z( B* \2 b5 n! T
: u& [9 z( h! J* O2 lpublic class BubbleSort {
$ F6 l) D$ j3 W( |6 K    public static void main(String[] args) {
& }- k8 ^6 S: ]4 Y$ q9 V        int[] arr = {3,9,-1,10,-2};
" ~4 X& e2 Z+ a$ I) y        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
9 J- m; Q- M( J) _% |8 U" I% ~        //            //如果前面的数比后面的数大，则交换
& w8 l. d9 f8 T- P1 t2 X( i        //            if (arr > arr[i+1]) {
  F. m5 y; O- I4 b* T3 m/ |        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
6 |, N/ E( s7 M: _: {- o, v- m        //            }
# p7 D: X6 l4 O$ C  f        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
5 a( h0 d) ?! v        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
, }# q1 w5 [" ?" A, ?$ N/ j7 B        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
/ c7 L# s6 P, d        //                temp = arr;
; g) k( G: d5 F6 s        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
6 S3 r" p  q2 N+ t* X& S* O        //            }
& k  [9 \; U/ y# x4 Z# ]        //        }
        //3、第三糖排序，以此内推
: Z1 L2 ?& y$ ]        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
- N% _+ {/ V! ~4 F/ j1 f  [        //        }
) P' L, F* K, t; i$ e3 _/ F( W        //4、第四次排序，以此内推
# o; j( Q: Q# ]! B5 e( y        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
5 F7 {; T: {5 x+ S        //                arr[i + 1] = temp;
        //            }
        //        }
        /*int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
+ m% m0 ]: C( X( m8 a            if (arr > arr[i+1]) {
! f  z2 q4 o9 l3 Z$ X& ^                temp = arr;
2 f& v' N- D  S( b8 \, h- e                arr = arr[i + 1];
                arr[i + 1] = temp;
6 G3 b( t7 n/ D# U            }
        }
. q! H# b0 L+ K& T8 `( ^! N: I
7 o) Z$ a" e( g4 B3 M
( w% f" W  ~* |9 f5 _7 F        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
- ~5 d0 s/ ?# g& O, F8 L! i) k                arr = arr[i + 1];
" E1 p7 H. R+ M6 V( Z6 N                arr[i + 1] = temp;
: ^% Y6 K+ T2 A  m4 U- _! S            }
        }

0 z4 j& n5 i4 M- y
2 u0 A0 }7 Y2 ^0 R        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
, d$ W* @# e( r6 M" }7 A            if (arr > arr[i+1]) {
                temp = arr;
" d2 a( I/ }. J, h3 u, H                arr = arr[i + 1];
                arr[i + 1] = temp;
$ r5 i2 S7 r7 a+ F3 m            }
5 _, j( b/ ]! H7 M( x. s! [5 m        }


        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;
            }
        }*/
5 T) }, _5 w; g1 S/ x

3 n# |4 r$ ~4 D. L0 @; I        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
% m0 t' H  V) i7 T


) a- L: ?6 i* {- D4 j( q$ C, W


* K% ]# O5 m1 {1 M        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
4 b8 H  n7 x; M        int temp = 0;
6 M, O3 Y% h% g) k& K

7 [, a1 Z! G4 u. u/ K2 c        boolean flag = false;
3 }3 n$ \! z- l" d" I        for (int j = 0; j < arr.length - 1; j++) {
; w/ H' S% x1 B+ P            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
8 \9 Y& a$ J, R# P8 A                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
4 g3 X4 u7 U0 d* _0 ], ]6 c                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
& Y7 H, G0 u: U  O9 h/ n                }
8 b2 u- i8 L4 B, }+ ~            }
$ U4 u% [7 \3 I/ Z  W            //在内部循环的时候进行查询
# G' X; L" J) F( S) t, h( \  V& ~            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
$ ?# l) h7 P; J5 R                break;
+ y* e8 _- s- G, K$ h  B            } else {
; J- _9 Y8 \8 D5 L# m4 Y4 [. U                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
: `# p* o* ]& L8 K. ?) s/ P- |( J            }
& S8 b" y; B: w* H' p2 m1 ^% I        }

* |  R  S/ j$ e5 s
! Z$ E8 y% z6 e9 ]& E        System.out.println("world " + Arrays.toString(arr));
% ]! {% y8 |$ R9 I* T    }
5 d/ n; i, P8 {" f  l! k. }# M* p7 _}
6 l  P) M% F# W* F+ i四、将上面的代码封装为一个方法
public class BubbleSort {
    public static void main(String[] args) {
% o3 f8 u3 J' a0 k* {        int[] arr = {3,9,-1,10,-2};
) u5 Z4 x- d! q. }
* [( H+ ]; S+ j/ F# v9 _
        bubbleSort(arr);
0 O+ T+ z  T( u& t* @! C        System.out.println("world " + Arrays.toString(arr));
    }
; J/ n' g+ j# ^6 W  k6 M1 _

, l& a  Q# ^5 z' O    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
. `9 M% V7 P7 \8 d! }0 X        int temp = 0;


) a. W# @+ y5 _  h0 |        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
: F" Q$ p8 B. A) [. ^+ H            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
3 ^1 F% u' D( P                if (arr > arr[i+1]) {
7 X/ N1 V0 v% _: e# O0 t, z9 g/ b. L                    flag = true;//在这里把flag值为true
3 d* h' O+ z) }0 G                    temp = arr;
                    arr = arr[i + 1];
, X' i7 b3 v" W- x, B                    arr[i + 1] = temp;
                }
            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
8 W7 k- _% _9 I  ~% d) s1 f                break;
$ k% ~5 {& H; A9 n            } else {
' m$ M$ o- I! ~; o6 X                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
) C/ q6 V. B4 }' _            }
        }
8 K6 w. H, N5 z, [    }
}
9 b- U% U; e7 x1 \/ c: ?五、测试一下冒泡排序的时间复杂度

1、代码是实现

import java.text.SimpleDateFormat;
import java.util.Arrays;
6 Q  t  a# h: L& Bimport java.util.Date;
& A5 J3 n* J7 H
4 w- A4 ]/ ~* m
public class BubbleSort {
- ~, `; _' K* J' K9 R7 M& q    public static void main(String[] args) {
! O; J: u8 Z3 j8 N9 T        //1、创建80000个数据来测试一下我们的性能
5 A/ b8 |. n: S( X/ y7 |, K        int[] arr = new int[80000];
: W( i& f2 h7 S$ {        for (int i = 0; i < 80000; i++) {
  N2 j5 o" z: ~  R9 N9 @- ]            arr = (int)(Math.random()*80000);//生成0到80000的数
4 k+ k% z: \7 |$ X8 I        }
  w  L7 E  W1 h) C# ]8 d( w        //2、输出时间
        Date date1 = new Date();
; r$ G% q# F7 \6 R& r- D; j9 U        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
& Z2 N+ D4 ^0 P0 L- K, q        String date1Str = simpleDateFormat.format(date1);
/ m+ @; U# Q. u/ w        System.out.println("排序前的时间" + date1Str);
        bubbleSort(arr);
. @, {# A, X; ~- Y8 {        Date date2 = new Date();
0 }6 U' l* r1 {        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间" + date2Str);

& K, C& G" O* t$ l


6 Z, v  \+ ~& W6 J6 Z- j( z    }


5 o6 g( C" V  t$ a( ?7 E$ f8 f    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;
7 P+ U5 Y4 A2 i% [+ U6 }
; V+ [- F  [1 A0 X# m4 c# F; A
        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
) C7 }% F( l+ d) P            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
2 g" K: G. c2 s) B5 z                if (arr > arr[i+1]) {
/ x' Y  t5 }' r, r                    flag = true;//在这里把flag值为true
: y& S7 P! f7 @                    temp = arr;
                    arr = arr[i + 1];
+ s! s, M6 Y9 T# n/ c' ~5 T" c                    arr[i + 1] = temp;
8 J( H+ [( Y8 q' n3 t7 ]                }
            }
/ `' b# N. [% p7 F, y& N& V            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
. v. ?! a0 v* |/ W2 e- I                break;
            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
: d0 r' W" f& G4 n+ m2 z            }
        }
    }
}



2、效果
6 h% r2 f$ P1 J1 p" t& t! \+ |+ K0 O" l
* F3 `/ O. T0 s4 U# k
  K+ @' g; a7 Y5 x& i+ q: H

  {: I. f) a# i' f" m& W0 h& Y) }
- Q4 u* Y" ?+ O% }' e: J

470557092

顶。。。。。。