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

杨利霞

10大排序算法——01冒泡排序（Java实现）
: s* a6 Q: k  @" H冒泡排序（Bubble Sort）
- P+ q% m, j$ W' A
# N/ D! s+ p6 b) L+ g* E( F冒泡排序也叫起泡排序
! p" O9 Y3 r1 C( z/ n4 @
2 j8 N' f6 p; g) c冒泡排序的执行流程

% c4 Z2 X8 C6 O% V, T1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
4 Q& x( y6 P1 B, M7 m! w
2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序
  \$ E3 q" ^( g' `
! @; G; F# z: ?1 m3 u# U来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
+ _! f) D' N! s3 D" [/ S                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
0 o# V. M. c! J% @$ G, }! c                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
) g1 V. L5 y3 G- y                                }
                        }
                }
                return array;
, {8 a( m/ i8 K& M- y* d4 T        }
1 z, U2 n$ _( B1 k. h
7 t& h: Z2 H; ~; a9 c调用一下试试
( D7 ]( D+ h$ N        public static void main(String[] args) {
+ U  }, c, n: r8 ?* a                BubbleSort b = new BubbleSort();
* o/ _. J& N  \0 t6 ~( Q                int[] array = {9,8,7,4,5,6,1,2,3};
                System.out.println("排序前");
                for (int i = 0; i < array.length; i++) {
9 u& v/ A( z1 {! G9 o9 S                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
/ D8 k9 J. _  ~" p: k                }
               
                b.bubbleSort(array);
* ~) F: L4 v# N5 ~               
  |: Y1 L" o* X0 B; |2 M5 J                System.out.println("\n排序后");
                for (int i = 0; i < array.length; i++) {
; Y" ^$ i* V9 j+ @( d& m, Z                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
        }
- b% n' a# p9 k5 n

运行结果：运行结果：
3 Z% u2 S( o4 K% J1 R     排序前
; ]& p' }) d$ y" Q- @4 d  A     9 8 7 4 5 6 1 2 3
5 \& g9 X3 L' L4 _8 b/ O( }     排序后
" I7 Y* |9 s9 [: q( _0 D; L2 H     1 2 3 4 5 6 7 8 9

这是冒泡排序的最简单的形式，下面我们来给他优化一下。
/ Y' h# }0 I% K  a3 `& G
# b6 }+ j  e4 {; I0 [& O7 b优化冒泡排序1

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

1 A. F* n# _# K) M# S6 S3 \来看代码：        public int[] bubbleSort(int[] array ){
2 u+ v2 d0 U5 r- v                for (int end = array.length; end > 0; end--) {
. f6 N$ ]  P- a) i' {                       
                        boolean b = true;
                       
. W" a7 B) s( l! R                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                       
7 G" f5 S- M; H9 x                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                       
  X# e( c* m9 W7 W1 Y6 U                                        b = false;
4 n: g, h. D0 N, K2 [                                }
( O3 Q% \% T9 k# E# e                                if (b) break;
                        }
                }
                return array;
" P7 P8 z0 Z) c% D7 c7 F2 A/ a        }

' @, G+ |7 \% y8 {7 b* Z7 ^: l" o, W优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。

当然这个排序还是可以有另外一种优化方式
6 A9 ]0 ~) j1 E, D  X
" k7 v" K" f, {+ I' K优化冒泡排序2
0 p% }7 _- p) C5 \0 n6 Z
% E6 B- ~; D9 n! l  `优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

来看代码：        public int[] bubbleSort(int[] array ){
8 B! ]8 D7 O( X1 Q: u                for (int end = array.length; end > 0; end--) {
                        int j = 1;
! X! _0 k) ^) x% a5 t4 I4 z                        for (int begin = 1 ; begin<end ; begin++) {
& u" C7 g/ Y4 u4 ]0 D8 O9 O! `8 d                                if(array[begin]<array[begin-1]) {
1 G/ _2 k3 T# n' @8 B2 {/ A                                        int index = array[begin];
6 W! e3 a; ~7 T                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
* `- x4 T& g1 \                                       
                                        j = begin;
1 Q" Y2 ]( z% `" S" I: {                                       
                                }
; [3 C; L4 ]* I& r                                end = j;
4 c7 X5 y3 c' w% V9 v- `. l                        }
                }
# H8 w5 p; [0 ?+ r2 w6 S3 H) H7 U                return array;
        }
  A* }' T; p6 v' R3 b
优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。

冒泡排序属于稳定排序，为原地算法
, \$ E" J5 r6 F0 q6 N- }  M+ z/ x& N
注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
7 l* q. I# e6 w" H3 |' D+ U

柠檬草lll

发表回复
! e0 o" P# r- R/ p! \5 l