排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
了解冒泡排序是什么！
: D+ G1 Q1 @6 J" b; J# B2 n, ~6 ~知道冒泡排序的思路
" Z6 ?: W) h* z知道实例代码并且练习
有收获记得帮忙点个赞，有问题请指出。
一、冒泡排序基本介绍
1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。
  [4 N3 V0 D' ~; V8 C0 n
& p7 H5 R. V$ m. y& U9 Z9 X: I
2、冒泡排序的优化思路
- a" `4 J8 M# m- |! }" [( B; n因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。
! N# A* {* c8 r2 l+ J  Y) y

3、冒泡排序的图解思路
( i" [3 s$ |; h# b6 X; S0 _7 L
& k; }1 U' ]" m$ L  u1 t
其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：
& K. S/ s; r& V, h9 j
; y1 q+ J% L0 `1 w5 X
第一轮循环得到最大值
/ B3 c) F, ?) a第二轮循环得到第二大值
( Y$ z$ @* o# ^第三轮循环得到第三大值
第四轮循环得到第四大值
总的要进行数组大小减1的词循环


二、冒泡排序代码实现package cn.mldn;
; P/ M  \  h9 F& z* |
, L& F" g. M) d8 S
' ~. k' U, F) l2 a. c: F  r5 k8 @import java.util.Arrays;


; g9 {- d) T; Q9 x- Q  Lpublic class BubbleSort {
    public static void main(String[] args) {
( b% {# A& ~" ?' z- `  v# X        int[] arr = {3,9,-1,10,-2};
; N1 G3 i# r( b2 b+ h        //大致过程
/ n( L5 F- B! a. E2 ^9 |        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
+ |* v$ W9 x/ U        //            }
5 Y; r, ~0 H/ `  E5 K        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
) |6 m7 s4 [* G  z2 c: y. T        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
" H! A$ t; @$ d: t' {# M        //            if (arr > arr[i+1]) {
% ~2 ^/ i" B0 _& V1 V' b7 K4 F* `1 V; C        //                temp = arr;
* Q7 [$ A( C0 R5 u4 V1 t        //                arr = arr[i + 1];
( N3 X7 F+ D/ Y" P5 `        //                arr[i + 1] = temp;
        //            }
        //        }
) s( Y" E4 K4 l- W9 {        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
2 ?; \9 t4 x2 z" B  E5 |+ J        //            //如果前面的数比后面的数大，则交换
6 m# {6 \( D9 V/ W        //            if (arr > arr[i+1]) {
8 g0 A) y- \" r        //                temp = arr;
% Q: C5 U% [0 p. I' B        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
/ G7 H- }' R  k# N. D        //4、第四次排序，以此内推
3 Y5 Z) ]: m8 O        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
, a. f8 p- S% {8 Q        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
3 C( L+ f* m; T$ a4 [6 G        //                temp = arr;
8 a2 b- V6 c; C        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
        int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
# R9 G) U, r6 `6 d' H* e            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
5 T( i& _0 l7 [4 L+ e/ X9 p! i                temp = arr;
                arr = arr[i + 1];
1 |0 \2 e# _% j* i" c; |                arr[i + 1] = temp;
! c6 N# C2 @7 `9 B            }
        }
( p( ^+ b/ @% S
( r$ ^7 a* S- [! y/ U
        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
1 }) D; Z8 d( A" S& f3 _- E% ?            if (arr > arr[i+1]) {
. v  i9 N: W/ M: {4 p3 F                temp = arr;
- \  ]/ p" u) L$ h9 \' h                arr = arr[i + 1];
6 e- O; ?6 ]. f8 t3 Y6 Z                arr[i + 1] = temp;
            }
3 `, M7 L: J( P: J/ O% k5 y! w        }


: h/ d8 D3 F1 f8 B+ I        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
0 E' q, x" L) X4 Z: ^                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
' z4 k3 a0 I  ]0 `# z- h* E            }
        }


        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
+ N) c& Z7 Q# i            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }


        System.out.println("hello " + Arrays.toString(arr));
0 q+ y( b. I" _% R" X        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
$ S8 L8 \& n5 L# d# i) {% Y& r

9 Z1 [5 N4 _+ D8 G8 D

        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
( r. g6 q: s. E0 L            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
  v% U0 f1 e- U# a* h; X7 I                    temp = arr;
                    arr = arr[i + 1];
& ^2 n6 J/ @/ s3 D. Q                    arr[i + 1] = temp;
                }
            }
        }
    }
}
三、冒泡排序的优化

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

package cn.mldn;
$ @% L6 O. ]& {) B# F' Q9 w
) Z0 ^7 ^. e) N% z" H4 n
* B  W5 ]+ m% s. R' d! i$ G/ }import java.util.Arrays;

: U6 v, y" u/ F. E6 {# `" B
public class BubbleSort {
    public static void main(String[] args) {
/ c8 v4 i' f4 E- ~# i1 z        int[] arr = {3,9,-1,10,-2};
        //大致过程
3 ]2 t4 a0 R; d2 `: h3 [3 i' w        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
/ o) W# n/ F& U: b7 C( M        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
/ h/ [$ E; a+ Z5 c6 A1 \        //            }
* c, w' W8 Z7 `- I1 h: A        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
5 p& v  s4 s5 u; J# j* W9 `! j        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
6 `% C3 Z  p5 c( N- B1 }% m        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
1 U2 G  z) O8 J7 b1 a$ S) w        //            }
        //        }
        //3、第三糖排序，以此内推
        //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;
2 E& i. m& j8 U: e) N$ U% f        //            }
        //        }
  O: X  _" g$ ]" T! M8 M        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
) \& Y0 q9 L" G8 n2 a3 G! H) ~8 Z        //                temp = arr;
" M0 O3 i% M( a2 L' p( s0 `, U0 V        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
! j. S6 T, ?# v/ S/ U) {! l        //        }
+ |% k2 ?" M: A: N# C1 u$ F        /*int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
0 A* @( X# {6 s: p& R" o" F2 l/ ~            if (arr > arr[i+1]) {
0 X" P/ {+ }7 l* o                temp = arr;
! F, b) _8 _/ }; \! u* C3 E                arr = arr[i + 1];
                arr[i + 1] = temp;
! z- q8 g' Q' N3 o0 w            }
        }
