排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
了解冒泡排序是什么！
知道冒泡排序的思路
知道实例代码并且练习
) O- f# q) O2 x7 ~, Q" x1 `5 [, B有收获记得帮忙点个赞，有问题请指出。
8 p3 y9 T" q( K* q一、冒泡排序基本介绍
5 L6 A7 k# O6 e3 Y  P+ Z1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。
2 e1 v' Q% P% U1 {4 I

2、冒泡排序的优化思路
8 N# i5 h$ ~" [) _5 A0 ]- l因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。
- b+ i* E9 t" Y" w# x
6 B) b+ i8 {4 c/ p& N2 T
  z: B1 p7 H+ l3、冒泡排序的图解思路
5 g) X- Z( i7 {; e1 s6 {: E" r
( g$ w) V; [" G
其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：


# S8 Z+ Z0 }8 s" S  |第一轮循环得到最大值
第二轮循环得到第二大值
8 f4 f, y! D) w$ B4 V0 S# R* i第三轮循环得到第三大值
第四轮循环得到第四大值
总的要进行数组大小减1的词循环
2 q" s  V" j' b6 L/ y
/ W) P/ ~# M, y# e8 d
二、冒泡排序代码实现package cn.mldn;

* @: @! C  R, v: ~. v- R
( E* _& q* t5 D+ ]* |# j4 I9 {import java.util.Arrays;
9 M$ b2 a7 S+ F( D. W* g. k7 E
" L4 w# ]+ y* y7 l1 W, k
public class BubbleSort {
    public static void main(String[] args) {
. [2 m1 m0 J( ^/ m. ]& T9 L9 h        int[] arr = {3,9,-1,10,-2};
        //大致过程
# _% k5 L; u2 x: o  J- T7 P        //1、第一步就是第一轮排序得到最大值于最后
: v! [6 z! C' Q# n4 P. [        //  for (int i = 0; i < arr.length - ; i++) {
: w' G  r) v# J# ~- U( M! h& ^" ]% ?        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
1 e5 N4 f* [2 |( r        //                arr[i + 1] = temp;
0 g$ }) K$ A( ^" z2 ^7 h        //            }
        //        }
" A5 d2 O% g, Y2 z; M        //2、第二糖就是把倒数第二大的排到倒数第二位
# ^6 K/ f, A0 G7 H" _        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
+ Z) n; S7 Z2 v: O" }2 C' T        //            //如果前面的数比后面的数大，则交换
2 t$ t6 |3 F7 C) K- [        //            if (arr > arr[i+1]) {
        //                temp = arr;
$ o4 p8 ]* @6 _* u8 n' m8 W        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
/ B/ `/ I/ W$ Y3 G5 [        //                arr[i + 1] = temp;
# k  i/ j5 B8 P$ P  d        //            }
        //        }
        //4、第四次排序，以此内推
- L/ b& ~  o% F; C: Y3 K" d# S        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
* g$ W* e& ^% p8 B# a0 V        //            //如果前面的数比后面的数大，则交换
  ~$ B7 X9 R) E6 H        //            if (arr > arr[i+1]) {
4 Q0 i& z5 j$ x# e2 S* V% r% m4 C/ ]        //                temp = arr;
2 z7 t( E8 `0 Q1 R; U2 Z9 R5 R        //                arr = arr[i + 1];
0 V' o/ F- A; \, ]5 b+ Q) _        //                arr[i + 1] = temp;
, b3 f  x( \6 y7 q2 A: g/ ^! @        //            }
        //        }
        int temp = 0;//零时变量，用来将最大的数值排在最后
! T4 s5 G; ?/ k/ O, S        for (int i = 0; i < arr.length - 1; i++) {
0 D( ^) j' F7 n8 P+ f' l            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
" q- W* k) E- W+ C9 j; @                temp = arr;
                arr = arr[i + 1];
2 z: Y) @. L# T& O/ C                arr[i + 1] = temp;
            }
        }


        for (int i = 0; i < arr.length - 1 - 1; i++) {
9 g  P; C4 G, u4 }            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
$ |1 q4 w) }& [8 y- ~                temp = arr;
' p4 J8 s) Z) v, W5 L                arr = arr[i + 1];
* y. ^6 `4 Y" O- m, x4 M# P                arr[i + 1] = temp;
% t3 J! g8 ~) R6 `1 P/ x/ s' r            }
* I# ~' x# L0 k        }

% k) R5 X9 W% T- d! X$ E
  _8 Z0 l  {  o% H0 B, e        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
# n- q4 G5 k. }8 H' M$ u$ c- w            if (arr > arr[i+1]) {
2 S* p- c1 L) e3 z1 ~- a) v                temp = arr;
/ ~$ M- E7 m$ C6 r  c$ ]                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
& f/ `- d8 T. y6 q
8 |; p1 u- C) l# T3 z$ w
        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
' R+ _+ Z$ U2 H' x            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
! M$ w, \. L; l8 H4 M. j9 w                temp = arr;
! ^) k. f  X4 T- D  J- K) r* D                arr = arr[i + 1];
& H8 J. L5 ?7 b7 L0 S6 c" Q9 I' u$ K                arr[i + 1] = temp;
            }
        }
* f4 u! f9 c3 T9 p0 n) I/ W

        System.out.println("hello " + Arrays.toString(arr));
, w5 Y0 ]7 k& R3 Y$ V& {9 Z( |        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决

) q) E0 o9 W8 ~/ z* H' `
6 ~8 R- o6 ~1 |. ]
! O" D  S/ c7 D& k# `  h2 T  |
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
0 v$ @  j5 z$ V' B        for (int j = 0; j < arr.length - 1; j++) {
! E: w: I3 o# @) T% q: |% Z4 N: R            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;
                }
