排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
了解冒泡排序是什么！
9 C4 I4 {) l9 t3 v& W知道冒泡排序的思路
知道实例代码并且练习
有收获记得帮忙点个赞，有问题请指出。
/ A! @. z3 p! J一、冒泡排序基本介绍
0 X/ ^) A3 h1 x/ E1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。


2、冒泡排序的优化思路
# c2 [$ Z% G, E0 L/ ^因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。
: k* E" f. U  F  k4 t8 a1 f# u' r

/ }- W& d8 R* g" q' h3 t3、冒泡排序的图解思路

, `% S+ s" ]3 z  D6 S8 _
( I) w- _( o/ D4 V2 ~其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：


7 s+ L' c2 L$ j' c" a+ E第一轮循环得到最大值
第二轮循环得到第二大值
# @! m3 H9 y: Q4 y5 O/ @第三轮循环得到第三大值
第四轮循环得到第四大值
总的要进行数组大小减1的词循环


% v, a! ~1 d: X( l  i. K二、冒泡排序代码实现package cn.mldn;
  H; a% ]. V$ L, Z2 f/ [) `( S- ?
" V/ m: s, q  p$ Q6 a& b' J5 G
import java.util.Arrays;
# a. ?$ b$ w- ]
( H9 ]& w4 ?. x+ R2 J9 x' \7 H
public class BubbleSort {
; A8 O2 `' @& i9 |9 m$ U, j    public static void main(String[] args) {
( ^5 z  |) B- y" B! C) D0 Y        int[] arr = {3,9,-1,10,-2};
        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
0 B+ N, Z: l# G3 X        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
7 ?+ U, N, k, `+ T1 q0 O- V        //                temp = arr;
9 G: q; X# E8 Y4 x5 g        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
$ i2 d& F. V, B9 z$ I- [/ ~        //2、第二糖就是把倒数第二大的排到倒数第二位
. l9 B# a, D! d8 j) V; U& v6 A. Y        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
- z7 s8 L+ Y2 d' b        //                temp = arr;
. t0 O9 ~1 D: z        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
  B' W) R4 P# c; b* r% @        //3、第三糖排序，以此内推
: j$ Q/ G6 {: O' s        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
% e3 ?8 S" V, i* ]' y        //            //如果前面的数比后面的数大，则交换
5 D, r' L' X4 l3 j8 ~+ |" z: ^        //            if (arr > arr[i+1]) {
        //                temp = arr;
* \& P3 V! m* m$ `' g5 S# q        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
) e- G8 c4 [$ J" |0 f4 N        //        }
        //4、第四次排序，以此内推
! M7 K9 X4 G. Z: U$ U7 Q, w  u( M; l        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
3 u! m+ ?. _0 \# L5 [  a        //                temp = arr;
1 s$ N5 [9 l' S4 U8 v        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
4 K' t; u. Y+ D. E' b        //            }
) |! ^( G* @/ G/ i! ?3 f        //        }
' X4 P2 N+ I% p) j& X        int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
2 J1 b2 [0 G4 Z: C2 S& f            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
& R( T( q8 }: S4 Z' X3 M        }
) b+ f3 t- ?# I) [/ P+ Q
! ^! @0 @! ]" T% g6 y- |+ r
! S! @" y& D4 X7 o( t        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
. ~  x! [: |8 N$ P& s% x+ U+ z                temp = arr;
3 ~/ s0 u% G* `; z" I2 I& ]- Y                arr = arr[i + 1];
                arr[i + 1] = temp;
  V+ f) L3 W# `$ c: s0 T            }
        }
# N: k; ?4 M! k9 v1 ]
7 E! V$ D$ Q$ Y4 k# |
        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
  Q5 w) \9 \4 x0 Y. V; P            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
6 q1 s  v  r- i                arr = arr[i + 1];
+ X  y; P* T/ Z/ E8 Y+ j                arr[i + 1] = temp;
/ K" W6 A: o! l  H            }
        }


' p, I( g6 q* Z        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
+ `& N* W7 o* @/ j- T1 v& E                arr = arr[i + 1];
0 B" `( M7 F# `' V7 b- x                arr[i + 1] = temp;
            }
        }
9 {. V$ z" t; D6 I3 C
# X' r+ Z* |  l9 t- V" y
        System.out.println("hello " + Arrays.toString(arr));
# G+ R# [( F1 b  Z6 r: }. S        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决

) ~; h8 P6 {0 S: }
, ?# L0 S2 P( \

        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
7 O/ M9 W7 K' D' ~# g$ w" d5 X                //如果前面的数比后面的数大，则交换
  @" e. v) a6 K3 T# N; |                if (arr > arr[i+1]) {
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
7 L2 J3 j- i5 h/ w) x" P                }
& W9 n6 C9 @2 m' C6 E1 d6 i. _% s7 f            }
        }
    }
' D$ o6 ?  b& H9 W) G, F}
三、冒泡排序的优化