( G0 S9 X+ k% m: j, u; m  K

) P7 E$ Z/ G' u3 b' Q4 C        for (int i = 0; i < arr.length - 1 - 1; i++) {
& b, v# h4 s2 Z/ x  I+ h  J            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
! d2 R3 T4 T* B$ r. ~" ?- y                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
' V8 v3 E. `  u        }

1 N  E6 {' b) f9 D. x
0 c" R% D! W) Z  H        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
( v4 q2 n1 A2 m$ L# o            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
# h4 v' N1 X4 b! `; f: V                arr[i + 1] = temp;
            }
5 S! _. h0 T+ O3 x9 {" c* O        }

4 n; L! z3 \: d% q1 _& B: B2 `3 j
& _7 {9 _8 L8 x5 X% l/ H8 E        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
. [/ E' W" H% e5 ?/ i  z1 p                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }*/
- O. t/ X2 ]. |$ ?3 \( T

        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
4 Y) W$ H0 u: S* n- o        //根据上面的观察可以知道了撒，可以再用一套循环解决





6 ~( u3 |- I1 i! O2 s; e
- b1 @2 h& L9 s        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
+ k2 B* V% e% o. P) v' H, o3 d" U( s/ t, e        int temp = 0;


        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
" {% }* X" ~, V4 f# f' ^4 S                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
, ]8 n! ?5 I. l8 A. V" r9 @# V                    flag = true;//在这里把flag值为true
* B+ l" G- L# K, e0 _                    temp = arr;
, L+ v/ k; _5 n' W0 w9 f9 q4 M; n                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
            //在内部循环的时候进行查询
5 G- T6 d8 o  T, E            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
. k. i( m$ L% L0 M) \  j9 E            } else {
) d8 _; y' x. D: Q0 n* G                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
; F* |5 L4 {! C4 U            }
        }
) ?' a/ ?/ t( {4 s! r' O! o* N
) q' V! \  f% f3 S& R1 ~. K& T
- a5 Z9 j+ w$ q7 Z$ n" I3 P        System.out.println("world " + Arrays.toString(arr));
    }
}
( W6 T* u/ I5 q9 y8 ]四、将上面的代码封装为一个方法
public class BubbleSort {
4 h8 e( p0 d, U0 y9 ]# `) r    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
; r" j3 A* d& C* n
6 P; ~# L  f1 W2 [9 `
        bubbleSort(arr);
        System.out.println("world " + Arrays.toString(arr));
    }
: x2 d) @  Z4 ~5 H. T2 K$ ?+ I" W9 t

    public static void bubbleSort(int[] arr) {
% S1 v3 N8 E8 V% W        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
2 x; c0 w) c* U6 m2 ?        int temp = 0;
1 ]/ E1 ]0 W* a5 W! U0 U

        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
