排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
了解冒泡排序是什么！
4 `5 e/ k* `* u* ]- P& a) K知道冒泡排序的思路
9 A  A0 O! n/ J! \# q' Q知道实例代码并且练习
: `  j# \6 b9 S: J' Q+ O4 @0 y有收获记得帮忙点个赞，有问题请指出。
一、冒泡排序基本介绍
& P  p4 [, y3 @; \1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。
: z4 [1 N7 w% a9 q. ~

2、冒泡排序的优化思路
因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。
7 A* p9 \5 b5 a- c/ k5 h

3、冒泡排序的图解思路


其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：
% C  @  S$ \. }9 E! \: r- X

- [" f+ [( l6 G第一轮循环得到最大值
0 Q# W0 e. |* `, k6 Y5 o6 m& N第二轮循环得到第二大值
/ }7 `- O* ~% u8 _8 M+ ~% e第三轮循环得到第三大值
第四轮循环得到第四大值
# c$ ]) ]! C& g总的要进行数组大小减1的词循环


; }2 {0 S- a  B二、冒泡排序代码实现package cn.mldn;
3 c3 ~2 _7 o9 k/ ~

: G+ x  }5 [' K8 d& F" e* X. ximport java.util.Arrays;
  ^6 @! ?, I0 |- C) F8 J
  [6 h3 L, |- u( z
  E- F5 s* s5 `3 P3 y) H3 ~2 G) [public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
; n1 G' }6 h4 T: m        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
! y* ]* s  c% ?3 V) A- c2 e        //                temp = arr;
        //                arr = arr[i + 1];
$ O8 m& k: L3 E, n        //                arr[i + 1] = temp;
        //            }
        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
8 v1 E" ?/ U! q: V4 r  V        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
0 Z' E' u+ v8 \4 E+ x" Z" ~2 O        //            //如果前面的数比后面的数大，则交换
5 r1 g. D' C; _' j5 X" g! p* M1 ?        //            if (arr > arr[i+1]) {
# B# D0 O9 K. P- h0 Y4 S' p7 N6 }4 l        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
3 @+ Q9 V3 L; }) g& U* t, S! l        //            }
        //        }
