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

杨利霞

10大排序算法——01冒泡排序（Java实现）
3 a6 i  s) o6 ~7 y$ k: w冒泡排序（Bubble Sort）
# A. I- F/ R& c# ~
冒泡排序也叫起泡排序

冒泡排序的执行流程
( w  S7 M! N; f
1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）

! E9 z' m1 ~2 X6 I! O$ d2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序
$ e, l4 b9 {0 A8 v, L- x: W$ p
+ R- {: O  a3 v; H: B7 J1 X; k来看代码：        public int[] bubbleSort(int[] array ){
6 F6 u1 X: V/ [# J. L  G                for (int end = array.length; end > 0; end--) {
                        for (int begin = 1 ; begin<end ; begin++) {
5 \7 g! z* g7 O. i4 _( X5 k5 r) |                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
  M" {& j8 ]) F5 b                                        array[begin-1] = index;
6 V: [3 C6 ~& E- s/ I8 [                                }
                        }
                }
' @5 x- A( E) Z  W& Q                return array;
0 i" j1 w) G2 S6 }! j        }

调用一下试试
        public static void main(String[] args) {
8 W5 H5 v7 G: B% ^6 u; H, F  [                BubbleSort b = new BubbleSort();
9 e$ G* i6 U6 \8 v3 D6 Q9 T2 D1 R. K                int[] array = {9,8,7,4,5,6,1,2,3};
1 c2 r( v. A  S7 a; {                System.out.println("排序前");
                for (int i = 0; i < array.length; i++) {
4 Y4 o( |, S& \; Q% [2 T# }                        if(i!=0) System.out.print(" ");
. `# b; m& G9 ~) H9 Q                        System.out.print(array);
                }
               
                b.bubbleSort(array);
               
% _7 y2 w; D, \" r                System.out.println("\n排序后");
                for (int i = 0; i < array.length; i++) {
! d, r' @, `( @7 q; ]5 F1 l, q                        if(i!=0) System.out.print(" ");
8 I  i1 M% R5 ~& h8 b8 m9 @0 u& H                        System.out.print(array);
% z6 n* j0 G7 n0 L                }
5 J* p# j% C" s" ]        }

# b. m8 y: v0 v% O+ d6 x
运行结果：运行结果：
/ m# K0 Y* c! l) [& I# h7 B     排序前
6 X8 {8 |% c+ E: W- w) j# @     9 8 7 4 5 6 1 2 3
     排序后
! V1 [8 @4 r% q0 V% x     1 2 3 4 5 6 7 8 9
+ Y7 e; V' T4 X
% ?5 \! u2 d+ N3 r5 ]7 b这是冒泡排序的最简单的形式，下面我们来给他优化一下。

. M) R% p: A, a$ B- C4 }* n# ~优化冒泡排序1
+ A$ ^  j" C# x# D8 x9 _
优化方案： 如果序列已经完全有序，可以提前终止排序
' Z3 |- I2 {# y- p5 q2 y' Q) x6 v/ m
. i% b6 g/ Q: P0 E7 Q6 q' m来看代码：        public int[] bubbleSort(int[] array ){
6 F) X' D& z9 p                for (int end = array.length; end > 0; end--) {
2 g# ?/ \+ ~/ C3 S& C" P. [  @                       
                        boolean b = true;
                       
                        for (int begin = 1 ; begin<end ; begin++) {
; {! _( d3 W# I& X                                if(array[begin]<array[begin-1]) {
                                       
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
- {& c( Y: o# c; x" [                                       
                                        b = false;
. b+ t5 {# ~- f                                }
1 T( X, ~" q+ `- N  }: R* a                                if (b) break;
                        }
                }
                return array;
        }
( s/ B7 o. m# ?* O7 o* g) n
( {5 d$ f1 X  d优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
" n0 i& o$ y5 m" E1 B
当然这个排序还是可以有另外一种优化方式

优化冒泡排序2

优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

来看代码：        public int[] bubbleSort(int[] array ){
7 Q6 `. W8 r+ \1 L# [                for (int end = array.length; end > 0; end--) {
( I) Y5 ]& |9 l. @% m9 c0 l. J                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
: K$ ~  @3 L. H/ n                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
" R7 L8 {- d2 h- S8 X                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                       
  Q" d5 Z$ X! B+ ?& ?: _6 R                                        j = begin;
$ ?, B( g2 m. d7 z. L                                       
                                }
                                end = j;
                        }
# u, E* a9 G- u8 t                }
+ D" _5 q) ~8 M: }2 g                return array;
        }
% e- I# o# i( G4 `- `
优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。

冒泡排序属于稳定排序，为原地算法
: i! u0 L5 b2 X" k
6 l. g2 W( ?; n注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
6 \: ?) U8 j  @" L原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
% W! M4 R/ s1 U+ f0 `1 H) i* N

柠檬草lll

发表回复
+ t( ^/ x& n/ F( u, T  m% u