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

杨利霞

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

4 G' F1 W/ h& j: c: h冒泡排序也叫起泡排序

. h& r8 r8 ^! M冒泡排序的执行流程
. D5 v; w2 k# E$ C+ X
" A; `; \/ o. s" V1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）

( x1 W& a! q1 j. W9 o. X2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                        for (int begin = 1 ; begin<end ; begin++) {
. `# u6 x3 A: v+ a                                if(array[begin]<array[begin-1]) {
; d3 \. w& }) f1 L5 u; G& D6 A                                        int index = array[begin];
/ m7 `! ?0 B! u/ [& C' m                                        array[begin]=array[begin-1];
! Z( C: ]( E( L) Z7 \& I' W7 J                                        array[begin-1] = index;
                                }
3 I% b2 {' i- w* W7 C% p9 `                        }
  w' x" M; q" W( ?7 |8 ~$ ]" i                }
                return array;
        }

4 N( {' _" @% z调用一下试试
, J; r3 Q& m7 m        public static void main(String[] args) {
# E3 E5 I% Y" D                BubbleSort b = new BubbleSort();
# y* M1 \% G! i. }' b( {- R8 S' h                int[] array = {9,8,7,4,5,6,1,2,3};
0 G7 h, w. K" `                System.out.println("排序前");
$ q$ R3 `: \7 c" K                for (int i = 0; i < array.length; i++) {
. C5 e1 |, I* g) C' a                        if(i!=0) System.out.print(" ");
" ]9 _2 e: @- V8 d0 O# E* S2 C                        System.out.print(array);
2 Z8 @+ c* [; r                }
               
                b.bubbleSort(array);
! V0 J+ d9 H5 n3 p8 g               
5 y1 k8 ]4 \' H' \/ o9 S: m# i/ G                System.out.println("\n排序后");
" Z; n+ L7 s! i' `4 g% Y$ @                for (int i = 0; i < array.length; i++) {
1 w) B7 N/ s; y0 s* x, q                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
9 y* z! B$ I/ l3 A7 h0 V! b0 k" a                }
        }
  I5 B- ^" j, z( O& p4 w
5 v9 M, h, v. B" k2 [
运行结果：运行结果：
- `' _$ T/ R0 a( h7 f     排序前
     9 8 7 4 5 6 1 2 3
     排序后
     1 2 3 4 5 6 7 8 9

8 O5 ^- K: E  O这是冒泡排序的最简单的形式，下面我们来给他优化一下。
! k  C# J' j1 M" ]7 M, j
" [9 l. |. N! v- i优化冒泡排序1

6 G% F) r2 m4 O1 \4 I1 l# Z, r/ v2 E优化方案： 如果序列已经完全有序，可以提前终止排序
: @6 A: r3 [; f+ v$ ~
- d6 d, r, a+ `& }: r! G. k+ k来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
7 F( M& ]) Q; C+ D0 J! L4 T                       
* m* N1 K( C9 l2 m  ~9 F                        boolean b = true;
$ P3 c8 S+ G) y                       
                        for (int begin = 1 ; begin<end ; begin++) {
, d! ?+ _+ r' I" Z3 S& h1 _                                if(array[begin]<array[begin-1]) {
& O/ o% d; z& `                                       
                                        int index = array[begin];
1 X) V/ H+ `- W6 [+ J                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
* O+ g' E: {1 O1 J: [+ }                                       
                                        b = false;
/ V8 p& N8 p! _2 a3 C! L* P                                }
! j- A" M# Z* z2 A                                if (b) break;
3 C( U& o- l' d. ]! i: ]& l: @, e: U                        }
# s5 L' \) C! a! c                }
5 \* g3 X: k- d2 Q- T4 Q7 l/ B                return array;
        }

: B" J1 m0 K+ `* _/ T优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
/ |9 a! G$ w& |/ a& Y
当然这个排序还是可以有另外一种优化方式
' A' D: O+ e- o& K9 s% D
优化冒泡排序2

) j7 _. l7 g! x" q( W* M6 l优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

# b; ~8 I6 Q4 r* W/ J4 o' v来看代码：        public int[] bubbleSort(int[] array ){
# f2 P1 J6 o( X" f' Q                for (int end = array.length; end > 0; end--) {
                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
! f# W' s9 P/ Q8 w9 D! A1 [                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
$ \. z4 D- |  k6 c& Q# D" O- y                                        array[begin-1] = index;
4 u+ A6 S% {9 G                                       
                                        j = begin;
2 L! [# d9 D! W5 z: o                                       
8 H, a) C3 ]0 m2 q5 }! \: ]) b                                }
                                end = j;
                        }
1 m* i! h( D; z: }( O( @) ?: l                }
7 N3 v; ?1 d3 F; \) [# p                return array;
/ {0 A1 H. N& C8 L4 Z        }
# ^0 }; X( l1 b  F# p. |  ^
优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。
" ?# ?" x" m5 V" b" x# p. ?5 F
冒泡排序属于稳定排序，为原地算法

' g# D* K1 g  ]: X8 C注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
2 E. x# I1 s5 d$ M3 \9 u  d6 S) P原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872

8 z8 d* ^% O+ k* C& _: F; f
; N- B4 ]+ |! b: w" ^6 n- M

柠檬草lll

发表回复