排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
了解冒泡排序是什么！
4 w: Q; g( D$ w% _' O8 {1 A: L知道冒泡排序的思路
) d& P) C3 s/ P0 M3 c& i8 C知道实例代码并且练习
有收获记得帮忙点个赞，有问题请指出。
一、冒泡排序基本介绍
1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。
* h) Y( `& s& v

2、冒泡排序的优化思路
) Y) {4 N- O7 a9 Z因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。
; \7 ?8 k" P5 z! a

3、冒泡排序的图解思路

3 K0 s0 c- u  m3 a- e3 |- D
其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：
$ |# P) Y: ~, a

% F7 o4 t" c; |9 G6 F% H- W第一轮循环得到最大值
$ m: H0 }# k) Y: N第二轮循环得到第二大值
6 N+ e: w6 Z7 ~第三轮循环得到第三大值
8 L- p) \/ C4 v, I( a0 L3 o第四轮循环得到第四大值
, C0 v! q2 ?9 `3 A; m( W- K总的要进行数组大小减1的词循环
3 h/ Y6 p% B" r/ J/ K8 F
$ M; |; O$ x1 S# Y/ Q* y1 g
二、冒泡排序代码实现package cn.mldn;


import java.util.Arrays;
% A1 `$ h; w/ E2 Y" {9 O

; |) b& X) a6 l( m9 dpublic class BubbleSort {
% O& q4 g0 c2 @    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
+ @3 Q4 T( P2 m+ K! ?' V: l6 h        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
, C6 u3 t9 Q7 A        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
2 t- m7 N" F; A- m! ]: Q        //            if (arr > arr[i+1]) {
        //                temp = arr;
( p& z: g% \' @6 j- Q        //                arr = arr[i + 1];
, Q! F% _- p* V7 f  a- U        //                arr[i + 1] = temp;
        //            }
! Q# Z5 p( x4 O+ v7 I        //        }
! Q0 {& m  G) K        //2、第二糖就是把倒数第二大的排到倒数第二位
* u0 I4 c' T+ Z+ p' `        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
7 @! L! g% a: l( q4 E: s        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
8 x: H* }8 ^; P        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
: K2 S; u( }1 D2 v* Z        //            }
4 e0 D. `- y9 a        //        }
: \! p! [' h( o' p        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
% X  W. v9 X) l2 x        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
, O/ e6 ?- Z- E8 E1 a- L9 p0 U8 N        //                arr[i + 1] = temp;
! i  Q* n$ Z( [: ?' A3 H4 m        //            }
        //        }
5 D2 a1 @2 n! J" j( s+ I" d        //4、第四次排序，以此内推
  z% ?- K. @7 y# @" O& G        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
" S5 K/ \  m8 ]        //            if (arr > arr[i+1]) {
5 O, h  V1 y. V& q4 r        //                temp = arr;
5 Y6 I# G) F! I, ~* C        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
: Y! Q% ]. i$ C' `$ `$ s* h# i        //            }
        //        }
/ Y% b$ O, Q2 P1 h  Q! m& Q3 t        int temp = 0;//零时变量，用来将最大的数值排在最后
- K- `3 ^3 ~" Q        for (int i = 0; i < arr.length - 1; i++) {
3 p" K5 |/ o2 O6 ~) [  v            //如果前面的数比后面的数大，则交换
: H- y% @1 K: f' `8 W; X8 E            if (arr > arr[i+1]) {
) Z* H2 I& k2 k2 x! T                temp = arr;
                arr = arr[i + 1];
* |& H9 m2 o; q! r                arr[i + 1] = temp;
            }
+ s$ d# v* i3 t2 ^7 M        }
( v. d4 Y* o, M+ d/ p. |5 m0 l5 r1 t# l. A
+ N8 V7 b+ M# T9 s5 [
: z& h4 \2 e. T6 \0 f4 K$ i        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
1 [) ~# _. k" `5 b                temp = arr;
! E3 e. z  m& O7 a4 m                arr = arr[i + 1];
4 Z* [/ k: M" ^* Z, U& D8 w                arr[i + 1] = temp;
% E3 ~3 \4 G) ^! i1 d( ~( F% S: p4 ]            }
        }
/ _0 s3 i: y0 @$ u/ z# F; z8 c/ S  e
/ u' m+ u* f# k' j+ I" o
0 b) G- u+ _/ g  R2 z        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
2 @  ^. J9 k) \) Y5 `3 x, Q0 W            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
  N$ t! e% |! q+ [( O                temp = arr;
                arr = arr[i + 1];
: k. F4 @5 ~$ E6 q                arr[i + 1] = temp;
            }
        }
8 A" ^5 Q5 ?7 G7 f% k

        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
  Y& v9 M# f2 k: c0 g: Q            if (arr > arr[i+1]) {
7 Q" W) e" P4 P$ ~                temp = arr;
9 V2 E5 B$ @% p: m1 h6 Z* Z. [                arr = arr[i + 1];
                arr[i + 1] = temp;
. m$ B2 X# P) `' J0 c7 N5 [! ?            }
: F7 l( r8 U1 q- n: c, I. A        }