$ y6 Y2 W* {  Z4 ~            }
3 e8 Z, ~( e' l6 b0 |5 o0 N1 K        }
; c9 a( [" \2 h    }
}
% `+ B* g9 P+ A0 u  r: v三、冒泡排序的优化

1、思路
/ i* S8 c. b2 g' ]如果我们发现在某一糖过程中，没有进行一次交换，提前终止
2、代码实现

package cn.mldn;
6 U( j2 {% _5 Y# x2 r
( C3 i" V; _! E% M7 W
import java.util.Arrays;


public class BubbleSort {
6 X) b) m- G0 k# N" @6 J- {    public static void main(String[] args) {
! R6 y* b- q' U) z& t        int[] arr = {3,9,-1,10,-2};
$ H. O! `$ ^, G" f* p* c: d        //大致过程
9 ]4 L7 C/ I4 L+ R$ B% [& C+ o        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
( g, x. f2 R! x6 \; |0 C' Q, [9 m        //            if (arr > arr[i+1]) {
; `0 o" b0 K0 E; C. D        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
& Y% r+ q- x* y        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
/ f1 t. |% t+ g  v; Z0 _        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
) q2 c! |3 t1 M0 ^2 u# Q6 ]        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
+ [; \5 B& p: P3 w) A        //        }
5 W, _) X* f) y& m        //3、第三糖排序，以此内推
" A1 @% d2 D  u+ o+ L        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
+ A2 |6 F/ g0 N2 x4 K% }        //                arr = arr[i + 1];
9 k* q( c! O8 d; ~) u        //                arr[i + 1] = temp;
        //            }
. U, ?3 f! H) c8 d6 Q        //        }
) I6 N$ O- u' i        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
6 k) |7 M% Y0 x+ H+ b0 B3 J, _1 M; U        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
+ G- V7 Y+ R+ S4 H        //                temp = arr;
/ K; L  d3 r" @* q5 O9 b+ i        //                arr = arr[i + 1];
# H: {+ j: U& n! c* E* s        //                arr[i + 1] = temp;
' l/ w. X8 u( V/ J6 j        //            }
        //        }
9 T$ b6 W) w% {# \6 Y  K        /*int temp = 0;//零时变量，用来将最大的数值排在最后
0 g& \5 _5 A% K$ W) \7 T' n        for (int i = 0; i < arr.length - 1; i++) {
7 h+ E: d# c9 z$ K2 G            //如果前面的数比后面的数大，则交换
8 X+ Q) N4 E7 c, I9 _3 ^, e            if (arr > arr[i+1]) {
% a( J6 I! O' @                temp = arr;
2 m* c3 P7 O9 E( x1 H* b& {                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }


        for (int i = 0; i < arr.length - 1 - 1; i++) {
# J2 N- u4 D5 r2 L. b' R            //如果前面的数比后面的数大，则交换
8 X5 m& l" E. t  n6 J3 W            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
( R! c8 t/ _$ N% u1 v                arr[i + 1] = temp;
            }
& \+ f  {+ R8 d        }


3 [6 J- s" @* k* I  ]        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
9 @, ?  j8 X; S- l4 F            if (arr > arr[i+1]) {
1 B' L/ q0 L7 ~2 i                temp = arr;
, R' B1 _& h+ F& r" R1 T' W, K                arr = arr[i + 1];
                arr[i + 1] = temp;
7 H2 Z' f5 f2 F( @) Z+ L            }
$ W& m% A4 E3 L6 P) i4 H8 |        }
% V7 c; @+ ?. y  L
% h+ P' x/ e0 H
        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
& t, A3 i4 Y$ Z0 L3 K* m            if (arr > arr[i+1]) {
                temp = arr;
* D) r% {8 V5 @- @3 _8 v                arr = arr[i + 1];
                arr[i + 1] = temp;
2 b9 F9 f" @# C/ B6 L/ A& ?            }
4 c: ^5 r* ]3 D7 m& C+ v1 w( ?( m) h        }*/
& B9 a, m1 _  {; w* _# n0 [
7 Y3 i1 L6 d' p/ O& X
        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
* n, `6 L- v2 z# r1 s" @        //根据上面的观察可以知道了撒，可以再用一套循环解决
/ Q# f9 ]; u5 x. _
1 E5 Y+ y8 }. C$ O+ M  s

, A! p" N0 W4 M# c" q

- I7 y7 T! y1 z/ z
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
: d) V0 T8 P. g        int temp = 0;
% i; |+ u* U  ^& b  n

        boolean flag = false;
0 N+ d  g- e8 l& a5 u% C        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
                    temp = arr;
1 N1 j$ G- Z* [3 {+ }" f% q# u, E                    arr = arr[i + 1];
4 T$ Y  }5 h" W# F+ ~2 s                    arr[i + 1] = temp;
5 J# O3 x) \; J; z6 _8 m                }
            }
            //在内部循环的时候进行查询
