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

杨利霞

10大排序算法——01冒泡排序（Java实现）
冒泡排序（Bubble Sort）
- ]& ^" p8 o* J% o) D. a% l/ f
冒泡排序也叫起泡排序
" B8 C5 s8 b7 Y
冒泡排序的执行流程
0 [- d* A/ |$ s8 W( \+ H8 F2 t- C
1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）

2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序
0 [- ^# x7 o, y5 i9 V# [
来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
2 y. F* x5 i% O" a8 R                        for (int begin = 1 ; begin<end ; begin++) {
$ `  m: y6 O* L2 N                                if(array[begin]<array[begin-1]) {
1 ^9 B4 }# v, G% Y                                        int index = array[begin];
. _7 x7 @* R5 y! a0 W                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
0 t6 R4 E0 y0 e+ P                                }
                        }
                }
: n1 V; O1 s/ x6 s1 S- M, c- p                return array;
        }
' }! N  [# s- |) H
" _- i' D5 j1 b1 O- D( }调用一下试试
        public static void main(String[] args) {
. B; [$ y5 [, E8 Q5 E+ G                BubbleSort b = new BubbleSort();
# j# P; a. @, z; |. r/ R                int[] array = {9,8,7,4,5,6,1,2,3};
                System.out.println("排序前");
5 k8 I( \: [1 q; K5 V/ V6 w                for (int i = 0; i < array.length; i++) {
2 z& m1 l' I' t) O6 D" `                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
% W0 \5 `$ `! J9 U6 L2 I               
                b.bubbleSort(array);
/ g: D; r+ C5 s5 [/ R) W               
                System.out.println("\n排序后");
5 E9 I9 {, Z2 e# [( d. H) E! V                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
- t! b# A- ], o' q, H        }
- v5 }5 |- G( u$ f+ p

( ^; ?, v& z% n( w运行结果：运行结果：
  ?, U7 S! k' K     排序前
     9 8 7 4 5 6 1 2 3
* ?# ^$ N# r4 Y     排序后
! {8 {0 ]9 M) {! ?     1 2 3 4 5 6 7 8 9

这是冒泡排序的最简单的形式，下面我们来给他优化一下。
/ D" c3 X( [$ b% ~% w
8 I/ O& T2 L3 p优化冒泡排序1

& l+ F2 |! R+ x! ~& C优化方案： 如果序列已经完全有序，可以提前终止排序

( T& b6 g+ e* h来看代码：        public int[] bubbleSort(int[] array ){
1 q9 l; G1 k8 ]/ P5 x' G                for (int end = array.length; end > 0; end--) {
4 {0 j5 t" t$ t) @& s" E% O% `0 r- E3 q                       
                        boolean b = true;
                       
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                       
                                        int index = array[begin];
7 @) I  G. W9 ~  j- S+ y                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
; V/ I6 L3 D" B3 S1 F" d                                       
0 a% j& ^4 v0 [                                        b = false;
& f% t7 u. s* n9 O$ ~5 H                                }
                                if (b) break;
                        }
                }
                return array;
        }
- O2 t5 I* D' ^) d# _% r
2 N' h8 c! a( P优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
" r) h2 V0 {) Y
当然这个排序还是可以有另外一种优化方式
7 q; G2 L. P/ l
优化冒泡排序2
1 T7 G8 J  ]* s4 ^4 Q4 n! Y7 @
优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。
' d8 Y; E5 }! {( {" c
' R0 d5 x3 O6 h% J( N5 i3 \& ]来看代码：        public int[] bubbleSort(int[] array ){
2 {  [" o; [( A" ~                for (int end = array.length; end > 0; end--) {
                        int j = 1;
5 Q* Z' C+ _6 B3 ^6 E                        for (int begin = 1 ; begin<end ; begin++) {
9 i' O! v: T, V9 w7 V                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
6 Y: d$ U, s: A3 H* y' Y1 B                                        array[begin-1] = index;
                                       
                                        j = begin;
8 t# V8 }$ k( H8 d1 S                                       
$ ^- m6 s* E3 [/ Q4 W                                }
. L3 @9 M9 `4 h' n9 A1 d                                end = j;
$ M5 `# \0 K' e5 N8 z6 `' {                        }
7 z* O/ j) N8 ~$ G9 p                }
                return array;
3 d- L3 `* p/ Y; M        }
7 w" O6 H& I% j9 j0 ~/ x/ `0 E
优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。
) N. L( D4 r4 d8 _% `
5 R( O6 i0 e4 u冒泡排序属于稳定排序，为原地算法
+ G/ h2 ~- ~1 u2 a
注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872


3 I- F. ]$ X2 v- e

柠檬草lll

发表回复