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

杨利霞

10大排序算法——01冒泡排序（Java实现）
/ F7 }5 d) x2 J' ~. Z$ s冒泡排序（Bubble Sort）

  E- u, x" B6 _9 l5 f冒泡排序也叫起泡排序

冒泡排序的执行流程

1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
, F* T! A* }8 \# L2 s  B
8 O" {! y* Q$ b$ m7 Y2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

来看代码：        public int[] bubbleSort(int[] array ){
3 N* Y6 ~; J1 D; D                for (int end = array.length; end > 0; end--) {
8 J6 o& v9 H' ^4 `, j* l6 r' e1 l                        for (int begin = 1 ; begin<end ; begin++) {
% n8 k+ \* o) y8 Q* M& P  ]                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
6 ^1 Z9 |2 n  S                                        array[begin-1] = index;
                                }
                        }
' P8 a. r4 c" t                }
' ^" x2 s* [. w! j                return array;
/ B: i- e: [/ e0 Q  ]        }

调用一下试试
        public static void main(String[] args) {
( @. }( s) r% j4 b; X                BubbleSort b = new BubbleSort();
) f; B8 s  r8 Z) _# d                int[] array = {9,8,7,4,5,6,1,2,3};
                System.out.println("排序前");
                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
3 F# |+ u" R2 N8 f9 j/ w                }
, S; H* P4 Q2 F& N/ m1 ?               
. A3 g- H1 h: x                b.bubbleSort(array);
               
1 l9 E8 C) U7 C! V$ [3 _# O$ D                System.out.println("\n排序后");
                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
: h% F# O2 ?* a) l. `. t+ R                        System.out.print(array);
                }
        }
0 g: n# i, F8 p' g

运行结果：运行结果：
     排序前
! q& S: z4 Q4 U, s6 h) M2 d" x     9 8 7 4 5 6 1 2 3
$ K+ D& [  d# K* |# v# R" ^     排序后
1 ]7 S" [! S$ G& l+ F3 \     1 2 3 4 5 6 7 8 9
/ C2 d3 I: G- c  u
这是冒泡排序的最简单的形式，下面我们来给他优化一下。
1 S0 U9 n$ G5 z3 P/ \
# p5 `' L. M. ?3 v6 f优化冒泡排序1

优化方案： 如果序列已经完全有序，可以提前终止排序
( T2 K5 {" R4 H: L! }5 g$ Y
来看代码：        public int[] bubbleSort(int[] array ){
/ u; V3 n+ \$ l1 K1 p                for (int end = array.length; end > 0; end--) {
                       
                        boolean b = true;
; \: ]  ]+ `. h+ E5 Q2 S& N% N                       
4 N3 i1 N0 u1 {3 d! t                        for (int begin = 1 ; begin<end ; begin++) {
% N5 z% b+ u/ f* a. B: Q" O                                if(array[begin]<array[begin-1]) {
' g" z( \9 m' i0 w* h9 j4 }                                       
- e/ ]) p9 ], K% Q! {5 t9 w                                        int index = array[begin];
2 d# ]" f. Q; x4 S/ e                                        array[begin]=array[begin-1];
8 N7 w' w, h0 x2 z                                        array[begin-1] = index;
! `% F9 a; P7 u. q1 Z7 s                                       
                                        b = false;
4 x' R1 v  B$ n8 `6 F                                }
6 g' I4 [& d$ b# X                                if (b) break;
                        }
* i8 B( I( j2 x& e! B                }
: R2 t0 c7 O( d2 |* Z5 ^                return array;
        }
1 Y7 `& ^  ~* m; h' L( ~
优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
2 r+ m+ R/ _6 x7 ?% W
当然这个排序还是可以有另外一种优化方式
% S, x8 \- I% {# _) z  d
0 r  Q; `2 X+ u  h7 n优化冒泡排序2

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

8 X9 N% s) i7 l+ O6 U来看代码：        public int[] bubbleSort(int[] array ){
7 H! C, f: K5 F4 E* T5 Z                for (int end = array.length; end > 0; end--) {
: e; ?! ?% r" @. ^' H                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
$ c' `; B3 C8 k( ~                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                       
                                        j = begin;
                                       
7 Q* Q/ m, c" ]" M                                }
, y5 N7 E# c$ I                                end = j;
4 c$ N- O8 S' t                        }
3 {& j% C# |, S/ I6 E6 _) Q2 i                }
                return array;
1 k$ L* f/ w2 h1 {        }
% g0 r& w7 r" Z4 B
优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。
6 C2 |- s. Q4 B0 b% c
冒泡排序属于稳定排序，为原地算法

; u) d2 M8 C# L% I6 h7 g注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872

( B8 i0 ]  ?8 j
# O, m2 F) L. V1 F" C5 z9 `9 ]

柠檬草lll

发表回复