排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
1 ^2 d* f. Z  H7 U了解冒泡排序是什么！
知道冒泡排序的思路
" `  Q5 Y9 {- ]知道实例代码并且练习
) `* {: K, h8 e. w8 X有收获记得帮忙点个赞，有问题请指出。
一、冒泡排序基本介绍
2 X: t$ A  R- u1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。

$ {9 J; j$ F& c0 F# r
& s' M/ r( d' O; F4 {; x8 C! \2、冒泡排序的优化思路
因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。

9 M7 M. `3 I, j. ]! v# f
3、冒泡排序的图解思路
" a& y# {( ?* t3 B8 D/ L* p
+ w# H( c! A3 z* I, c8 M
其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：
7 h. |- t: Y# r0 t( v8 ^6 j7 u; x

第一轮循环得到最大值
第二轮循环得到第二大值
第三轮循环得到第三大值
第四轮循环得到第四大值
7 F" E+ q& I  `+ c& |/ L) t7 Q总的要进行数组大小减1的词循环
' T$ e" J5 M; o
+ q% z& l8 y9 `2 Q; b. q
5 o; e! K) c9 V二、冒泡排序代码实现package cn.mldn;
8 ]8 e0 ?  W0 N  P$ j

import java.util.Arrays;
6 C- N% }. I/ l# D$ l9 h0 S4 ^

public class BubbleSort {
: Y: d6 {. b' h# D    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
        //大致过程
% K0 C- v. V8 b        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
0 J" v9 ^7 v; b3 v4 F        //            //如果前面的数比后面的数大，则交换
' V/ r! i( x/ M( ~4 Q* s        //            if (arr > arr[i+1]) {
        //                temp = arr;
2 f9 Y% }! i5 b( [. E        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
/ {( q) C( Q7 J        //        }
0 V8 ~0 }2 k$ P        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
# a8 G: @* X% }. T" u9 |  p' E        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
# I3 A7 |2 U/ b8 }# A8 N        //                arr = arr[i + 1];
/ p6 [& L, u9 D: F6 R. }! |$ \        //                arr[i + 1] = temp;
        //            }
        //        }
5 U, t2 j7 G% S        //3、第三糖排序，以此内推
$ D6 u9 v) \( G! P        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
" X" ?6 k0 z* |* V. l4 x        //            //如果前面的数比后面的数大，则交换
' y8 u+ ]- Z/ t* l4 b3 |# E        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
4 X6 ^. L/ a" C2 P1 [6 X; d        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
3 }( v( a/ Z! o5 o3 y9 w0 c        //                temp = arr;
        //                arr = arr[i + 1];
8 R; x  ~. Y1 D, z        //                arr[i + 1] = temp;
        //            }
: Y# v: x; g4 B( j        //        }
; {0 j; g2 |: f0 z- C+ n8 f. A! {, @        int temp = 0;//零时变量，用来将最大的数值排在最后
6 p$ P; j7 G1 ]9 K7 y' N        for (int i = 0; i < arr.length - 1; i++) {
9 _! G, v' |5 \7 r; `7 D4 P2 c1 b            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
# y6 M, T/ l' }% W) f                temp = arr;
+ B' I( r) u6 H% T( b% b4 G3 z                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
" X3 P, B  f# Q4 E# [0 T        }
, c3 Z' }, q3 m+ r, l$ @

9 n( X: r" t) y: F        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
# y: a; n9 s, R. \            if (arr > arr[i+1]) {
                temp = arr;
' ?( F0 ]& Q& ^( j7 L                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
  t8 Y6 ^% a9 y& I' H: ]        }
7 p: Z) s) W. C
# Y, E0 v4 t' s( k' Q
        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
4 o8 C1 K: z0 S  F+ r+ o5 f            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
+ d) R5 G+ ~3 W! i        }
! Y( R7 Y, L0 V/ }4 U

        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
1 [3 p5 H" H9 r                temp = arr;
9 P5 r6 \" |' P3 h! \1 v. ~& |8 z* ~                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }

! z5 k  O! \% s9 ?7 f0 e) ~' `
        System.out.println("hello " + Arrays.toString(arr));
7 n& }* L+ D- o; E3 K- ]/ H        //------------------------------------------------------------------------------------
' ]8 m$ B  x' g" ]4 {! l: y        //根据上面的观察可以知道了撒，可以再用一套循环解决


# a1 }' ^- E5 C( ]0 q( k. o
! a$ A4 S( C& C' @
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
! t+ R4 w; G) v" y) s* T, A                if (arr > arr[i+1]) {
                    temp = arr;
. Z2 H3 F0 }* P                    arr = arr[i + 1];
8 I0 @; ^5 G: l$ i- Q                    arr[i + 1] = temp;
- ^% y* n9 G' \9 Q( z8 r! S                }
            }
