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

杨利霞

10大排序算法——01冒泡排序（Java实现）
2 t9 E/ Q1 L0 b9 m冒泡排序（Bubble Sort）

. j0 j" L6 \; i冒泡排序也叫起泡排序
: j' y/ i/ S; ^0 T$ x9 }* m
  I! z% h, @$ D6 w/ @) J+ U: }冒泡排序的执行流程

1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
0 S. f' e% V; Q9 n# M) `
" _6 C: X1 k' V6 W- a! f( p2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序
2 c0 G- B0 s$ q; Q( i  h, h
( u1 J/ @. {  {( z3 |来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
5 b$ p. m1 r7 M* y0 k                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
: {$ k( m# n) s$ g! l# N                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                }
                        }
. f( K( x; c: G                }
                return array;
        }

# l, g% S' j2 e调用一下试试
8 I3 e  C3 u8 g7 B* h        public static void main(String[] args) {
                BubbleSort b = new BubbleSort();
/ g5 Z  ?8 _3 y8 l                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(" ");
: @! w# `& x/ b8 {0 U                        System.out.print(array);
                }
               
6 {+ t6 F' Y  w5 X: P6 K6 f6 C4 f                b.bubbleSort(array);
% d) |' e, S$ C1 P; B! i0 w               
                System.out.println("\n排序后");
                for (int i = 0; i < array.length; i++) {
# K. I/ p  q$ H9 Q( y- x# i                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
" D4 @* L2 P/ s4 v                }
3 l" e0 Q7 l$ N' `+ I        }
* y3 n7 O) `% }, i5 n

运行结果：运行结果：
* b+ S+ d! g, v, A     排序前
     9 8 7 4 5 6 1 2 3
     排序后
4 z" h% D8 e6 ]; [' y. Y& i     1 2 3 4 5 6 7 8 9

这是冒泡排序的最简单的形式，下面我们来给他优化一下。
2 a$ U5 b8 O, ]( a" R6 c! S
优化冒泡排序1

优化方案： 如果序列已经完全有序，可以提前终止排序

来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                       
8 m1 v" t  H; T, \& o3 W' q! j                        boolean b = true;
6 ~% w9 }# i  \                       
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                       
' X8 x+ W2 k7 E, h) b6 g                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                       
                                        b = false;
                                }
                                if (b) break;
9 D( J4 i1 g- h7 A! `5 ~) x                        }
3 X8 i9 E% l5 k5 a1 o+ D                }
0 B6 ]$ u( a8 \: L$ i                return array;
4 T& n, p# D0 h9 E. c% }& F$ @        }

优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。

6 p8 X& E# f% O8 x8 }# @5 f5 |当然这个排序还是可以有另外一种优化方式

优化冒泡排序2
. @( I: g; I1 U( c6 S1 X
优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

. j0 M1 s/ f& T' f. R8 t! }0 v' `来看代码：        public int[] bubbleSort(int[] array ){
$ i+ Q& E2 k: N2 E7 I3 ]1 ?                for (int end = array.length; end > 0; end--) {
                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
; K9 a& j. ?- M. A0 [$ s                                        int index = array[begin];
: x4 Q8 d! F% u                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
% K) i/ X5 o$ K  U2 l                                       
                                        j = begin;
                                       
                                }
                                end = j;
7 Y9 g, T3 H% m7 ^* D                        }
8 t% W) N0 G6 L7 e, P2 y" ?- z                }
                return array;
        }

; ^  x. W. ]' j9 U6 _/ |$ k+ ?优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。
( o1 D: @4 v* b9 r
冒泡排序属于稳定排序，为原地算法

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


, H6 |# A. g5 K1 P3 l4 K5 ?

柠檬草lll

发表回复