1、思路
如果我们发现在某一糖过程中，没有进行一次交换，提前终止
- ^# [, O- ^" J; e. T2、代码实现

package cn.mldn;


- g" j3 R6 ]) v( j) vimport java.util.Arrays;

$ R  l3 ~* Q* b3 Z1 {1 u
public class BubbleSort {
8 [3 B, c$ o& n3 m* E3 R9 ^0 f2 ^    public static void main(String[] args) {
# N$ r1 f' k7 c7 v- H2 R2 u        int[] arr = {3,9,-1,10,-2};
        //大致过程
1 j: d) z/ m  T% q        //1、第一步就是第一轮排序得到最大值于最后
: M& {* \0 w" N2 c9 Z, |6 d" t        //  for (int i = 0; i < arr.length - ; i++) {
/ ?$ p9 q# Y' H% {0 J- h/ N        //            //如果前面的数比后面的数大，则交换
; E+ k  x. T; c, @; b        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
  j& m" n  |* U, `( j        //        }
2 ^! J. |5 n3 o) U1 @: V        //2、第二糖就是把倒数第二大的排到倒数第二位
9 W& u) K1 W) i. k; W, [        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
$ G) e0 i+ r6 n( P4 B        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
/ H5 c& S" Q8 |* X5 b$ V        //                temp = arr;
        //                arr = arr[i + 1];
/ ^) C" Q$ R6 G  y$ C/ A        //                arr[i + 1] = temp;
0 W$ @$ I7 m: B" @/ ]        //            }
% w1 x9 B. X! c7 W# E2 d: y        //        }
9 K2 x; n; S% _0 m        //3、第三糖排序，以此内推
1 }& V% ?4 C  I: Z        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
1 W) M1 `+ W% a5 v" u( ^! |6 _" O: O0 s4 \        //                arr[i + 1] = temp;
1 H7 |% t% u/ _- R' Z0 N        //            }
        //        }
* l, q. J! {* v  g, R        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
        //            //如果前面的数比后面的数大，则交换
: g  E) h. q* m; k        //            if (arr > arr[i+1]) {
        //                temp = arr;
, j. |2 t0 S, W, c! k( u0 `: p        //                arr = arr[i + 1];
9 P# e7 j! h$ V6 V; v, a        //                arr[i + 1] = temp;
! h* @0 W! M4 X/ M+ }5 s9 o+ M6 A5 A        //            }
/ n+ \$ J# w6 j, N- ^' ~5 m: G, C        //        }
        /*int temp = 0;//零时变量，用来将最大的数值排在最后
/ ^0 J! @7 ^- g% E' r5 U( _, Q$ I        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
! P, a9 R3 Y9 C                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
/ N. w6 m+ J+ _7 W# V3 z$ r            }
        }
3 v. `2 f. g+ v- n5 r
. q) C2 y, Z7 s0 m) h: C# `# G
        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
) l/ k( E) O* G* y& V                temp = arr;
                arr = arr[i + 1];
/ V: @$ B! H9 T5 W                arr[i + 1] = temp;
            }
; E; l4 z: h. a' q6 ~' A7 K        }
4 S& @6 l& k; `& P( D. \1 r* z! b
$ G' |& T% m- A% R2 o7 ?
        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;
            }
        }
9 [* _- }4 v0 y6 G3 g9 i
* Y/ ~2 H& N$ s5 @$ l
  m5 z2 X' ]) @        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
3 l  |: U& n- _! e2 ]% B( r  L            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
% R( o0 U; g- f: B                temp = arr;
2 G1 g8 _1 M" B* t: _                arr = arr[i + 1];
! ]% N) i1 S9 W8 F2 P5 Y' n                arr[i + 1] = temp;
- j" S0 G/ [$ d1 x            }
! `% U0 {  D4 F5 P        }*/
! S! v$ J6 m1 Y

/ n: G& K- z7 E        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
! }% a) N: z" M' p; v0 `        //根据上面的观察可以知道了撒，可以再用一套循环解决
' Z. Y4 `7 }6 {/ z6 \5 e

, r0 q0 D+ K0 Y. Y3 |# l+ Y. o

) D. l7 z; M- G! v. Y/ H

