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

杨利霞

10大排序算法——01冒泡排序（Java实现）
$ ~! w5 M0 M& A- Y5 h冒泡排序（Bubble Sort）
# S1 d- p' d* O5 M
* x' d- ]: x/ g; J; l冒泡排序也叫起泡排序
# z# O, h& l0 Y2 }4 t
% l1 v; r) r' U$ Q8 e% _0 R1 |0 V冒泡排序的执行流程
& N3 h$ W4 O2 {7 ?! k. y$ S
- ~( `. q# m% {( e3 c8 w1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
, J( Y: h2 Q! _) z" u
2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
1 `% B1 N4 @# Y4 ], L8 p# L, u, Q; N  P                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
- Z( H" [- b# `6 ~+ N4 A                                }
5 N" W$ Y/ I& P9 K$ [' |+ |2 [8 y' Y# X                        }
/ N  d! N( K. t+ E/ I: A                }
                return array;
* N7 D! K2 p3 j" B. O/ M        }
7 D% i, c' j; Z7 u
1 O' Z  \2 h3 R- I3 `调用一下试试
+ l. }. N' I) T; x! D1 x% T        public static void main(String[] args) {
2 U+ N" s4 V  |1 `                BubbleSort b = new BubbleSort();
, Q4 t5 G/ T2 m8 ~! i2 M+ f7 W* z7 s                int[] array = {9,8,7,4,5,6,1,2,3};
# u% k+ a  w5 w                System.out.println("排序前");
                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
  v6 R$ n: F) i1 a7 L                        System.out.print(array);
0 M* I+ A# `* \0 o: U- e% e                }
5 `& }+ m, W7 ~" Z6 i8 Q               
                b.bubbleSort(array);
               
                System.out.println("\n排序后");
2 Z* f' \: D- a4 M% s# b) m+ y                for (int i = 0; i < array.length; i++) {
# \5 M7 {$ Z' P$ q1 S1 M, w                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
* l& V1 n% U0 ?( P( R        }
9 K: x5 M/ [, k3 @. m
8 T7 c8 f" }' ^' Y: j4 `$ h
运行结果：运行结果：
0 W$ Y+ @+ g* i6 {8 ?     排序前
/ a7 s( P- Z" \     9 8 7 4 5 6 1 2 3
2 o' f% B  u' D! q$ T; x     排序后
6 k# @/ A% K4 J! L# P7 t7 i6 X; m     1 2 3 4 5 6 7 8 9
! h" v8 W* H0 W
这是冒泡排序的最简单的形式，下面我们来给他优化一下。

1 h9 E3 \# l. }9 m/ V+ b( T+ E) q优化冒泡排序1

优化方案： 如果序列已经完全有序，可以提前终止排序
; E4 u  f0 t9 L8 G* A& _
- H( S' c4 D  O3 V: o. [来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                       
! |2 J" w" W5 ~6 U4 L! }0 P* U- J                        boolean b = true;
/ E: M, J: d7 m: t3 c$ H5 u                       
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                       
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
8 I+ _3 N) L/ ?! Y9 b                                        array[begin-1] = index;
                                       
: q9 Y5 w( q8 G# L' h0 G' Z                                        b = false;
- k8 w8 r: j; F# ~                                }
                                if (b) break;
                        }
                }
                return array;
        }

- c$ I" C4 G, Z5 ~优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
8 G+ ^% w' ~! v
当然这个排序还是可以有另外一种优化方式

! i. a1 y; N5 ]6 G1 F) _, R优化冒泡排序2
1 T3 a  v# v  K( R  d
优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

来看代码：        public int[] bubbleSort(int[] array ){
+ X- a3 _6 M8 a6 o                for (int end = array.length; end > 0; end--) {
                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                       
                                        j = begin;
                                       
                                }
* x7 f) B% t6 N, W1 A                                end = j;
) Y; k, Q* {* G* D# |; V                        }
# ^1 e  V- A  ]) W( R% C3 h! L" O                }
                return array;
5 |2 B( C- ]5 c. _/ _3 h, H        }

' u( X+ Q, z% ]- M' K优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。

冒泡排序属于稳定排序，为原地算法
# [2 c% K9 r. S% D$ {5 A
5 i9 p  Z! b* L/ h5 ]# j  r注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
/ q- z: B- u% D& [原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
6 S: `  V1 E; E3 d
$ n& u, }( S+ a

柠檬草lll

发表回复