+ s$ b6 E2 _* A* k" I6 g/ v+ D                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
' A! q+ y- h) v% {8 K7 I" y; o            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
( s! Q+ P4 d* f# k* Y; J. r            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
    }
8 B2 K& y% T# {4 r9 i; G" x}
五、测试一下冒泡排序的时间复杂度

1、代码是实现

import java.text.SimpleDateFormat;
import java.util.Arrays;
0 I0 t- s% ?1 ]5 T8 `import java.util.Date;
: T) S" T' M/ B* ?5 `2 {1 U0 c

public class BubbleSort {
/ a% i; W* Y2 F- Z) ~3 [: O    public static void main(String[] args) {
        //1、创建80000个数据来测试一下我们的性能
* D9 {, t- U- J8 P( S5 ?9 y        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr = (int)(Math.random()*80000);//生成0到80000的数
4 {* T; j5 L7 F        }
+ h# R$ h, A# s: o) @        //2、输出时间
        Date date1 = new Date();
; H: }  Q9 Z* Q3 R" v        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
0 F; q/ a* p* I8 G2 ?! S9 |* a        String date1Str = simpleDateFormat.format(date1);
& X. |* f2 d( @8 [" F        System.out.println("排序前的时间" + date1Str);
* ]3 E' I4 x1 t% R        bubbleSort(arr);
, m! t* n8 B$ k9 J" r$ R9 z% _3 g: f        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
: i; Q0 M2 S& n* `        System.out.println("排序后的时间" + date2Str);




9 }0 ?: P5 h2 L& _7 f, h$ L    }


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

+ C4 H9 M) v( h  B9 O
        boolean flag = false;
- y# A, M2 w3 I: {2 y        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
- [: W# O6 C; n                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
. H4 E/ V7 g7 g" ]2 x1 R                    arr[i + 1] = temp;
, P- d% p4 h% d4 b5 u                }
% x( W0 Q2 I3 ~1 e            }
; Z6 @5 v1 L# W            //在内部循环的时候进行查询
; h' j9 \0 O& h  ~6 W" L! u5 _            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
) e$ g/ _5 C* f                break;
: h9 \6 P7 y* [  i0 P            } else {
8 g, I& Z  ?4 `0 S! u                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
+ h, z  Y2 c5 M6 [  G$ P/ m8 y- p& T        }
    }
$ M3 U' y8 J& j7 z}
: A% E! `! e& w' c$ q

% v. Y9 L4 D- a  R( I9 l  D
2、效果
' Q+ a; C& I9 L
; L! _: g- c8 H5 X7 \5 \

; X. C; f% y* i2 o7 \

$ C1 }7 Q8 w$ F7 N! \

470557092

顶。。。。。。

9 m' R4 U& l1 t5 S' T0 j