( N& P; I) i" d! [: L/ v1 j' \        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
& v: D/ v. W9 K* w        //            if (arr > arr[i+1]) {
# ?' I- g' Q6 T6 b        //                temp = arr;
( U1 d. T' O4 _8 K, e  ]        //                arr = arr[i + 1];
9 G! p0 @! V7 b5 X! i( E2 q        //                arr[i + 1] = temp;
        //            }
6 `$ T1 Q. t4 H) {# U8 i5 t% c        //        }
( W- I1 s2 }4 V# F7 ?! ]8 s2 a        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
: K9 \% p' Y$ v' T& l. V0 l        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
) X! P' W- D9 n' I8 @  E        //                arr[i + 1] = temp;
        //            }
! w6 ?5 ]$ ?) V5 `) {6 O        //        }
0 G0 e; e5 j1 k        int temp = 0;//零时变量，用来将最大的数值排在最后
5 O' o/ r$ S; |4 c3 q- ?2 B4 i# E        for (int i = 0; i < arr.length - 1; i++) {
( L# A0 L0 x/ a8 A$ C% Z# Z            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
% `0 C: z+ v7 Z. M1 L( {( q) [                temp = arr;
3 t, C/ d4 n% }4 w; a% ?; \                arr = arr[i + 1];
                arr[i + 1] = temp;
- M/ j$ J% a1 n0 L2 M$ m            }
4 n8 [7 w. [* B5 i0 U        }

; O6 B' f5 Q: i& r$ W
, i5 S0 [$ g/ j/ z% b  _        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
% S! [  a; y' f9 a4 u4 W  K7 G                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
% i# U" F7 y3 X& w( b5 @        }


        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
. z# a5 Q4 n6 I                arr = arr[i + 1];
                arr[i + 1] = temp;
7 Q- U- ?5 H; E  T; _6 x5 x            }
        }
* Q9 ]& O2 _0 r0 f' a1 c" _
+ ?7 u% b2 t; Y9 g7 U( L$ P
        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
$ ~' |3 L( N; d- O  p( l            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
# s1 v& R: D& T2 H: R8 }7 _6 p3 Q                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
  f. i* a# f" o        }


        System.out.println("hello " + Arrays.toString(arr));
3 t, _# p; y& p, K5 X        //------------------------------------------------------------------------------------
" _' I3 A' D; L3 Q( l1 S8 C        //根据上面的观察可以知道了撒，可以再用一套循环解决

8 t, V; p6 N2 I, |. C0 H


        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
! c: a# o- J) x. X            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
3 i% \: f% m# I& ]# p                if (arr > arr[i+1]) {
4 P$ b7 H; G$ P% w. x; G                    temp = arr;
; V. O7 g+ o9 r; M0 [                    arr = arr[i + 1];
! P  e2 J8 O+ m, ]                    arr[i + 1] = temp;
! M2 \7 U/ P+ }% M3 R                }
8 O1 q  m/ m) T9 ?" Z9 c& Z: g            }
        }
    }
}
三、冒泡排序的优化

1、思路
如果我们发现在某一糖过程中，没有进行一次交换，提前终止
" F% Z9 x' u0 }8 b2、代码实现

package cn.mldn;
& z5 n/ n- f& S
3 {1 E& P4 ~! t; ~! O3 E7 t
import java.util.Arrays;
3 I2 X  M& I! N8 L: G

public class BubbleSort {
0 Y( h5 G# h1 i; o& Q, m    public static void main(String[] args) {
3 N" H9 u% }$ M0 E        int[] arr = {3,9,-1,10,-2};
        //大致过程
/ m2 K* x2 l" g# B5 ^0 X) j% ~! K/ ~        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
% E( ?, v5 H# b5 N/ ~8 W( ~        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
) d& V( x: w0 m        //                temp = arr;
5 y# ^2 l/ S: S  F5 @& m1 Q        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
+ M- J4 |% R4 x6 ?& z* e. R8 m        //        }
" F4 M# w0 |" s% u0 [        //2、第二糖就是把倒数第二大的排到倒数第二位
6 D* T  s/ L7 k; M+ P4 x) ~        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
: A4 F# m% P9 [: X- {6 }- ^        //                temp = arr;
2 ~. X/ j# ]# {8 O" U        //                arr = arr[i + 1];
( O2 s) ~4 |' u0 _, Z6 O5 M0 }) M2 ~        //                arr[i + 1] = temp;
& I; v3 R' ]2 q4 U: O, E( o6 M        //            }
8 u5 P. [+ p4 b+ C        //        }
0 }  u# G: R7 i& U        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
1 X4 C- Y5 I' ^4 P        //            if (arr > arr[i+1]) {
/ s* v+ V' _! h; I5 b6 i        //                temp = arr;
        //                arr = arr[i + 1];
1 z6 Y3 E5 t% Z1 c        //                arr[i + 1] = temp;
        //            }
        //        }
/ `# z) }0 F0 w* Q        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
. {5 M- [: d6 J* Y* T        //            //如果前面的数比后面的数大，则交换
. v9 T1 P; m- [% z( Q- `! k& a        //            if (arr > arr[i+1]) {
        //                temp = arr;
- H4 Z( p7 d5 I6 c        //                arr = arr[i + 1];
& l# o& W# S4 H        //                arr[i + 1] = temp;
# |' C6 F1 A0 m8 ~: k& Z% f        //            }
        //        }
        /*int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
% g6 _! X9 t5 N' Q4 N# U            //如果前面的数比后面的数大，则交换
- A* J: O9 R; `# n% T' q            if (arr > arr[i+1]) {
                temp = arr;
  b3 A% `' ~: b9 ]9 O* o                arr = arr[i + 1];
                arr[i + 1] = temp;
* ~$ Y! U0 I2 j0 x& g7 j            }
        }
1 z% _9 Z% m/ o* [7 g; ?* t, f
- R% B! ^" \+ I: h+ T# y
8 e, U" ~5 R" e        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
( l+ P  t0 f3 K5 s0 k2 Q  s            if (arr > arr[i+1]) {
                temp = arr;
2 X) y$ |  g+ B0 Z                arr = arr[i + 1];
1 v, I: n: i% n$ z( s+ ]                arr[i + 1] = temp;
            }
4 j+ G6 N5 I; R) ^5 L        }


        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
. a$ i$ e' o  n. G            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
; X6 A) O: d2 P8 O, j                temp = arr;
- x* a/ X6 h$ d                arr = arr[i + 1];
1 `! h! W5 G7 Q) W                arr[i + 1] = temp;
            }
* R5 d. z* }4 a1 ~6 C        }

' p/ B7 ^) w& }/ F6 p& X) @" f
        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
9 m# Q2 u( O- f$ Z% p" o            if (arr > arr[i+1]) {
& l% g3 o* e  @% Z+ x                temp = arr;
( R( d1 F$ D& }( R/ u                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }*/


* Z$ e2 D' Y- o5 [; |        System.out.println("hello " + Arrays.toString(arr));
7 }# k8 l; d. u/ j        //------------------------------------------------------------------------------------
* C0 p9 n9 T& X* O; @2 L# x        //根据上面的观察可以知道了撒，可以再用一套循环解决





* s  X! N" C) S# n# I" p
" y+ ^: B1 H" H, ]3 _" Z        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;

% n' [7 f7 x# c# Y, u1 b
: F& u8 R% u8 A3 p7 s& z        boolean flag = false;
- R0 j: o$ S& l# Z" l        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
" K3 j  @& I" f  u3 p* m                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
0 c5 y5 ~& S: {$ F( I- X5 n                    flag = true;//在这里把flag值为true
                    temp = arr;
8 k& g; v6 p! `1 E5 w                    arr = arr[i + 1];
, `# l1 T- v' s* t# A, Z                    arr[i + 1] = temp;
                }
" Q2 b: k. w& P/ p2 w            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
            } else {
$ p9 A# [( b% Y" o- m2 U- i; D                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
! D8 M5 J0 U8 o        }


        System.out.println("world " + Arrays.toString(arr));
    }
}
四、将上面的代码封装为一个方法
public class BubbleSort {
3 q" P( c, \0 d, u    public static void main(String[] args) {
$ \: S; {) ]4 e$ g        int[] arr = {3,9,-1,10,-2};
* l5 U6 |* ]( \* B
. V5 r- T" k5 g9 h
        bubbleSort(arr);
        System.out.println("world " + Arrays.toString(arr));
3 |9 t! N3 V' `6 ~" A5 S    }
' E2 A8 s- f( P/ D

    public static void bubbleSort(int[] arr) {
! R$ g/ T. y" F# R+ p- N        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;
9 r. X4 l- q# f( T
: @, B6 w5 N" f8 O
        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
* S& e& r: H( T1 w                    flag = true;//在这里把flag值为true
                    temp = arr;
8 ]2 r/ Q* t- V( u                    arr = arr[i + 1];
                    arr[i + 1] = temp;
0 Y  D' T, q1 s) a                }
0 A' b0 H# O/ Q) @& L4 V; J            }
            //在内部循环的时候进行查询
( p" w# f0 M" s! F+ s            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
            } else {
3 Y5 p* p2 A1 D: \4 h4 `                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
2 d" h' B( k* W8 m' Y3 l: F    }
}
五、测试一下冒泡排序的时间复杂度

1、代码是实现

import java.text.SimpleDateFormat;
: R1 V) p/ `1 k, w1 @7 \import java.util.Arrays;
6 Y/ Y1 D, {% Z3 G. ]' X- Qimport java.util.Date;


) |9 l# t, T2 ~$ \. Qpublic class BubbleSort {
    public static void main(String[] args) {
        //1、创建80000个数据来测试一下我们的性能
; p! k6 K8 V. O6 ?( ^        int[] arr = new int[80000];
3 ~+ Y  A# T2 q% T% b        for (int i = 0; i < 80000; i++) {
! |0 U, b7 `* x3 o& x            arr = (int)(Math.random()*80000);//生成0到80000的数
        }
: J) H. U& |" w        //2、输出时间
' T1 F+ l9 f" Q; P        Date date1 = new Date();
9 _2 A$ w, O8 }% i, _' i( Q+ X) ?        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
2 M. C; m  q) _2 e: ^& Q5 \  D        String date1Str = simpleDateFormat.format(date1);
) Q' C" D' Y9 [( U$ Y        System.out.println("排序前的时间" + date1Str);
        bubbleSort(arr);
8 u8 Q. z3 {9 }( r! j        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
# a* Y3 {( [4 I        System.out.println("排序后的时间" + date2Str);

6 g+ r; o0 C  g0 {
  w' e, o8 a/ ^& ~6 V  Z4 G( T: g6 D
( u7 A7 V9 X1 E- a( v3 R
- M, J% z; Y0 S6 _    }
# y0 F7 a/ q8 m4 [8 H; }  M7 ]8 b2 X

    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;
/ n- B! V; w: X/ T# ~! {

        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
! x9 k) }5 z: i5 s0 q5 X                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
: r0 P% Z3 S# Y                    arr[i + 1] = temp;
! @- {" s. F# f" q: ]- w                }
3 I( ?0 L/ @# E7 D; F) x            }
/ i( d: s* P  o& N            //在内部循环的时候进行查询
! I* B9 D4 w% X5 d, `( @) A            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
) z9 O+ n; m; A  Q/ Y' W                break;
# d/ b& z2 q; _            } else {
9 p& u8 {2 z# m                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
    }
}

+ P$ c. \+ W6 |: Y1 u2 n8 S

/ g$ y" Z1 T$ D) K# V2、效果
4 N/ E2 o( k6 |$ ?2 s1 s


. P% G# p8 O2 B( U2 a

5 ?& z6 ~( }9 B+ l4 U) t

470557092

顶。。。。。。