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

杨利霞

10大排序算法——01冒泡排序（Java实现）
% g( K0 |' P  r! i+ S冒泡排序（Bubble Sort）

冒泡排序也叫起泡排序
3 i) j: ?# t& ~- N
5 f9 S6 J. j! \; {# y' c2 s冒泡排序的执行流程
. c6 R+ r. d0 a8 b' }2 y
, N! T, f# {/ h- }& F; R" w, L! C1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）

2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

! ~* k0 S6 e. U! r来看代码：        public int[] bubbleSort(int[] array ){
) r- t3 B- U0 L                for (int end = array.length; end > 0; end--) {
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
* ?* m+ ?0 x7 i/ A% f0 R                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                }
                        }
* N- t* h5 Q# r( ~( a5 N, F                }
5 n: |% g% P9 C2 U                return array;
        }

  S. v8 @- E: p调用一下试试
        public static void main(String[] args) {
0 s! _( o0 R3 B2 ~5 g* H8 @                BubbleSort b = new BubbleSort();
                int[] array = {9,8,7,4,5,6,1,2,3};
9 s" T( l3 a' O! N) v) w                System.out.println("排序前");
                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
) `2 g  R! W$ h* s               
                b.bubbleSort(array);
4 p3 I/ e9 E/ @- l6 I) s               
                System.out.println("\n排序后");
/ r2 _" f; |3 L. }2 T* U                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
        }


运行结果：运行结果：
     排序前
3 ]6 D. x" j0 K' `" h     9 8 7 4 5 6 1 2 3
6 ^5 |! l6 C9 n/ \. b/ P; T9 E7 ?     排序后
     1 2 3 4 5 6 7 8 9

这是冒泡排序的最简单的形式，下面我们来给他优化一下。

1 L) ?  `( n1 e+ `8 D% g8 }优化冒泡排序1

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

来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
# f  e6 c5 K+ l; X  z, q                       
                        boolean b = true;
& P; j+ @! X" P0 u& e. b; H5 u                       
% P9 a. k3 H# Q$ d2 \                        for (int begin = 1 ; begin<end ; begin++) {
- n& G: l: K; H1 Y                                if(array[begin]<array[begin-1]) {
                                       
+ Q/ k) |* t8 p( C9 V% u; `                                        int index = array[begin];
                                        array[begin]=array[begin-1];
% r. `) \8 y4 }. Y5 K4 h6 L                                        array[begin-1] = index;
                                       
                                        b = false;
                                }
% s1 c  T$ a4 D, n% S- T, t; l                                if (b) break;
/ l8 q0 L. w7 s, Y8 l5 x& r' q- q                        }
9 k" h/ C2 X3 M                }
                return array;
        }

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

. w0 O# `6 X. Z# K# R/ |2 F. P. u. x当然这个排序还是可以有另外一种优化方式

优化冒泡排序2
6 f! J: l; p" X0 G
优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

2 E8 a% K+ n) W2 f, e* h! M6 i来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
: k3 x" T4 U# {. G$ R; ]9 N                                if(array[begin]<array[begin-1]) {
! Y2 m# @; m$ L/ Q6 c8 _                                        int index = array[begin];
/ R3 [$ M- Y# k. O$ F+ A' |                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
( C  L: P, z* I% S5 z3 f                                       
9 r1 Q9 F9 i2 h! ^7 E# x                                        j = begin;
                                       
                                }
$ Y2 i: ?  `( H! A4 L- `                                end = j;
                        }
/ y3 N% H% M% k( @                }
. {" g$ r8 y& F* ]; z5 W7 W                return array;
; K+ C# L* S/ A; i. Z        }

. t' l: Y$ A0 Y) F) e优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。
2 y8 K# U/ P# s- m+ @
冒泡排序属于稳定排序，为原地算法
) E% k, Y/ t3 b
注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
. G& P* J+ B% F原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872

! [  l! P, h+ ?, f& B6 T

柠檬草lll

发表回复
- }8 K( e8 c. G& b7 w! A: ]