排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
了解冒泡排序是什么！
+ N6 R/ c2 R8 ?- I+ f知道冒泡排序的思路
知道实例代码并且练习
0 \6 x9 U. t3 }有收获记得帮忙点个赞，有问题请指出。
一、冒泡排序基本介绍
1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。


; N3 y, _- o( h3 i4 v4 J2、冒泡排序的优化思路
5 b7 G& R4 Q2 Z5 w- F3 S, i% I因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。


3、冒泡排序的图解思路

! r6 u1 r: M" a2 ]
其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：

1 \. |+ s( Y" d0 T
第一轮循环得到最大值
& ^( ?1 u" g, E/ F第二轮循环得到第二大值
第三轮循环得到第三大值
5 m2 V: V( ?0 m8 e8 `2 f第四轮循环得到第四大值
1 k' e: P' S- G6 i总的要进行数组大小减1的词循环


8 V9 k3 Y; |7 P1 ?$ a! c二、冒泡排序代码实现package cn.mldn;
1 ?3 u2 |; a$ J9 ]& j
; q+ a8 F1 d3 \
, [6 X6 {  Z/ G3 O) y) Bimport java.util.Arrays;


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++) {
. V3 T) A% h, ?5 |! F+ {8 |- \# l0 H        //            //如果前面的数比后面的数大，则交换
1 O& g/ A+ E6 B        //            if (arr > arr[i+1]) {
# X, c0 Q7 r9 s) E" w7 E, @9 e( d        //                temp = arr;
        //                arr = arr[i + 1];
! K4 Y# y, {! ^, a& m6 ^        //                arr[i + 1] = temp;
        //            }
        //        }
/ B) x9 U% n/ x& ]3 m8 x        //2、第二糖就是把倒数第二大的排到倒数第二位
# Y: c, T  G9 A+ w4 [4 b% \% [        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
( c& L0 y" a9 W% f$ q& P        //            if (arr > arr[i+1]) {
2 G8 k  O+ n7 h% u1 c) ^8 T        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
        //3、第三糖排序，以此内推
7 x1 Q; T: |1 K  b% _) W9 M+ z* d        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
8 m% N' @9 z% ^! h! T6 v/ ^: ^        //            //如果前面的数比后面的数大，则交换
  c2 N0 |) O  h, T        //            if (arr > arr[i+1]) {
3 N' R1 ?* H1 |4 u! v6 @5 K7 O        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
, `+ ~  a( A3 i5 R1 P        //            }
        //        }
        //4、第四次排序，以此内推
/ E2 R1 s- E! p# [4 J- U. w/ d, V        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
9 u5 Q, x- Q; A% n6 z        //            //如果前面的数比后面的数大，则交换
; G; V8 F, d- _1 ^/ \3 T/ S0 y. j        //            if (arr > arr[i+1]) {
# Y6 U  Q/ b* P5 x" [        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
" |4 V. o# o2 P$ y        //        }
% n& @) c! U; S. j        int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
; I: ]3 c' \2 s: S            if (arr > arr[i+1]) {
                temp = arr;
2 r8 j$ X' s  H                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }


        for (int i = 0; i < arr.length - 1 - 1; i++) {
$ j% n5 r/ R! Y" v$ x6 ]            //如果前面的数比后面的数大，则交换
# _. E2 B% k. `. x$ _            if (arr > arr[i+1]) {
                temp = arr;
, I) X. m1 m, t/ g! [6 v6 \7 ]                arr = arr[i + 1];
                arr[i + 1] = temp;
9 X; j, p, d  Y" K            }
        }


# N3 U. h4 e2 _! B. k/ f* c6 `        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
$ l# F0 `. R, A) {; M                arr = arr[i + 1];
9 q" O- ], \) B2 H5 y                arr[i + 1] = temp;
& W6 t* x% \2 j% E* X9 L            }
        }
! v7 e+ y9 F5 ]/ k8 X* j* d
6 t! E, _7 `4 @/ ?3 Y% C
0 i0 o7 ^7 j: `- h8 n6 W0 J+ K        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
3 \4 W0 s, ~/ ~  d- e: z" u            if (arr > arr[i+1]) {
                temp = arr;
- y7 ?4 U4 x. Q* S% h$ D, Q( h                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
8 }5 Q" S1 l/ v$ V6 {- h        }

