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

杨利霞

10大排序算法——01冒泡排序（Java实现）
; }/ ^* S1 i0 O: h  |7 p0 o冒泡排序（Bubble Sort）

冒泡排序也叫起泡排序
1 R, y$ B9 A# }; ^3 S
冒泡排序的执行流程
- P; M  A6 {& H; b
' Q: l$ t& E, @/ F1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）

5 `9 ~; A: a/ m2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序
) g. ?( @  h" |) a; Q" @
+ W( i8 N5 p# `来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
, N2 m2 q- L, N; e' b8 E: O& |4 [                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
5 A5 A; h" B; O" Z% n) y1 P- m9 S# v                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
! t& M  [" R; s( Y& W0 J                                }
                        }
                }
. \! C/ s. Q9 |/ ]/ w9 E                return array;
8 {1 n* k# `! A! X( P/ P        }

调用一下试试
0 n, ^3 Q2 p3 }5 y        public static void main(String[] args) {
                BubbleSort b = new BubbleSort();
( v, N' c9 F$ b& y  P                int[] array = {9,8,7,4,5,6,1,2,3};
                System.out.println("排序前");
3 G, s9 h5 p% L# J& l* @# q" u+ X% b                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
# _  h8 i9 A" O0 K  f: N7 ~- T: }                }
               
4 N& x4 l! @+ |) W/ \! m                b.bubbleSort(array);
/ h# E9 @) g* b! X/ {1 M               
& ?% w+ T" j/ s6 C4 P3 c* C                System.out.println("\n排序后");
) C8 }4 z& X$ f7 ^) ~                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
, G5 S8 ~* G* A. O# |        }


( Q* W; f8 n1 f4 Z' U  h# V运行结果：运行结果：
$ J$ o% A0 z/ B4 L2 ~" ?     排序前
0 u  f! y' j& `& B     9 8 7 4 5 6 1 2 3
# o. n7 `& w  {     排序后
     1 2 3 4 5 6 7 8 9

" Z' o* D( V* X. h这是冒泡排序的最简单的形式，下面我们来给他优化一下。
3 K6 D( E% Y. b  M
优化冒泡排序1
+ Q2 k4 o% @/ x2 b  x4 j/ y6 s' m; L+ h: @
: [  `/ H' A; j4 q" D优化方案： 如果序列已经完全有序，可以提前终止排序
7 X) J- ]) J+ V' g' ]$ T: w
$ z% \  d% }7 x3 y. ?/ H9 `5 \! p1 `来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
  J5 r  F# n+ k( m4 i8 S$ x8 f5 ^                       
                        boolean b = true;
                       
. D9 K" h: T) T, F                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                       
* E$ W" J8 h2 y' m: R$ Z; h4 Y  d                                        int index = array[begin];
                                        array[begin]=array[begin-1];
: P9 A0 ?2 Z0 u0 Y$ `# |; M5 B                                        array[begin-1] = index;
                                       
1 T! ?# P: h' j- f2 n3 t, i, z                                        b = false;
                                }
                                if (b) break;
* ^* U  U2 ]3 ^( b! D, b3 U                        }
                }
+ K( x7 G! ~, b$ u' [                return array;
        }
1 ?/ G# E% k% S$ a5 y) ]- p
9 K& z- l" ?2 X. n5 X优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。

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

优化冒泡排序2
1 q% q8 z! a% P$ I" w4 ~, Q8 K: G
8 W( B. l6 k1 U$ A优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

& o  t+ ^; R1 E, u% ]) i/ L来看代码：        public int[] bubbleSort(int[] array ){
+ `5 L3 o# D$ d8 S! ?/ \/ q" R                for (int end = array.length; end > 0; end--) {
0 W# I$ n4 A& i4 l9 x                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
; B: K1 h0 r3 `( ]4 s  ]                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
) w4 P' ~# g% s+ e& ~                                        array[begin-1] = index;
                                       
                                        j = begin;
                                       
                                }
! n9 F1 ?8 z4 K8 ]2 c                                end = j;
                        }
                }
5 e4 V% i1 L4 e; d% @                return array;
7 X: a- Q4 e( z        }
1 `" b2 S4 T# z' w* y# ^
- p" d- U$ _- E5 q1 N. Y优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。
& D4 u5 q3 L6 b! v
9 l6 r4 `0 G0 h2 T( X' S冒泡排序属于稳定排序，为原地算法

6 y9 S% I, j) g2 u注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
3 M5 m+ H3 i- E- M  B. I原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
) O; W5 R4 w) C5 g/ S
+ t& a4 C4 D$ ]' p& m3 S* J

柠檬草lll

发表回复