! h. @6 o' k9 L, x7 i# e        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
3 I* ?+ K' c; a+ c        int temp = 0;
/ N1 x8 d5 c6 K7 V! W8 c$ w/ |1 f3 O
) k' R$ q, f0 K! v
. W: [8 k* }# u* k        boolean flag = false;
* i  U7 t: w1 ~- t$ g6 m        for (int j = 0; j < arr.length - 1; j++) {
  l6 B' I5 A9 D9 |            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
* d$ X2 }1 O8 w# O/ V' ]                if (arr > arr[i+1]) {
% Z( {2 h( B" o                    flag = true;//在这里把flag值为true
1 J: K$ R5 ?. ]$ g                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
6 w/ c8 C) d( {, o$ I4 S# q                }
            }
+ \. v) P# T; t9 J) [            //在内部循环的时候进行查询
" i8 S3 K9 Q2 N+ a3 T0 P6 M- T            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
/ S2 ]) n3 g9 o4 ^4 i$ x            } else {
4 Y4 Q' f+ I& ~  I: t6 `                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
+ u0 A* j" ^3 c% a$ W5 q( e) m            }
8 u3 _. ^6 f/ {% U# I        }
% }9 o! }) y. X7 A0 g, e
" s1 O# t2 w$ H* |
$ k  K# p; e& }) o9 p, `1 F' |2 g        System.out.println("world " + Arrays.toString(arr));
4 M5 v1 z! g# U9 X) ?4 s3 m    }
) l" S  O3 T/ Y) J( ]$ L4 Q' [3 y}
四、将上面的代码封装为一个方法
0 B9 N' k0 j# [  }3 A* ipublic class BubbleSort {
! u7 @0 q/ }9 ], I3 X/ v. B    public static void main(String[] args) {
2 I+ z: y2 a( s  ^        int[] arr = {3,9,-1,10,-2};
; F4 h  V! B1 d- |% y$ D
6 W# B9 M- ~- z" ~& p$ o
& m7 v8 ]# h, r: ]( {# U1 C        bubbleSort(arr);
2 l/ T! T3 g5 Q% E2 l# J        System.out.println("world " + Arrays.toString(arr));
/ k" s1 g7 Q% h% D0 Z7 M    }

0 E* ^- @* _4 n+ P9 ?+ A
1 H% q2 r$ n5 k% {6 T    public static void bubbleSort(int[] arr) {
% b3 B$ ]9 E: q( [  k8 h        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;


        boolean flag = false;
) d; O$ m/ u, y        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
1 F3 E) C8 U6 l1 _5 h                if (arr > arr[i+1]) {
! H2 F( C% M+ }7 B0 f3 n5 ?3 k+ g                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
) j) ^1 |0 y! G" N& Q                }
            }
% |' Q5 P, d1 v- E- U% N            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
* d/ Z) P3 ^: c# L' ~            } else {
6 R# s5 }1 L3 x9 t9 D! q1 g                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
* s# @# d) o: f: }    }
# V  T7 h% b& y2 U. }}
) |/ N9 q5 {* c五、测试一下冒泡排序的时间复杂度

1、代码是实现

import java.text.SimpleDateFormat;
$ M: T0 g/ k* x9 M' L: R' wimport java.util.Arrays;
import java.util.Date;


public class BubbleSort {
    public static void main(String[] args) {
        //1、创建80000个数据来测试一下我们的性能
! _- k* P) P. L        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr = (int)(Math.random()*80000);//生成0到80000的数
( N, l' M+ P" P- B  u        }
6 V# H* D5 @! A+ v+ y$ W0 t        //2、输出时间
% X- l: x7 ^; n        Date date1 = new Date();
5 q/ P# Q' }+ O! X3 X2 b1 j# F6 }# \        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间" + date1Str);
1 B/ H& E9 M; L, n- W        bubbleSort(arr);
  Y& j2 L7 d& {* u& @6 Q& y        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
9 p3 \% c' m, S7 X) z        System.out.println("排序后的时间" + date2Str);
/ O; P$ t( q. N2 o7 \0 o4 T' d



+ m9 P: c$ a* A* h' m    }
) f! X+ c; R$ f0 P5 B

: {8 h. w& B6 o, S+ }+ Z7 t+ W    public static void bubbleSort(int[] arr) {
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;


$ l: ^( X5 L3 `  [/ ^3 W/ b- s# ]        boolean flag = false;
: j2 U9 e6 a, F$ B6 j, T; e: W8 g+ ]        for (int j = 0; j < arr.length - 1; j++) {
+ A3 V% i6 d* R( o+ r3 m8 ]( _            for (int i = 0; i < arr.length - 1 - j; i++) {
! l# h# O! C2 W& ]                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
$ b* w" h+ L! ?5 U7 W                    flag = true;//在这里把flag值为true
' q8 m: u/ p  u& ^+ s                    temp = arr;
1 m1 W* ~5 z+ j% z  Z2 @+ @4 Z7 R                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
: Y. j* l2 E5 Q3 G. K3 o) e6 R            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
5 F, l" @' C5 Z0 k% Z) K                break;
: e& `6 k% Y  p9 G            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
    }
" V! v& X0 `( C6 q7 X* {5 p4 k: V}

( q1 ~. Q) p" N  j- c8 a
9 n8 S' z3 g) I2 f& ]. H: i% x, t
2、效果

, B+ Q) W& x6 _8 p0 d5 y) k

  L6 |6 a# f3 r0 ~1 {

470557092

顶。。。。。。

" I. D7 K' q4 J! l" d! G