/ x2 n, K: g8 V( f* O
0 T1 ]) `3 p6 S7 x" }        System.out.println("hello " + Arrays.toString(arr));
/ O& X/ G! Q+ y2 }3 z- e7 S3 n        //------------------------------------------------------------------------------------
8 X! q3 s+ ^5 y/ M6 h        //根据上面的观察可以知道了撒，可以再用一套循环解决
5 Y1 [$ Z* _8 H0 O0 n



        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
" ?. r2 t; h! |8 e0 x            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
+ R/ T* z: w1 {2 R  {                if (arr > arr[i+1]) {
. H3 D1 i" T2 a- j- w                    temp = arr;
                    arr = arr[i + 1];
7 D9 P, k/ c5 o% q                    arr[i + 1] = temp;
                }
            }
        }
! M" j' m8 C! r' W2 y    }
- ?( m7 b: t2 q" J9 `4 @* j}
三、冒泡排序的优化

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

package cn.mldn;
& ?. W- y, M) J' p) i# ^
3 L% y% _3 a& I- H
import java.util.Arrays;

1 q4 A/ O5 X6 ]9 I) D! n& I% }
public class BubbleSort {
    public static void main(String[] args) {
9 ?7 S1 o2 E8 H+ e        int[] arr = {3,9,-1,10,-2};
$ b1 |3 u1 c3 Z1 t- K4 n$ `        //大致过程
. ]3 e. W6 Y+ [; g, y        //1、第一步就是第一轮排序得到最大值于最后
2 p% H3 N4 D4 ?4 `8 h2 {        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
6 c% b' k6 u* ~        //            if (arr > arr[i+1]) {
        //                temp = arr;
) r$ y7 F3 ?# e2 F; V$ M0 h        //                arr = arr[i + 1];
& g+ f1 u2 u' x        //                arr[i + 1] = temp;
# r- t# l: e) P, w0 ]! D2 g        //            }
, t% G% q2 K5 R% p& a$ m        //        }
: B1 l4 u9 W3 O) W* R* r        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
9 S9 T8 t, Y) r; x6 j        //            //如果前面的数比后面的数大，则交换
5 b( N9 m9 q2 n8 [/ B( _        //            if (arr > arr[i+1]) {
: Z3 R7 d, d1 g) J        //                temp = arr;
0 P1 p' }* R/ e+ a        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
  J: K% ~# q6 n& A        //        }
        //3、第三糖排序，以此内推
0 m, p" q9 B; O8 p! F& S% T7 A        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
# X5 ~  H" }0 Q) ?5 [- |4 w) n        //                arr[i + 1] = temp;
        //            }
        //        }
5 _' p" w; _) h; f) I1 H9 W' r        //4、第四次排序，以此内推
% o9 W% g* K. M; v& G        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
8 q" i- A+ D. Z! d0 T! c        //                arr = arr[i + 1];
- q6 R6 B7 H8 j! V, ?8 Y! W9 P        //                arr[i + 1] = temp;
        //            }
        //        }
# _8 H6 ~1 v# |* R# t' r        /*int temp = 0;//零时变量，用来将最大的数值排在最后
( D. ~; x6 ^$ L) h5 L$ t; ?        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
/ s# @' d& v+ S* B+ s            if (arr > arr[i+1]) {
9 D$ A7 z  v- B: M5 c/ |  k0 O                temp = arr;
                arr = arr[i + 1];
! T' E9 @5 a) x; g8 S$ C                arr[i + 1] = temp;
            }
: h" |) W2 F' H        }
0 ]" {0 D# r  z; O2 P

        for (int i = 0; i < arr.length - 1 - 1; i++) {
3 d2 P3 e0 P/ L) V5 D' `$ I" B            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
- [) t1 j* k. V% _- G8 J* A2 {; j                temp = arr;
' N3 Q$ _, r8 x3 u' }$ y2 R' ~                arr = arr[i + 1];
                arr[i + 1] = temp;
4 \( ]3 L, P6 F( b. O) ~0 q5 [            }
) P: @. Z# @, w/ p6 c4 b  c        }


        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
/ t" d& W1 X/ b8 y! I( `                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
2 R. d( b* r# y/ _/ D& g/ ~% c        }
& a# w. l6 ~' ]- q( ?% Y0 w1 s

( ^: Z% T$ U1 ]7 f, E! z        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
- @0 _3 O. V  Y9 I  c2 ~+ H                temp = arr;
. k; ]: ]: g0 n3 E                arr = arr[i + 1];
                arr[i + 1] = temp;
0 j! ^! U' p# R' c/ u            }
        }*/
1 r& a6 b. z% }4 Z# F- K6 N, f7 l9 z

        System.out.println("hello " + Arrays.toString(arr));
