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

杨利霞

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

冒泡排序也叫起泡排序
: `# U' n1 Y% F) I5 Z
冒泡排序的执行流程
5 K+ U8 P- B# }" i4 L/ y/ S
2 L. k& R  W- G2 a. q# u1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
6 l" x+ O2 N' u. c1 F( w, a
2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

6 I# {( \. G" B来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                        for (int begin = 1 ; begin<end ; begin++) {
) ]" @- _# |; [- X- j( C) t                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
2 q6 m* z# o, O                                        array[begin-1] = index;
                                }
                        }
                }
, F& c" s; Y7 F                return array;
: G$ \5 J0 |, V* Y& t  C2 S# t* Y        }
, H* O& ?/ ]; d  j1 l' L
6 x, z& o5 Z& d! K- g& n调用一下试试
9 v9 @! P3 O( x7 u7 |        public static void main(String[] args) {
* |- u$ k: H: U# C                BubbleSort b = new BubbleSort();
                int[] array = {9,8,7,4,5,6,1,2,3};
  A6 D) ^0 v8 J  ?% F: }  Z                System.out.println("排序前");
# s, f; J* z. [4 A                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
# x4 T+ g' f5 w1 q; `9 p                        System.out.print(array);
                }
& n, |% P, N* i; |5 A7 x               
9 S/ f/ V4 }( y- c( z                b.bubbleSort(array);
               
                System.out.println("\n排序后");
$ Y+ @2 a3 _- @, X! q# W: m                for (int i = 0; i < array.length; i++) {
+ g- S. }( ~- r$ C: K2 @2 {                        if(i!=0) System.out.print(" ");
' p. k( r( L8 q5 \/ [                        System.out.print(array);
                }
        }


运行结果：运行结果：
9 x/ w( u/ _. i1 A* I8 F* F4 H5 L1 y     排序前
     9 8 7 4 5 6 1 2 3
3 v  n+ |6 P7 p9 l: @. a9 H, a     排序后
+ u5 z) [" l( ?% j2 m! B     1 2 3 4 5 6 7 8 9
- c8 v: F% l0 V9 H- u8 ?
这是冒泡排序的最简单的形式，下面我们来给他优化一下。

优化冒泡排序1
1 A9 s! _1 x- x, k2 E/ }1 Y) p, S
) g' X: e2 Z. U- z# s( A" w优化方案： 如果序列已经完全有序，可以提前终止排序
1 n7 U5 |7 M7 L. @; n3 k$ N
来看代码：        public int[] bubbleSort(int[] array ){
& H4 Q  z1 B: V* {) V9 n2 G" m                for (int end = array.length; end > 0; end--) {
                       
                        boolean b = true;
4 d& _. j5 c7 ~+ f                       
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                       
" [2 R* o* ^8 s8 K0 ^                                        int index = array[begin];
) F* f5 h9 U- l6 x4 f! e4 @* u                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                       
0 d1 c; r# A' O9 Z7 ^                                        b = false;
                                }
8 x/ E" G% \0 `# o( C0 O4 s                                if (b) break;
                        }
                }
                return array;
6 Y7 U: l1 a4 u8 @$ V9 t: h% @8 _        }

优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
+ i) Z- L1 h- V
$ l& l8 K. Y. W) w4 Q8 X当然这个排序还是可以有另外一种优化方式

- U: H0 Q6 x$ W8 A8 c0 Y, e5 m3 t优化冒泡排序2
9 {3 z' Q+ q6 _; N: Q0 O% N
优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。
. q6 ?' }, k: [. V0 }( [/ L5 u
来看代码：        public int[] bubbleSort(int[] array ){
8 x2 }1 I5 h+ n- X8 U                for (int end = array.length; end > 0; end--) {
) \0 o0 X6 Q7 T  O                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
$ H6 }7 o3 F' c) y7 Q3 i                                if(array[begin]<array[begin-1]) {
/ x- f, r. j5 e9 w" [  z* ]                                        int index = array[begin];
3 J) i& g; u4 d3 P9 P                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
& j0 T! y2 E1 q- }% b4 G                                       
                                        j = begin;
                                       
; g4 H. O6 G- U2 x! T2 I5 @& d                                }
8 D& C. ]" {& `+ Z! A                                end = j;
8 ]5 [% ]& o* W  K$ A4 j3 P' |                        }
                }
% v( N7 J5 M( o# m# h0 e% \: o                return array;
        }

: Q, R% L8 p0 p5 s+ I1 r优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。

. Z/ X! F+ S0 }+ J冒泡排序属于稳定排序，为原地算法
4 F5 ?$ P: h# T$ n  [- z& b
注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
! ^8 [9 j" _5 w5 A+ n原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
  Y2 Q5 {+ [+ w4 p5 K

柠檬草lll

发表回复
& L7 ~- e. C# c) F. E' q