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

杨利霞

10大排序算法——01冒泡排序（Java实现）
冒泡排序（Bubble Sort）
+ c; t4 B. H( l/ c) \: B) l
冒泡排序也叫起泡排序

冒泡排序的执行流程
9 {) T: H. H" ~/ v, I
1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）

- k7 l& B" f3 L' D9 q- [2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

7 K+ u7 h. d) c来看代码：        public int[] bubbleSort(int[] array ){
, K) f3 M; T8 y                for (int end = array.length; end > 0; end--) {
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
; M" R3 f# Q/ u' _9 J/ K, I                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                }
9 y6 h8 @/ i0 [                        }
                }
                return array;
        }
) o2 {6 x" `+ W. W7 k
调用一下试试
9 k/ ?4 q. h5 P+ W8 a$ m" ^        public static void main(String[] args) {
                BubbleSort b = new BubbleSort();
                int[] array = {9,8,7,4,5,6,1,2,3};
                System.out.println("排序前");
8 j* ]" m5 a" I" }4 _( V% v6 v                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
+ ^/ G# f( Z7 F! A' G, O4 X                        System.out.print(array);
                }
               
4 U* R; U" N3 \                b.bubbleSort(array);
               
8 m$ x- O" I/ N2 Q, r* i* N/ g$ a0 N                System.out.println("\n排序后");
5 V# [1 \  H- |; d+ c2 a; P                for (int i = 0; i < array.length; i++) {
( Z) J) A- Q6 Y" c; ]                        if(i!=0) System.out.print(" ");
, w, J4 D! F* q# u' V                        System.out.print(array);
4 q2 A( p( k" _6 Q                }
( E$ v6 R% G8 E        }
7 z) ~: G5 g8 e
4 t/ w2 w+ X5 e6 _
运行结果：运行结果：
" O) a9 |9 o) _: B     排序前
) D) \" o- r9 Q* a8 w0 f. h2 _* J     9 8 7 4 5 6 1 2 3
     排序后
, Q4 S; R0 M6 x     1 2 3 4 5 6 7 8 9
4 N: E/ A& M6 A1 B
0 g# e* ^- V2 B0 |这是冒泡排序的最简单的形式，下面我们来给他优化一下。
. |% S* T0 d. r
. p' `8 @: P- w# A& X7 S# ~/ f优化冒泡排序1

优化方案： 如果序列已经完全有序，可以提前终止排序
' s3 c, M# X0 }
来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                       
: o6 V" b1 U# G9 F5 B                        boolean b = true;
                       
1 p- A7 W! M0 j, n) k                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
7 f% r& m+ H1 Z6 x" [. P                                       
                                        int index = array[begin];
' P* g5 _& Q+ v. ]0 m% E9 o                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                       
                                        b = false;
, r  H. J2 k/ e                                }
                                if (b) break;
% v" Z3 \6 y2 T! I& l- ~8 `                        }
& y+ u7 ?, {0 F  A4 z                }
                return array;
8 R5 B! P2 |# K7 u; O        }

1 D8 K# N' l9 c% t优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
' }. c% e- @/ f' B( }3 U% U2 Z
当然这个排序还是可以有另外一种优化方式

优化冒泡排序2
. g5 ^, M) S. j3 H
优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

4 p' Z. R& M! R( T; G/ A来看代码：        public int[] bubbleSort(int[] array ){
& a% N" t5 f5 Z; [                for (int end = array.length; end > 0; end--) {
                        int j = 1;
+ `( P  @* a$ ?$ I- |5 l4 o1 h                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
- j: u" O+ Q4 K( \1 G                                        int index = array[begin];
7 {. w. r$ y0 y" S8 N1 d* v                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
# n; m; x6 Q! A2 o4 ]" f                                       
                                        j = begin;
                                       
                                }
' |( V! D7 ~& E! H8 ]                                end = j;
                        }
                }
# A' {% n! ]1 Y3 e/ _- \" c7 e$ a                return array;
" T# r0 M* L" t  n        }

' q$ F$ P( a) s+ K0 P4 K+ A2 f0 c优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。
4 j( Y: q  L  W# y8 M
冒泡排序属于稳定排序，为原地算法
& B* g) D; S8 ?1 t7 C9 Q
注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
1 F" G5 h9 l+ R7 F原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
5 H# n. @; K' @

1 x0 g. P1 z8 E. x8 o" p

柠檬草lll

发表回复
( K; s8 W3 N4 \2 R" G