10大排序算法——01冒泡排序（Java实现）

杨利霞

10大排序算法——01冒泡排序（Java实现）
冒泡排序（Bubble Sort）

冒泡排序也叫起泡排序
1 _/ i& d; D1 S
8 c1 f1 i; K! I0 R  G1 ~! T冒泡排序的执行流程

1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
0 G1 s( ^& Q: Z- {9 a
8 f4 u- R2 N+ R$ J; q2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序
# v# V0 K' h5 @
; {+ M0 c2 z% s0 U* ^; b* n( k4 K来看代码：        public int[] bubbleSort(int[] array ){
6 t# Y% k2 r$ Q1 J3 z( J8 n                for (int end = array.length; end > 0; end--) {
1 B6 W; L: v; E                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
3 r: i+ Q0 z- @. D6 L                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
' n; P$ p, L# t6 n0 D5 B                                }
" V% g& B! Z5 ^5 P  s                        }
' j8 z' q( j: E. d6 I                }
% T+ A) g, o. P% p: Q                return array;
2 F3 x  D* o3 N5 X        }
# k: X, @2 q$ A: D
2 Y" D# ]) E! w  p& y调用一下试试
        public static void main(String[] args) {
, R# k5 v4 D0 G: N                BubbleSort b = new BubbleSort();
5 `  w" L. l) a  B' W                int[] array = {9,8,7,4,5,6,1,2,3};
                System.out.println("排序前");
* A0 r2 ^& m' @                for (int i = 0; i < array.length; i++) {
0 y* z7 \2 O$ _+ k                        if(i!=0) System.out.print(" ");
2 h+ V% K% _7 l2 Y- k; k0 B5 @/ {/ P                        System.out.print(array);
% D: g  P" G; g  w4 V! K: e                }
: h" S* C- n" U               
- y! z6 y9 G- G/ J% }                b.bubbleSort(array);
, K; T& X; P% P3 w, s" P0 G               
                System.out.println("\n排序后");
                for (int i = 0; i < array.length; i++) {
: k" P( J4 [. m4 E' [9 s                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
: Q& }% e. Q& j1 G( \% N, L        }


运行结果：运行结果：
     排序前
     9 8 7 4 5 6 1 2 3
     排序后
     1 2 3 4 5 6 7 8 9
- i) v8 i2 X% V9 ?& `
  R! ?& ^) N* c6 v这是冒泡排序的最简单的形式，下面我们来给他优化一下。
2 p4 ~- s* f& J3 y1 S
优化冒泡排序1
' b! E/ m9 ^+ g6 G% Z: X
7 j- M( Q9 j. `5 ?% \4 p5 H; K优化方案： 如果序列已经完全有序，可以提前终止排序

来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                       
3 M8 V9 V7 Y' E/ ?                        boolean b = true;
                       
8 u! P2 f; f* j- G4 P                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                       
/ e8 ^* c8 a/ n% X% V. v                                        int index = array[begin];
                                        array[begin]=array[begin-1];
* f+ O: B! ^+ U* ]) ~) g6 y1 ^                                        array[begin-1] = index;
9 j: ]! P9 W+ E4 g8 V$ P7 S! D                                       
                                        b = false;
                                }
                                if (b) break;
# Q  N/ U+ e+ i: y5 P  I                        }
                }
8 P( _4 X1 }6 W0 {: b' H: L  ^                return array;
        }
7 \: U, K* S' R3 N2 m3 G
. \& d& p" I- t4 J# S优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
$ q2 M$ [: l+ l. _7 l3 G6 [
当然这个排序还是可以有另外一种优化方式
! H# `5 y- t9 e, _) y; h4 x
1 d( M8 n8 z# o& I; V/ q8 Q4 I优化冒泡排序2

优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

来看代码：        public int[] bubbleSort(int[] array ){
$ l0 @' t0 J0 U" Q                for (int end = array.length; end > 0; end--) {
2 n* ]4 @" L8 X; S% ~- p                        int j = 1;
4 f5 a. k3 y# h/ [+ \                        for (int begin = 1 ; begin<end ; begin++) {
5 }( R5 F( P0 o8 ]% x                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
5 U) p1 s. `; T9 _1 M, Y3 c                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
* A$ o' Z! }: s3 x  e! |9 Z  ?% r                                       
                                        j = begin;
                                       
                                }
                                end = j;
' {+ y  X8 W- w$ s' {( W                        }
$ ?$ l8 @5 D( h                }
# ~1 c! H7 E9 |% Y  J) k                return array;
! U7 u/ S  g& W# T+ ~/ |" F, K) q        }

& ^: M, V; a8 \优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。

冒泡排序属于稳定排序，为原地算法

) F0 y/ o0 v% Q: h& g/ K7 b% @注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
4 z: V$ |6 S* }原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
6 z- U7 X6 r& X- p1 n% r

9 r! s* y& {; a

柠檬草lll

发表回复
7 P" m* N2 A& \; o, d+ L! Z) z