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

杨利霞

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

冒泡排序也叫起泡排序
( C4 K% u1 {- N* R6 d( V
冒泡排序的执行流程

1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
  w) V$ k& q6 f. `+ k0 Z$ u/ J
& C/ \6 V, P5 ]' c# E: \2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序
* R' }; r# r+ Q9 l! F- {  J  `6 {
0 m7 }/ g# F8 K3 Z# f3 X来看代码：        public int[] bubbleSort(int[] array ){
                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];
& V$ X' O/ ?6 b1 J  T                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                }
                        }
8 A& c9 W" I+ n6 s- n                }
: V/ ?( E- }& b                return array;
2 @  ?# O' ]* c( z        }
7 q% H4 U' B& J# e4 Z9 q2 ?1 L
调用一下试试
+ y# e; w# x9 n2 [7 G" I& z        public static void main(String[] args) {
                BubbleSort b = new BubbleSort();
. y* f0 u( g, o! F+ a                int[] array = {9,8,7,4,5,6,1,2,3};
1 ?: m) Q2 Z9 _; ?; K                System.out.println("排序前");
                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
- K" L4 q# t1 Q6 J                        System.out.print(array);
                }
( G% u) _+ _1 J* T# w, S, m( @               
3 a% T2 l* d( |                b.bubbleSort(array);
6 T6 B. J( K! j" y               
* h& y0 l! o# R6 l! S( s                System.out.println("\n排序后");
                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
+ S+ E5 ]( I9 |# ], ^        }
' [  t" A6 ?( X$ b+ L- W* l. F0 Q
2 n2 T  z! z$ _3 p6 L8 V, i
# R* u/ W; [2 B  N运行结果：运行结果：
     排序前
     9 8 7 4 5 6 1 2 3
+ W4 G$ h# R2 J! k$ @     排序后
     1 2 3 4 5 6 7 8 9

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

优化冒泡排序1
+ B% B1 g% i+ v" R2 M3 \2 f; x4 [
% J& W" l  g+ `2 ~  }# y  K! k5 l优化方案： 如果序列已经完全有序，可以提前终止排序
+ Y8 h1 q. e/ J5 ^5 C* B, N8 V: c
来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
5 u/ n3 G. t9 ]# P; O, E                       
                        boolean b = true;
                       
0 T9 k- H1 K& Q                        for (int begin = 1 ; begin<end ; begin++) {
+ I/ p" W8 w  L0 b" N                                if(array[begin]<array[begin-1]) {
                                       
+ N  S1 O% H/ K                                        int index = array[begin];
% s! P8 Y/ ~& \+ J* g+ a7 [                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                       
# b5 L6 R6 K" }2 p! E! b                                        b = false;
                                }
# G9 B# E* Q9 P' h8 W, M/ B                                if (b) break;
" n% p9 i. B8 |. j* [1 O( d                        }
                }
                return array;
9 q. Q* m+ g* W6 @5 Q% B        }

2 m- {% U3 S5 m/ b  _+ s: u0 K优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。

+ l1 ^$ i2 m! f; l  T3 W当然这个排序还是可以有另外一种优化方式
% ~  w3 H5 x$ d6 u7 I
% K3 ~7 ]/ S8 t- c5 Q优化冒泡排序2
5 b0 {2 L7 [' |3 b
优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。
. N) h$ t' i- d' B; y, j
9 K9 q) t5 _2 h8 w- X& v来看代码：        public int[] bubbleSort(int[] array ){
$ r: @, D% g/ u( y* v                for (int end = array.length; end > 0; end--) {
: ?% G' ?3 o- e7 m. j/ A+ L1 |                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
  F) ?0 O1 b6 D% y2 `4 d+ p                                if(array[begin]<array[begin-1]) {
! h- R6 C" T$ Y' E/ x                                        int index = array[begin];
4 R- h5 y+ k/ M7 b" D                                        array[begin]=array[begin-1];
6 }! p; \8 N) a  P                                        array[begin-1] = index;
                                       
4 P4 h8 |1 v5 D. W- Q7 q: ^                                        j = begin;
& t6 d6 _6 v2 J7 m$ U                                       
                                }
/ o; e$ w- J2 A/ |6 N3 G                                end = j;
+ ?# R/ i# R' W1 F: J                        }
                }
) v8 `& j! y1 z+ m                return array;
        }
: _1 b7 u6 _: a6 e8 d/ P  a, C
/ |3 U; b- |  v7 M优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。

. z* q& n$ X1 D" L1 Z冒泡排序属于稳定排序，为原地算法

' ]6 n& ]; v, h. I1 q# B注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
6 d5 Y& c7 K1 a

柠檬草lll

发表回复
/ D( B7 Q. h) D0 U