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

杨利霞

10大排序算法——01冒泡排序（Java实现）
冒泡排序（Bubble Sort）
3 p& m! A. N% g- L
冒泡排序也叫起泡排序

冒泡排序的执行流程
) l5 I4 f+ X9 Q. X
1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
! p3 V# H6 p3 O6 `! \% f
2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                        for (int begin = 1 ; begin<end ; begin++) {
. Y4 x4 D# R, o- b6 g* h                                if(array[begin]<array[begin-1]) {
+ V) q3 M9 O, ?3 \/ [( x9 @- D                                        int index = array[begin];
% x( f6 G% `0 a4 j! V2 a5 S, t                                        array[begin]=array[begin-1];
. p+ A6 V2 L" l9 x1 s' b. Z                                        array[begin-1] = index;
                                }
                        }
                }
                return array;
        }
1 B2 m& d$ z7 x/ U& J+ U
, I7 a2 S( ]" X0 w调用一下试试
        public static void main(String[] args) {
                BubbleSort b = new BubbleSort();
                int[] array = {9,8,7,4,5,6,1,2,3};
# D7 g; B0 F6 Q2 [                System.out.println("排序前");
                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
* ]5 D  r7 Y9 ~7 G- ~                }
               
                b.bubbleSort(array);
               
                System.out.println("\n排序后");
7 d0 W7 f. [  V4 v: H9 A* @                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
        }
) M# q! I6 z8 W- n( ~! r

运行结果：运行结果：
     排序前
     9 8 7 4 5 6 1 2 3
# j" a( K& n( L: Y1 y     排序后
3 C. k5 u7 P% Z0 ~5 L1 o     1 2 3 4 5 6 7 8 9
5 I" T! A3 U: N+ j- P3 s
这是冒泡排序的最简单的形式，下面我们来给他优化一下。

! D" L0 B: |) n  x7 u9 s2 C优化冒泡排序1
/ S6 H. v9 z' L$ M- H% h
: d! q; ^& }. G. x3 O优化方案： 如果序列已经完全有序，可以提前终止排序
( h( J% e" L0 K, s9 }3 w
4 N8 d; ]; j' g0 ~5 T来看代码：        public int[] bubbleSort(int[] array ){
% A( j: O2 o5 Y                for (int end = array.length; end > 0; end--) {
! ^# |4 [- |' q2 t0 o' F# o8 O                       
                        boolean b = true;
: \# w$ g% Y8 C1 h8 U8 E& ?                       
5 _  N6 o" |0 r  a3 G8 k9 E" ~                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                       
/ z4 c9 B* w5 ?* E; j4 T5 `                                        int index = array[begin];
                                        array[begin]=array[begin-1];
! k+ T9 U, l: w; \1 i+ k                                        array[begin-1] = index;
                                       
                                        b = false;
                                }
* _' r/ K+ h& d0 `* r/ E                                if (b) break;
* b& e* m2 E+ l3 R' b                        }
                }
                return array;
, [: v6 {* s9 d5 O. _9 L7 d( ^        }

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

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

: @# ^6 l: u5 @* W& Q! q2 t8 e( j优化冒泡排序2

" @6 J% q, j, T8 q优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。
$ E8 K) |/ L; P: T
  v3 `# ]: n' F+ V' V5 k/ E' E来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
1 b! ^$ }. B3 V& A6 i                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
" g+ L$ B2 C: V& [                                        int index = array[begin];
" r2 h2 y* [6 x# _, O                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                       
                                        j = begin;
                                       
                                }
                                end = j;
                        }
" F" |) q' q& J1 o' n$ ~                }
+ a" L3 v# W* {7 V2 H4 p& c3 h2 T                return array;
# X9 @  F$ e0 ~        }

优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。
# |5 f  |: O- v
冒泡排序属于稳定排序，为原地算法
6 `; A  B. A" c2 e  ~$ C) i8 A
9 {5 K+ H/ B$ F( j, M. i注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
( e# X# s9 a) I- B2 Y. G原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
2 @  t4 j6 `$ `4 r# Q
9 `2 V$ p* ?, X
: p/ V! B2 B% I$ L1 ]

柠檬草lll

发表回复