* F' R+ p0 ~/ |+ k  g            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
( F: M0 g5 F8 W            }
        }
4 v9 T; U, \- F/ ]- I6 d2 Q

3 n' ?; T8 r& {        System.out.println("world " + Arrays.toString(arr));
! [7 i) X9 ~, C+ z, J3 x    }
% o, U  A" i7 W: r; U0 J& z}
0 [. I; X: J& k& `9 _: K! l四、将上面的代码封装为一个方法
* C' z: L1 l/ Y1 Q/ opublic class BubbleSort {
' F  u- G. g' S. d# M. a    public static void main(String[] args) {
) ]% t# y. ~+ X: v) I8 B8 n        int[] arr = {3,9,-1,10,-2};
6 Z+ O. h4 I* c1 O$ Y  r) }+ v  V

        bubbleSort(arr);
  a  u  X4 j+ _$ o8 X) G        System.out.println("world " + Arrays.toString(arr));
    }

8 k7 C, \7 Q4 j: K
9 g" Y& G4 W' D+ v    public static void bubbleSort(int[] arr) {
6 r8 B, k+ D. P$ B  r' Z! k& M        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
3 e# g+ u% v4 P9 R. p/ g, |        int temp = 0;
" L1 Y7 t# S' M' w

. m; D& k9 P' O  @: U- m        boolean flag = false;
) e+ w! ^# [  H        for (int j = 0; j < arr.length - 1; j++) {
3 E4 @, {+ R$ a- h0 y            for (int i = 0; i < arr.length - 1 - j; i++) {
. D0 R: z4 T6 U: u                //如果前面的数比后面的数大，则交换
" y- V7 S/ Z" M                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
2 ?5 Q5 x2 }! y8 y" Y! T. U( o            }
            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
+ h& S% V& h/ M) r  B                break;
# P/ X% l1 Y& o+ d, Z. t            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
1 ?  C! {- r" M+ D" s4 j    }
3 u; _0 n) T6 }5 f4 K}
5 Q/ T. B; [& u# ]  Q五、测试一下冒泡排序的时间复杂度

1、代码是实现

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

. V: I; C/ k/ D; `9 W2 T
* e* N$ I: y$ z3 {6 e7 {) _public class BubbleSort {
    public static void main(String[] args) {
" F+ P: Q& F) @" M+ r; l$ ~8 a        //1、创建80000个数据来测试一下我们的性能
        int[] arr = new int[80000];
8 M; s: A) _9 J! q        for (int i = 0; i < 80000; i++) {
. D% n+ [) }7 N/ W8 {            arr = (int)(Math.random()*80000);//生成0到80000的数
        }
/ G8 O" }0 M3 k. k, I        //2、输出时间
& p3 M4 H0 W: z! o4 g        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间" + date1Str);
0 Z0 ~; W9 l% U1 L        bubbleSort(arr);
        Date date2 = new Date();
% ^9 C. g/ H* N6 T& k$ P7 m% I        String date2Str = simpleDateFormat.format(date2);
  r1 m; L) ]8 H' ?' U; C. v5 U7 Q        System.out.println("排序后的时间" + date2Str);
+ Y: h/ ?1 _9 c6 l6 ?( S6 m! z; K
# @% Z, G/ S( u4 r1 S
$ y+ @6 s8 B; s' F; R( l9 C

0 ~; k' k2 u+ M! _4 W    }

; s6 e1 A# }  F
    public static void bubbleSort(int[] arr) {
$ _2 b5 q9 D$ f9 R/ r" g; ?' a        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;
2 a' E- L- k3 ]: Z' l

9 e7 b5 t; W/ h        boolean flag = false;
' T! [3 h9 `  e8 d- R        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
& g3 w- A, Q  N/ @$ r                if (arr > arr[i+1]) {
1 a: f4 U: p( A$ J                    flag = true;//在这里把flag值为true
3 ?! F) b) M7 D! _                    temp = arr;
( [9 Q' n  F# G                    arr = arr[i + 1];
2 R/ S2 [, m# C8 l  _" `                    arr[i + 1] = temp;
+ ~$ f, ?; F) z! S                }
            }
            //在内部循环的时候进行查询
% u! q( s# b! F$ Y5 L5 V* F9 I# R            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
            } else {
; F- S$ x  G5 J! O! U) X) C                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
5 g( ~4 h) r+ G4 h5 X) E        }
! ~5 x: h9 X: Q: Z6 j! p3 g: j1 x" s    }
5 K% y6 a0 z  l; e5 [2 Z$ W}
/ ^0 z3 A1 V) z  v5 E
! J/ w( ?! T7 s: z2 V
8 y3 d! _. U$ o) h) ^% h: p
2、效果



. ?$ B  V: n& @

# K' K$ g3 `; I$ X# t9 _9 A0 l

470557092

顶。。。。。。

: t3 B8 d, H9 q