& K; P( b, w0 Y6 J+ p! d% \        //------------------------------------------------------------------------------------
) o/ T. {7 J7 K8 Z( d        //根据上面的观察可以知道了撒，可以再用一套循环解决
( B  S3 Z4 h# O8 Z




  W9 u) Q7 D6 c- u  {% g* G
) i! z) K0 \! |+ L% z2 X& d  L        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;


4 U" h, `4 {, E: _4 w' |        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
/ w' S/ V- T4 \* N            for (int i = 0; i < arr.length - 1 - j; i++) {
1 l( @1 Q$ s7 V                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
1 p. p/ b- l/ ?+ b, [                    flag = true;//在这里把flag值为true
                    temp = arr;
* Y3 H8 [4 D% V* O6 @                    arr = arr[i + 1];
                    arr[i + 1] = temp;
( T4 ~+ q4 }" Z) E                }
            }
" l' ]2 v1 ]8 c- c1 T            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
" k; I# P0 V1 I8 w, }& p4 X/ @' l                break;
1 k, o9 H( v6 g8 G! C            } else {
- m4 {" A# X5 w- q1 s+ E( h                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
: m+ ?% ]1 Z, h        }

5 B8 I6 u: J* U4 z
        System.out.println("world " + Arrays.toString(arr));
4 D& h. u) F( J- E$ j: B    }
}
8 s1 E' E% t! u6 Z/ I& A四、将上面的代码封装为一个方法
public class BubbleSort {
. [2 c' H& L: L5 J$ }    public static void main(String[] args) {
& U6 k- W( G0 X6 U& F# d        int[] arr = {3,9,-1,10,-2};
, o8 S& Y: K9 s
4 U# \% H" k2 Q( w
        bubbleSort(arr);
        System.out.println("world " + Arrays.toString(arr));
    }
& @; a8 @# |0 y/ y

    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;


        boolean flag = false;
  k" d; S' u  b) I4 T        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
: R: w: w! K# ]0 Z* u                if (arr > arr[i+1]) {
8 Z2 Q2 C# u+ ~7 V! A                    flag = true;//在这里把flag值为true
/ E9 i# ?* U( e/ z+ B( T( @                    temp = arr;
7 _6 U( Q- O+ j5 l1 ~  s9 z* P                    arr = arr[i + 1];
                    arr[i + 1] = temp;
" l+ ^, `5 m" b/ ^% @, ~* ]  X                }
            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
! u$ p0 `8 T# a  N2 a) t9 X                break;
            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
    }
}
8 Q7 N. C" O* Z* r. j( {五、测试一下冒泡排序的时间复杂度

1、代码是实现

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

7 P& \$ v) Y% |8 u# Q
public class BubbleSort {
' K/ m3 X6 Y% n) h/ w    public static void main(String[] args) {
        //1、创建80000个数据来测试一下我们的性能
  G& x% I6 `& j9 o4 x6 A& S        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr = (int)(Math.random()*80000);//生成0到80000的数
        }
        //2、输出时间
* P3 d2 q4 A& X        Date date1 = new Date();
# W3 J7 |! _0 d1 Z7 O8 V        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
        String date1Str = simpleDateFormat.format(date1);
0 D! \- n/ D5 |- R2 H; f2 V  d% h        System.out.println("排序前的时间" + date1Str);
        bubbleSort(arr);
        Date date2 = new Date();
( F8 p: c7 g# |        String date2Str = simpleDateFormat.format(date2);
! j- U: K' f1 B        System.out.println("排序后的时间" + date2Str);


: i% T/ N' }9 A. Y6 Q3 N7 s8 b' M* q
/ L. Q$ C& G9 D1 L( n" {
    }
- C" P% q6 A4 s' p7 }1 w

    public static void bubbleSort(int[] arr) {
" N  h% ^) J5 q& B        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;

4 F0 n1 b0 F8 J2 C
+ t4 D9 z. g9 v$ X3 m9 A/ ^        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
8 h8 R$ M" D" _                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
- Q( k) `, g- E  d9 b' R* S; q                    temp = arr;
% f8 K# W- L1 y# I$ C9 a3 a                    arr = arr[i + 1];
0 s; [# o5 F- N; I                    arr[i + 1] = temp;
  f2 U  m7 Q& {                }
1 N. l; t' H4 P2 o            }
+ o3 E% p' c$ F            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
$ C* q* V1 Y6 @+ L4 ]* I4 u                break;
1 H' ^" v' B5 z. ]; Y            } else {
$ d7 J$ G/ P$ u9 b- @                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
2 d( g5 y6 ~- x            }
8 _/ B$ J# r# K3 r        }
# K0 G5 e! c% W9 t* K$ o% x    }
}
9 ]. N. W. c# b1 E! {1 ^
' @+ J  G$ Y% s8 B6 K% `. T" d
4 G( `3 y5 K2 p# _& w2 Z/ w
  Y% O. L) [5 @/ \$ e& {( o2、效果
. K; v0 Z. ^/ }5 j
9 T  U8 d6 H! {1 G4 W( N4 \3 ?3 A
7 l; O* t1 F) O8 n' j  E- S


2 r* ^" [/ D- G% |; N% \

470557092

顶。。。。。。
5 x+ w3 d7 i4 v$ f5 Q: d8 i: ~* u
0 N- V' G- Q" X: `, Y8 S