7 p) A& M9 R; [: B- V
        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
/ {" G( z3 q. H, v0 a" Y7 T        //根据上面的观察可以知道了撒，可以再用一套循环解决

+ T3 D% Z" D+ n
. |# G) h# R1 e6 x
+ a; f. `; w" a
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
% A) l2 P3 f' j5 U0 o- L: u  U            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
( t* c1 ~( L2 w4 J* V( J, h, L! P            }
* i6 L/ l3 I& h# ^1 k        }
# v. r9 @9 G) i    }
}
0 x% g- }( _& @) f  @三、冒泡排序的优化

1、思路
8 \" T0 W) {3 f' J! l; |; y如果我们发现在某一糖过程中，没有进行一次交换，提前终止
) ]. m+ c0 X+ t, ]2、代码实现

package cn.mldn;
1 H2 x/ P8 {) J* s
5 q& n5 p* L2 g3 U2 p: [1 G
import java.util.Arrays;

* K# `5 t9 u- C$ `! l  e
' E- \$ s+ U  a4 Bpublic class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
, ~: ?) b9 Y% E& n6 a: [, M8 n        //大致过程
4 x% L! _2 O1 I; \7 n        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
+ w* y0 K0 A5 y: g) z        //            if (arr > arr[i+1]) {
        //                temp = arr;
8 \  K4 z4 L3 V, l! H! K( b+ z# S        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
, d" V, \4 D) W9 `7 ^# a2 N, i. R        //            }
4 n! q6 J# f( M, c2 `8 A9 W' Y        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
: S3 q" E- O6 Z        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
- W% D% \& ]1 w* n2 q( Y4 n" {        //                temp = arr;
/ D+ ?7 E" y  a        //                arr = arr[i + 1];
: T' N% q9 Z, @  j. i7 X1 _        //                arr[i + 1] = temp;
! d8 t0 k. W1 g% g/ B( U! H        //            }
        //        }
& o5 O0 l' Z# w        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
9 s: I0 p1 J( D! q9 h" [        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
5 J8 S# H5 @; g  ~) @9 O        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
6 N! m1 J+ [* ]8 q2 ?8 Y' d        //            }
        //        }
, Z% {* k* Q3 k        //4、第四次排序，以此内推
4 }; h" k+ x: y7 W4 P  B% J        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
5 T7 e* }2 z8 j0 {& Y        //            //如果前面的数比后面的数大，则交换
: O% }) c. D' B; K/ c6 ^" W        //            if (arr > arr[i+1]) {
        //                temp = arr;
" `2 l0 D* Q4 D        //                arr = arr[i + 1];
' t2 A! ]% O0 }  p        //                arr[i + 1] = temp;
0 l2 P7 @" Z2 B" S& ~7 _        //            }
, @' j3 k! P+ ^& ~! V        //        }
; g' d- J% V- [5 k1 z% R" d0 [        /*int temp = 0;//零时变量，用来将最大的数值排在最后
! {: n; r- ?. J6 q" W5 C, ~        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
$ ~9 g3 d5 i4 a" j- |2 }6 b8 v' J                temp = arr;
. l/ n# W' n8 r  n# r                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
4 S8 x# |( C+ ~$ k8 w6 E5 e        }

' `4 N/ J) Y- n9 P  C- b; R/ f
1 z4 D2 r) j7 h! n- c6 E$ C9 o        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
, J8 M% \' y' f, v: ~                temp = arr;
                arr = arr[i + 1];
* Q- x' z5 S$ ]1 d8 y& n* R# E                arr[i + 1] = temp;
7 w* e9 i. n, T$ W& H5 j% \2 t            }
, E8 B* |$ u$ ]0 B8 Z1 x% {        }


: ~* B9 V7 p: ^4 E! _1 v, B        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
9 i1 p# i* R1 p4 h9 ^                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
( L1 W& y4 I8 j+ H        }
5 U4 `8 n* S1 r6 F6 C4 q) J  ]
8 D$ E8 P6 x+ Y7 e3 g( E" K; s& S6 W0 c
        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
4 F7 A) q" t/ y! p$ X. X8 C            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
; n/ {/ w8 l( a8 E                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
, |# T% q, \. n0 S! [6 Y            }
        }*/

' S$ e! j/ O) e: \; T# i6 a4 h
        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决
2 X7 H8 s) i0 `: s; k8 x




" p2 ]4 w: g* ^' z0 t' n
3 E$ a# R  o: u# l        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
1 q1 X( P: n4 k4 T0 e* @        int temp = 0;
7 V, e  S6 f! n& A+ j
0 p+ W* p3 K# l/ x6 v0 P) N
& }3 n1 ^9 b* ~$ @2 h" q" A        boolean flag = false;
1 h: ?/ ^  ^' ^* ~# j        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
  g2 `6 `! G4 ^' p) c                    temp = arr;
                    arr = arr[i + 1];
