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

杨利霞

10大排序算法——01冒泡排序（Java实现）
% E; o5 O" P* H. F  Y3 B4 l/ E- q9 X冒泡排序（Bubble Sort）

3 c( D4 G+ N+ h+ g冒泡排序也叫起泡排序

5 x8 a8 o2 O& m* m冒泡排序的执行流程

9 P, T$ C7 i/ w7 O6 }% ]' u1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）

; S' z8 e: ^9 b2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

来看代码：        public int[] bubbleSort(int[] array ){
% ^: O  N* g% f+ ^; P* C$ p                for (int end = array.length; end > 0; end--) {
) d9 \: r8 R, J, E                        for (int begin = 1 ; begin<end ; begin++) {
9 o" W8 c5 {/ ^% ^                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
5 t# g' H6 C2 D- f1 |# I                                        array[begin-1] = index;
                                }
+ U  B/ |5 \2 }& V# ], i( D! e                        }
! ?( `6 i1 g; z9 H. T' b3 Q# A/ J; J" k                }
                return array;
        }
3 H1 o& h* a5 x/ x5 ~
/ @4 z  d1 ?: y& l; c5 Y  F1 t调用一下试试
! ?, ?) d6 U$ G! U! A4 u3 ?        public static void main(String[] args) {
7 I. r( [" {' h+ d4 Z, ?1 m- D2 T                BubbleSort b = new BubbleSort();
& Q3 d% U& p0 u5 M2 k: V2 k# R4 Z' B                int[] array = {9,8,7,4,5,6,1,2,3};
0 Z+ y2 r+ V( b& c6 U8 m                System.out.println("排序前");
                for (int i = 0; i < array.length; i++) {
2 w/ c! H# E0 G& {                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
  ]1 u4 b6 X$ X5 x                }
               
, }8 n! ^  t4 }$ }% y5 c$ C8 B                b.bubbleSort(array);
               
) y7 S, G: z* r, a                System.out.println("\n排序后");
                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
- {; I" X6 ]4 H8 E8 ]  H! B& z                        System.out.print(array);
: U& j" {" |* B                }
( ?; g" y& B6 R' c1 b        }
4 X2 X2 y9 ~3 S( x

运行结果：运行结果：
& @. O1 Z- M6 h     排序前
+ L- ^# H) ?0 K* z( c1 N( L     9 8 7 4 5 6 1 2 3
- \6 j4 ?5 e0 c0 C$ I& _3 x     排序后
* }* i3 N# F/ S8 z     1 2 3 4 5 6 7 8 9

2 E& P) y- @) Z) V( S1 T8 k这是冒泡排序的最简单的形式，下面我们来给他优化一下。

* }& _0 c. e( w: Q7 o优化冒泡排序1
$ U: r( ]% d/ ]
优化方案： 如果序列已经完全有序，可以提前终止排序

来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                       
                        boolean b = true;
                       
0 w' t0 c) K. {5 I  V                        for (int begin = 1 ; begin<end ; begin++) {
( R+ P/ H7 j; p& e. I9 ^                                if(array[begin]<array[begin-1]) {
# P8 y$ z( _- R                                       
8 x! r# S# _" B$ G0 W" v                                        int index = array[begin];
( U% C# J" s! K+ C2 |% y" w' u                                        array[begin]=array[begin-1];
- C6 k5 O$ W7 F) T, q, L                                        array[begin-1] = index;
7 ?3 o5 U2 I/ S7 X0 A; M                                       
2 I2 {8 _! }9 O- B! I                                        b = false;
                                }
                                if (b) break;
                        }
                }
2 m, J( M- X+ N% m% J5 Q: s# X                return array;
7 W3 v) ~9 D' A7 A4 C0 p$ ~        }

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

当然这个排序还是可以有另外一种优化方式

! x8 E+ V) R3 w优化冒泡排序2

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

来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                        int j = 1;
$ o5 V/ n  {, A, l; i1 }3 s; r& i                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
5 Y& p9 v" u- y" T                                        int index = array[begin];
, @  w6 @: S2 d1 g8 q                                        array[begin]=array[begin-1];
* j0 Q/ I, r: I' v                                        array[begin-1] = index;
, t4 w1 q& W9 F) n) i2 T" R                                       
                                        j = begin;
                                       
                                }
                                end = j;
; O, P" C8 l# y' H+ e& v' }% t                        }
                }
$ r/ ]9 Q3 |% V) `& W                return array;
        }

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

2 |2 w0 u) X6 F  K冒泡排序属于稳定排序，为原地算法
' C8 d  h) M# K  r
) [8 Q' V7 h* H; p6 |% w2 e! w! o注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
7 v1 j5 N: F; z- ~原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
# i( K1 f# A8 r: x3 V/ U3 A$ {
( w* o( A( V. U' T
- y& w. s! G, q, I2 s: Z

柠檬草lll

发表回复