排序算法之冒泡排序

1047521767

                                                            排序算法之冒泡排序
了解冒泡排序是什么！
知道冒泡排序的思路
1 Q% }% `6 O) Z, H9 V5 x9 V知道实例代码并且练习
有收获记得帮忙点个赞，有问题请指出。
; T5 D4 H. O" {5 X' q* z/ E  b一、冒泡排序基本介绍
# l0 \3 {9 X& \1、冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前往后（从下标较小的元素开始）依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，就像水底的气泡一样向上冒出。

% c( f: t! t# _+ h9 J' \& o4 x' A
5 h' k) b& S1 P- s* v: C2、冒泡排序的优化思路
' z, n9 l* E% U" x+ d因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说名顺序有序 ，因此要在排序过程中设置一个标志flag判断元素是否进行交换，从而减少不必要的比较。


2 p1 L( _. }. Q2 B# M- |3 ~# g3、冒泡排序的图解思路

: \: G! i# F- q3 y
其实就是两个指针，移动来进行判断，然后如此循环进行比较 ，具体思路大致如下：
5 \/ k" t) |" X  M7 z7 S
$ a5 r6 D  q! F; t& w$ N
; g( M# m7 Q1 d* p$ @  ]" e% \% J第一轮循环得到最大值
  ]- X) A" R( J4 h第二轮循环得到第二大值
4 w& Y' \- N! o9 D9 @$ @第三轮循环得到第三大值
  x( X# ]- i8 Q) x第四轮循环得到第四大值
总的要进行数组大小减1的词循环
' v' ]5 @4 U% J, @& G
# X" R$ \4 @$ v" \8 z9 G7 ?/ {
二、冒泡排序代码实现package cn.mldn;


import java.util.Arrays;
; R4 w5 U& q4 d) }$ E

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
        //大致过程
        //1、第一步就是第一轮排序得到最大值于最后
# H. m& J' y( U8 e5 T        //  for (int i = 0; i < arr.length - ; i++) {
        //            //如果前面的数比后面的数大，则交换
! ^: w& ?. n, t8 n4 P6 K& [9 l' w0 z0 z        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
) j- c% _) E% p/ x1 d        //            }
& Q# l+ s1 M0 M2 X" K        //        }
3 y1 f: ]- f+ Y. L# \- T5 W        //2、第二糖就是把倒数第二大的排到倒数第二位
! u- w0 ~. I  V        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
) R/ H4 w9 l; W        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
* d, N/ [/ p0 y        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
* W, G/ |$ e. F& l9 f0 [        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
2 V# u6 `  B# j$ d        //            if (arr > arr[i+1]) {
; ]% Y$ s+ H; D* ]4 b* \        //                temp = arr;
. D6 L- z) D/ W. D        //                arr = arr[i + 1];
5 y! c4 a: B6 K3 L$ F9 {: E        //                arr[i + 1] = temp;
        //            }
        //        }
9 I6 |, o& D6 p8 q# s        //4、第四次排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
4 Y% J! {! h1 W' S7 m1 N/ v( m        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
8 ?9 k( F  A* f. H. @$ \+ X/ e        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
6 u# @, O! A+ u        //            }
        //        }
4 H9 T& w& R, }4 j2 v% h        int temp = 0;//零时变量，用来将最大的数值排在最后
        for (int i = 0; i < arr.length - 1; i++) {
4 M6 D, `0 K! U; q2 |4 y            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
- o: z+ Q3 x. y% [                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
' B$ n) Q, T8 }, z# k2 [$ A            }
: ~) v: z1 s8 _# A& X, C( N; B        }
# ]- I8 b+ f4 G! A
9 B6 K4 p! |5 M6 e& c! n* H+ l+ d
! B8 q" O; i6 b$ r: H* E% W        for (int i = 0; i < arr.length - 1 - 1; i++) {
+ ]& u0 b3 Q) X& K2 K* _. v            //如果前面的数比后面的数大，则交换
" E- V3 o) K6 A' X& v5 t7 j  P            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
. z+ F+ E1 {3 E  K) i7 {/ y/ F            }
8 P" T9 o7 ]- x; P, [! b        }
6 l4 l) i  E: q
: e  A; l7 D3 E) n
        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
1 w0 I, @( L2 m# P0 C# C1 a, h            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
- i; x6 v' c+ Q' r                temp = arr;
; W+ O' u1 Q* y8 ~9 @; p6 N& H                arr = arr[i + 1];
                arr[i + 1] = temp;
4 i* Y' V5 u: Q& [& I: J- q& P            }
        }
. I& Q! v+ d  X9 @! R

# c& g3 s  m( s* v$ K. Y( H        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
3 p, f1 n8 L* V            if (arr > arr[i+1]) {
                temp = arr;
4 a7 T2 q4 `7 k9 c. G3 c6 ^9 O) r                arr = arr[i + 1];
/ w) y* ^/ o5 l- Z% Z                arr[i + 1] = temp;
* t( Y4 B' q6 s6 Q0 W            }
4 N# K9 P* [8 q3 K        }


6 G# B) _  h" D7 s4 B1 m: E& Z' V6 g        System.out.println("hello " + Arrays.toString(arr));
        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决


+ R/ L  Y* M  [

8 F% I& G* y6 E+ `$ N0 J9 F        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
$ y" W& o. J6 }, J4 L/ a6 Q        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
5 G3 D) S% Q5 y; C                    temp = arr;
7 w* ^0 Q1 T1 E, T                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
. Z8 U# W- X" o( @( K! R        }
    }
" u0 U0 h7 ?- R! j, k}
三、冒泡排序的优化

1、思路
3 b# `: m- `7 ^+ d) \如果我们发现在某一糖过程中，没有进行一次交换，提前终止
2、代码实现

package cn.mldn;
: A& n( k& o! N( g! j) W
' L% k; K' V9 I; D) Z! g5 N
8 T2 W3 N( T" s$ O- limport java.util.Arrays;

+ l: w$ R6 J2 ?4 }
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
) d: v, K, Y- I, T+ `2 V# [+ l        //大致过程
3 b2 k- p/ `8 d: Q        //1、第一步就是第一轮排序得到最大值于最后
        //  for (int i = 0; i < arr.length - ; i++) {
; |( \2 Q# N; ~5 }3 G& }- t0 c        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
' l6 V6 i+ b, G" {        //            }
        //        }
        //2、第二糖就是把倒数第二大的排到倒数第二位
9 o3 T4 h; i5 f, ^+ K4 c        //  for (int i = 0; i < arr.length - 1 - 1; i++) {
+ A% B2 G: f" S+ C$ H6 ~, U        //            //如果前面的数比后面的数大，则交换
! \6 @! b2 X: y1 b/ v# _5 x        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
. G! p: j% U0 I+ F* n        //            }
# v- W  A, P& ^" E/ F- m        //        }
        //3、第三糖排序，以此内推
        //for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
        //            //如果前面的数比后面的数大，则交换
3 n6 V' C& L. ~) O' b- u        //            if (arr > arr[i+1]) {
        //                temp = arr;
        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
        //            }
        //        }
  I  y% [! `: T        //4、第四次排序，以此内推
( }, ]4 P  w% j4 y) ]        //for (int i = 0; i < arr.length - 1 - 1 - 1 - 1 i++) {
; {) i* u8 b1 `9 A, e9 [0 j0 t        //            //如果前面的数比后面的数大，则交换
        //            if (arr > arr[i+1]) {
        //                temp = arr;
' h; |! b! s4 T) H! a) C: D7 V! [        //                arr = arr[i + 1];
        //                arr[i + 1] = temp;
6 q% W$ T+ e7 }3 ~        //            }
& N5 S7 M& y$ A+ |# e        //        }
        /*int temp = 0;//零时变量，用来将最大的数值排在最后
# ~9 f3 e  b4 @. P        for (int i = 0; i < arr.length - 1; i++) {
. _" l8 A" ]/ M/ _( R/ K            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
                temp = arr;
                arr = arr[i + 1];
                arr[i + 1] = temp;
4 W% @0 X9 x$ D* r            }
  y) c$ c# o# u* c* _        }

8 R1 t' x; V& f' c9 h3 u7 q
: T0 H5 d" h2 N# f+ w7 X! h        for (int i = 0; i < arr.length - 1 - 1; i++) {
& X3 O9 V: H$ I            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
& X% _/ |- I  G. A7 z                temp = arr;
                arr = arr[i + 1];
8 Z  \- D! t6 t) ^' F$ H                arr[i + 1] = temp;
            }
        }
  x/ [' F$ o/ a# u

3 B, a, h6 S! U4 i        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr > arr[i+1]) {
+ g# f4 @( N% [1 O  R  j                temp = arr;
6 V2 b: Y- G5 x/ H1 |0 e, `7 j                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
2 r5 U$ \2 j% L; x
/ _# @. \" p) S. a# F8 ~
        for (int i = 0; i < arr.length - 1 - 1 -1 - 1; i++) {
0 m+ w1 u1 k9 K            //如果前面的数比后面的数大，则交换
6 G' r$ G* P# a            if (arr > arr[i+1]) {
4 Z2 V2 e8 t: |/ M5 K/ e! k( ]                temp = arr;
( W9 f0 e/ `) Z  x' O* V7 i                arr = arr[i + 1];
                arr[i + 1] = temp;
            }
        }*/
3 I. U# w4 s, N  B9 Z; P* R' P

6 l5 R) C1 I3 z* B. L/ f# n        System.out.println("hello " + Arrays.toString(arr));
/ k% J8 {6 D% h' x        //------------------------------------------------------------------------------------
        //根据上面的观察可以知道了撒，可以再用一套循环解决



$ T: p' l9 k7 i3 u
: W7 `! U! b' R2 g* g( K
9 O; e) d% G$ m+ _" x: F' G- M
        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
( X' |7 b; n( s1 W  L        int temp = 0;
3 J& h/ o! x" z7 i" t( B

) V& s/ v( i; l1 x; ?% }6 D        boolean flag = false;
# G, I$ {2 q( }9 j        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
8 _+ A3 h% U; ~0 n5 ?5 X                //如果前面的数比后面的数大，则交换
5 O9 J% X5 l! }( L& t                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
                    temp = arr;
                    arr = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
; m0 w7 a' K# h% f            //在内部循环的时候进行查询
' X# o# k* [, {1 l            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
, J7 y* M% \3 S1 A5 v' \& q                break;
5 i( w/ m6 _/ L. H            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
* E% T# }" e; f: u! L. {( F        }
- d; V( ~; G& |- J: `( K% w
) {# ?' |. e8 O0 v, j* t* Z5 `
        System.out.println("world " + Arrays.toString(arr));
! `* Z, P8 Y/ x$ Z4 B! @    }
}
: i. W6 S3 N+ z+ v  L9 V四、将上面的代码封装为一个方法
. g8 _! V, ]. [. Y1 {  P1 }public class BubbleSort {
7 ?* P4 h! ]! A) f6 |    public static void main(String[] args) {
/ P: ?7 L- ]; t  F( L        int[] arr = {3,9,-1,10,-2};


        bubbleSort(arr);
! ?" c) U  L3 [$ l2 f        System.out.println("world " + Arrays.toString(arr));
; D9 J, ]- s4 ^9 s! S    }
* z  S/ G, q. E( P" Q) m

, a6 a2 w  ^2 b9 O( g, e- t    public static void bubbleSort(int[] arr) {
0 R* b7 _1 w. ], j. ?9 B  R- v! t7 U        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
        int temp = 0;
  X% m* w/ u% v, H+ E1 m
, d! y; g7 u% ^4 F2 ]; k' e0 X
        boolean flag = false;
) B5 D% R: [# j+ \        for (int j = 0; j < arr.length - 1; j++) {
& ^5 D% L8 w3 X8 P; N# q* T# l) m            for (int i = 0; i < arr.length - 1 - j; i++) {
                //如果前面的数比后面的数大，则交换
9 g7 l6 w0 n% r2 h                if (arr > arr[i+1]) {
! A6 k  c: x- {* }& s                    flag = true;//在这里把flag值为true
, E0 }, K  t5 @; U/ P  i  i- d                    temp = arr;
6 i. x; x4 I8 a$ Z                    arr = arr[i + 1];
. q; `1 g9 D! b5 D1 B7 [" L                    arr[i + 1] = temp;
% D7 b( ~* @. v" h+ k* r  K6 z                }
            }
            //在内部循环的时候进行查询
4 A( x. E. F; o5 {            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
                break;
+ [- o1 \- D  A! I" u8 S            } else {
, u+ j; _; S$ g                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
/ l% `4 d, Z9 j) b        }
    }
1 C5 g( [9 s& c  `}
五、测试一下冒泡排序的时间复杂度

1、代码是实现

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


public class BubbleSort {
    public static void main(String[] args) {
        //1、创建80000个数据来测试一下我们的性能
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr = (int)(Math.random()*80000);//生成0到80000的数
        }
        //2、输出时间
7 T2 ], a# {/ B* X( ?/ a2 n2 |2 c        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");//格式化
        String date1Str = simpleDateFormat.format(date1);
- j% J& R. q8 O4 q! s* |        System.out.println("排序前的时间" + date1Str);
        bubbleSort(arr);
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间" + date2Str);
& E  U0 G4 @; ~: U  i! b$ X7 D7 {


% E1 U3 M1 z; D# N0 n/ G3 e
    }

  L1 z0 p/ L: G8 R  H/ f9 M% I
7 T; a1 x7 Q; L; w0 f    public static void bubbleSort(int[] arr) {
& e0 ~9 B$ f# {2 ^        //好好理解一下、由此可知，他的时间复杂度为O(n*n)
, S/ Q$ @. n1 h1 H( C' \& J4 g        int temp = 0;
9 U# Q" ]7 ^/ C5 c) N
% b9 U. @, m& d" y7 o' ^9 y
8 D) J2 r3 l6 M& {        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
. S. Z" {5 _) y                //如果前面的数比后面的数大，则交换
                if (arr > arr[i+1]) {
                    flag = true;//在这里把flag值为true
6 @. V1 Z2 c$ ?9 U5 @                    temp = arr;
8 B& \3 q6 K6 M/ }# m  o) v' Y5 m                    arr = arr[i + 1];
                    arr[i + 1] = temp;
! q) r4 d" Q0 I" L% I2 t& U                }
            }
5 ?+ w! n- O6 Q% u            //在内部循环的时候进行查询
            if (!flag) {//说明在第一趟排序过程中一次交换都没有发生。
0 F; E3 _% E# Y+ p7 P: J1 }% z1 p                break;
            } else {
                flag = false;//没有这个就是执行一遍就没了，要让他进行下次继续
            }
        }
    }
) k2 }4 c, j+ q) W}

0 G  c; Y4 |; ?* [

5 x  U! G, k# W# ?( w; S2、效果
# ^- k9 a/ C5 I# g) b
% M1 S& H6 E$ S$ o5 {8 d% E7 J

, ]' q4 a$ {( q7 ?, i. i
5 c9 s; p8 h4 J' w! k. x2 T
3 M/ d) K# S3 Q  Y2 a& Y+ U1 z

470557092

顶。。。。。。