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

杨利霞

10大排序算法——01冒泡排序（Java实现）
冒泡排序（Bubble Sort）
9 ?! s: e, d$ i" V" X% r
冒泡排序也叫起泡排序

冒泡排序的执行流程
/ t4 H' l# q) q5 M+ K
1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）

$ ]. @3 U' n7 A5 w" o2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序
. w8 I  i9 B# x& D5 V
6 ^4 e; K" @! t9 R来看代码：        public int[] bubbleSort(int[] array ){
' a  h# R# R& c% ^. `& r, f# ]                for (int end = array.length; end > 0; end--) {
; i) D. d! D0 v) ?                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
6 Z! ?, W' J1 A" t& S                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
% F5 X8 N3 j# T- G1 t                                }
                        }
# U+ b8 [% B5 J+ P1 D! t+ U                }
. T8 a; f  G! U+ B3 e6 ~( r: u                return array;
        }
5 p% k: k4 {% M
: w+ ]& v6 v9 V5 D调用一下试试
        public static void main(String[] args) {
2 Z, Q+ _* }4 h) D! b- Y% h: ]6 y                BubbleSort b = new BubbleSort();
                int[] array = {9,8,7,4,5,6,1,2,3};
7 X& j7 {7 `" c% q$ f+ V# Q% y                System.out.println("排序前");
+ _8 L/ g- M, i- t% \6 J7 Y6 o; @                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
; T4 l7 A4 P( W6 {  w- b               
  E5 Q6 O6 K% C3 T                b.bubbleSort(array);
               
                System.out.println("\n排序后");
                for (int i = 0; i < array.length; i++) {
0 \& J2 f% |0 m# H+ c/ B                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
. U5 h, i  a* q                }
        }
% ~5 {$ E8 o2 L0 ~+ z5 W0 J
, G9 k; N; U( G1 R( q
运行结果：运行结果：
     排序前
9 r; D9 v$ G5 L6 \2 T) H' f% i+ P     9 8 7 4 5 6 1 2 3
+ @: R1 D2 F* c! ?5 Z$ Y     排序后
9 V+ j3 S9 q" I" h% U. X% t     1 2 3 4 5 6 7 8 9

, |: M: g& ~0 a. {7 {" j: j这是冒泡排序的最简单的形式，下面我们来给他优化一下。
* V! F- ~% _1 t  K/ R
% j( k( N, B% _7 a3 N. n' i9 G优化冒泡排序1
5 J/ ]- t1 A! q5 R7 M$ R, O& B  p
: S& f1 R1 X! ^) \- s9 y优化方案： 如果序列已经完全有序，可以提前终止排序

来看代码：        public int[] bubbleSort(int[] array ){
7 U4 h  c! _- y7 n$ b                for (int end = array.length; end > 0; end--) {
                       
                        boolean b = true;
                       
2 q4 E9 l+ v8 I& e/ F                        for (int begin = 1 ; begin<end ; begin++) {
4 r* h# u3 g- @7 w$ v9 H1 u                                if(array[begin]<array[begin-1]) {
+ ~. U& A. C/ g$ a                                       
                                        int index = array[begin];
9 R9 ^9 Z3 ~$ X) \                                        array[begin]=array[begin-1];
$ ~5 c4 {6 K; j! N, O                                        array[begin-1] = index;
/ }: o' _7 X6 @6 T6 B& ]6 ~                                       
                                        b = false;
                                }
, J" q. C. G6 G+ ]  _* g$ X8 n& g                                if (b) break;
                        }
                }
                return array;
        }
' N7 m$ C) s0 x# Z
3 G; r5 w1 A( T( w优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
* f" D( T* a9 L, x. _( I8 B
当然这个排序还是可以有另外一种优化方式
( Y! H. N! i* S0 z1 F6 w3 m
优化冒泡排序2
' P" ?3 \9 _" z, B
9 ?; ~5 f) j& d3 R# _# S优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。
+ d" s7 o! x  W: R: z  d
9 q( C; \* T. Q: O; _" d2 f, r2 p来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
) ^2 N; C, H( y2 y8 d! c4 f                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
- x, B  ~  t5 g7 Q7 t% o                                       
' z% Y' c, e% Z3 H                                        j = begin;
0 B% [; X! }" b: W                                       
                                }
4 }* |1 W8 E( K% j" D6 L& q( i6 y                                end = j;
                        }
" M. H8 l6 g: p* k& _( i* S0 o                }
                return array;
) H# ~) \/ M% a9 P( @. s" R        }
: B, J% c+ x9 w1 o- j
优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。

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

5 H! E. r  q$ A; R5 o注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
& E7 E6 |( E  G+ ^# C  D) o3 f3 E! x原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
: B) j5 h6 e- O! z% u3 Z1 l) g" R

& u. j- ~1 j  E3 J0 [2 L' X

柠檬草lll

发表回复