; ^/ u/ g# A$ P& u# G        }
    }
}
% [6 d% {9 I7 e0 l三、冒泡排序的优化

1、思路
如果我们发现在某一糖过程中，没有进行一次交换，提前终止
- Q. c, U$ M0 i2、代码实现

package cn.mldn;
% W. X# k$ \8 F
- w) [, R* ?  p0 t
import java.util.Arrays;
! V9 A' b9 b. I
. ^3 O6 P5 _: e1 B) y
public class BubbleSort {
: C9 b' H/ u$ l: r1 t9 _    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
2 }9 U* i! [" E" {+ D5 Q        //大致过程
; k' f! }' I: }! I        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
; |5 \: k) T: M/ _; v5 D        //                temp = arr;
+ B5 `+ M0 X: `% F3 A# [2 ?$ q4 z1 Y        //                arr = arr[i + 1];
0 H) ?# |; \' {3 D3 b2 k5 s        //                arr[i + 1] = temp;
! ]4 ]( U5 }9 E. i  V1 U$ u! Q        //            }
        //        }
1 d+ k: k0 X8 T" W% _' n3 o% j        //2、第二糖就是把倒数第二大的排到倒数第二位
        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
* O' y2 v& b+ r$ u( e        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
: B6 C" z4 b" k. b  l# _        //                temp = arr;
        //                arr = arr[i + 1];