% D7 C8 q1 j  b. j* q1 t                    arr[i + 1] = temp;
. C4 W. E6 W7 t3 t; f                }
            }
            //在内部循环的时候进行查询
9 G+ `$ i; O$ E7 q: E, F            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
4 o6 `" g1 b, e! Z            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
; p+ K/ ]3 K  q, [            }
        }
% R! t# h* }4 Q" x; N- I, n. Q6 y
9 O' U' W  Q( l4 z+ Q2 p
        System.out.println("world " + Arrays.toString(arr));
. m% e/ p& d3 W- J( x: U    }
8 @) B. P) ]7 p9 n}
四、将上面的代码封装为一个方法
, K/ L8 \* ?, \  }: L9 }public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
1 _% I4 K4 P/ F! W7 D( R

5 ?$ Z, t3 _% o; _% W8 B        bubbleSort(arr);
        System.out.println("world " + Arrays.toString(arr));
- U0 ]% G/ L6 n. i- a    }
) c: g8 C8 D+ R& {
, I" e+ e- b. h6 ?- y4 W, Q
    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;
0 ?  @. k  O- ?  J: w

        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
/ E2 E# D5 \7 Z0 M( V                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
& I" i! x; k( Y% \8 ~                    flag = true;//在这里把flag值为true
9 G1 h% R) w) b- y* ?2 c) C4 ~                    temp = arr;
                    arr = arr[i + 1];
. i$ R# O) J4 k                    arr[i + 1] = temp;
                }
            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
- Q! r) B) g9 W; y                break;
            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
) Y8 @" ?) f7 m            }
+ j, m! Y: e) G        }
    }
}
( T( n: m2 z$ F- {3 [0 V, t五、测试一下冒泡排序的时间复杂度

1、代码是实现

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

/ l, b: d) k; G! L1 _+ j6 P
) Y7 t1 M0 x: d' E' {& w7 Cpublic class BubbleSort {
    public static void main(String[] args) {
        //1、创建80000个数据来测试一下我们的性能
4 \0 I' {+ x( f: H: j7 w  L        int[] arr = new int[80000];
( ~. z( o% F( e1 p0 d% C, I! V: `        for (int i = 0; i < 80000; i++) {
0 q2 T! f: q1 a  H2 S) j2 R            arr = (int)(Math.random()*80000);//生成0到80000的数
        }
0 E" }, r1 r) h; W/ q0 _" H        //2、输出时间
        Date date1 = new Date();
# h6 j7 n5 D1 k; O6 s0 h        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
. }& J3 P( w: h5 v- i        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间" + date1Str);
% @  b7 c* C( l4 z9 \9 @6 Q        bubbleSort(arr);
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
% S  _7 K- `9 v6 a6 S        System.out.println("排序后的时间" + date2Str);

1 v/ h7 h+ ~6 L% }5 i7 C
: w; `  f; e! H# r2 V& D/ w/ F$ m

' l( ?6 k; n8 n8 H: c8 u    }
( \/ p/ R% w# N) B$ A, p- |

    public static void bubbleSort(int[] arr) {
6 @6 H' B+ r! c- m        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;


! I/ b& u( ~, X+ I- s% ?8 K5 f4 M        boolean flag = false;
" m7 @+ P" ?( I! C' O8 v# m        for (int j = 0; j < arr.length - 1; j++) {
+ P+ c( H5 x" R! B; W            for (int i = 0; i < arr.length - 1 - j; i++) {
% Q- M. W- O% O3 A2 `! G3 r+ N                //如果前面的数比后面的数大，则交换
( @7 C" k% N% X. |) Q- n2 z                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
9 K3 m! G+ Q, L/ A9 T                    temp = arr;
. x, B0 y6 d  h, Q, G                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
  G0 D6 N' A* Q# n) u1 F            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
- V- s8 T: F3 V  K. B  i, ?                break;
6 q; A, @) |; Q4 E            } else {
  v# y4 m. w; }                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
9 w( M" d) \/ ]5 h/ e! |4 }! V    }
( N: K8 Y& [# m/ h: v}


( t7 N! n* w* ~% J9 y6 r7 _! d2 Z
2、效果
7 d; ?3 W9 p0 Y$ n( w

7 {9 D$ ]0 F) X, V

2 L( \8 l1 u! _! X0 `% ~

470557092

顶。。。。。。
, g6 D. ]2 ^9 K% k( T
/ N5 [: \$ \9 k/ q! R5 I$ L