: x/ i+ q9 {. N/ {        //                arr[i + 1] = temp;
2 [4 b# u: K9 q; I" a6 z1 `# J/ `/ u        //            }
        //        }
/ ]% e* e; N- z' s& _( a; P        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
$ v: a7 |6 [# H6 b9 b' _        //                arr = arr[i + 1];
! x9 [3 q2 R" f) @! j        //                arr[i + 1] = temp;
/ w% y! Y6 v7 K7 R6 L, m$ C        //            }
. h# N2 s0 ]: H& n8 r        //        }
2 k2 o" x. _1 X6 l; N        //4、第四次排序，以此内推
1 `* N. F6 \% w4 ]3 X- r& `        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
6 L: Y  S7 Y" f        //            if (arr > arr[i+1]) {
        //                temp = arr;
0 t4 e$ v# V* c2 A! d        //                arr = arr[i + 1];
' A/ P5 R/ x3 q& i        //                arr[i + 1] = temp;
: P$ E1 R$ B# Z5 b        //            }
        //        }
        /*int temp = 0;//零时变量，用来将最大的数值排在最后
+ M8 r+ @$ \3 A8 f8 C" y        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
+ M0 Z( A. f8 d2 p( x/ F, R# C) e            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
, J$ ?7 J- D- G9 Q            }
+ a* g# {- g" J9 E; F; g        }
+ D! \' D2 M/ @# E! g* J) a- m: h- c
1 q7 b& ?$ {# {& L8 t
7 Z$ R) Y" ^% M' m4 M" E0 H; f        for (int i = 0; i < arr.length - 1 - 1; i++) {
9 [/ H& P; c2 K: s, z5 h; T. t            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
# \; }* n- Q' J- e! c) e# Z                arr = arr[i + 1];
9 s/ r6 v4 }6 B' e& v5 Z                arr[i + 1] = temp;
            }
        }


        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
5 t* C! C7 X4 P$ K            //如果前面的数比后面的数大，则交换
3 @% l0 {( Q9 f; V' I9 W* t: ^            if (arr > arr[i+1]) {
6 I' J0 C4 g& B4 a                temp = arr;
4 {7 V" D3 c4 w+ b) {                arr = arr[i + 1];
# p) o) R* B2 O) V. [+ e) u                arr[i + 1] = temp;
, p$ j# S8 N8 I: d            }
+ e7 i5 L1 j+ D9 X6 E; V" |$ L        }


, B5 K' W( I0 o6 f& J) v2 K! C( ^        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
$ H4 s8 o" S- z/ z4 m9 H                arr[i + 1] = temp;
6 {9 r& }$ F, V% I            }
2 P3 W* [: c. }        }*/


        System.out.println("hello " + Arrays.toString(arr));
1 t2 I0 N8 Y+ N/ x: h        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
1 b6 P7 ?5 b) Q7 j( i


7 _5 L' Y/ g" [* h


! \0 v- U5 H* p  {6 C  O        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
  I* O, \: a  v        int temp = 0;
$ C1 H2 `4 _) L6 G/ y

7 u& |) k5 D2 N9 j7 F        boolean flag = false;
$ f/ Z; p( |% f        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
" l- t/ T% y3 Z3 J) i4 [                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
( ^/ U& F2 p# j# o, x                }
            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
1 L0 T7 R5 C) B            } else {
) }1 x; V8 }" t* b7 L1 I                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
. Y3 S% J' S# k: o8 F$ t" l$ `8 z; k
3 }, y. K# H0 h) U
        System.out.println("world " + Arrays.toString(arr));
" `( l3 a# w$ X8 r    }
}
0 l# {5 v! i0 O8 v6 B四、将上面的代码封装为一个方法
, O$ V4 y! }3 z2 J4 y7 c/ H. X& opublic class BubbleSort {
    public static void main(String[] args) {
3 ?9 x0 a( ]- W2 V        int[] arr = {3,9,-1,10,-2};

" D" s. F5 o+ D2 s$ w1 ]
        bubbleSort(arr);
        System.out.println("world " + Arrays.toString(arr));
    }

' E0 w$ Y* Z* R7 R
    public static void bubbleSort(int[] arr) {
. t7 |+ j* b( Q" \# |        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
0 [; B6 e4 u9 [; A9 a/ }; m$ m' V        int temp = 0;
( l4 f# y5 ^: p. t( h1 U1 K" _

        boolean flag = false;
* Z, Y4 g4 t8 c9 [2 E        for (int j = 0; j < arr.length - 1; j++) {
( H1 V' f+ M& m            for (int i = 0; i < arr.length - 1 - j; i++) {
  r, F3 q! L) \; G% I                //如果前面的数比后面的数大，则交换
) f! M# r7 T  M4 U                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
; _& `1 g. b9 o2 O" k                    temp = arr;
: b4 i# B! [/ Z) `                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
: k" w' w5 n3 i8 h3 u% w! d            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
* i0 K& c! T5 O* r; k% H! `, A                break;
            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
- G: g, x6 `1 Y            }
- A. c7 E# F4 a5 e: m4 ?        }
    }
}
8 E% n" d- z4 |+ O% d五、测试一下冒泡排序的时间复杂度

1、代码是实现

import java.text.SimpleDateFormat;
5 o1 E1 ^! K" K+ m# C+ himport java.util.Arrays;
% T" o8 N9 B8 R! H+ Dimport java.util.Date;

  w% C/ U8 I" G' b
public class BubbleSort {
    public static void main(String[] args) {
        //1、创建80000个数据来测试一下我们的性能
; U8 K0 y. [% `. N' _/ x        int[] arr = new int[80000];
# v( x/ D; X- L2 T        for (int i = 0; i < 80000; i++) {
            arr = (int)(Math.random()*80000);//生成0到80000的数
        }
        //2、输出时间
        Date date1 = new Date();
, X' V" e/ A6 B5 i        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
  ?5 g1 p6 E6 O        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间" + date1Str);
! i* ?0 L) F2 }6 g% e) b- W        bubbleSort(arr);
6 u) D. r, R4 T6 F0 [        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
2 h3 E6 `# a3 I        System.out.println("排序后的时间" + date2Str);
' g( j$ m8 G8 L, M* w
. t- x% A8 H8 E3 u
: \' P% `, Z8 R8 Y

    }

+ s' r, M4 w% m! L1 k$ c4 S
( k7 R& a  J$ D    public static void bubbleSort(int[] arr) {
' h6 n% S. w4 j5 d- |5 z# O4 v        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;
! w$ {2 E. o: c. W  N: [

/ L9 y/ I% y/ O. U+ c        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
& }, ^  f- X0 j% k. Q8 o. [            for (int i = 0; i < arr.length - 1 - j; i++) {
% d4 C2 m/ d- J0 i  e3 D; j                //如果前面的数比后面的数大，则交换
; V- _0 `4 h% S                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
/ ~: e: J% o' S6 S                    temp = arr;
( ]# r* B/ L. R/ N/ J, S# u" [& n7 E                    arr = arr[i + 1];
                    arr[i + 1] = temp;
! R( c7 W7 S' }' X1 C9 |                }
            }
: [1 Q- ~) d/ }. Z, ~* R            //在内部循环的时候进行查询
6 M& [- [& r' g5 J4 g            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
6 b+ L( R# K, ^- ~" }2 W+ r                break;
            } else {
2 y: ~# l; W) h" R: b5 `# |- W                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
3 K4 r- A( c. ^  j            }
! B! T0 z) K( B9 q0 L        }
! t" |4 W2 ~9 k8 l# F4 n: [    }
/ p4 X6 @6 v4 y% k) Y' T}
9 f, ?6 b* Q+ c' J


& a- H- u( A8 j1 _$ h( `3 T& [2、效果
" k, [) c: [: s- c4 S6 e2 _0 }
: h( M  \: c9 J8 K6 C
* ^8 J7 @  l; Q2 y4 y% u

470557092

顶。。。。。。