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

杨利霞

10大排序算法——01冒泡排序（Java实现）
9 p& U  S& g/ ^7 {9 L" `# F冒泡排序（Bubble Sort）
5 Y9 w" I9 ~" [+ \7 c1 \- ^
冒泡排序也叫起泡排序
9 v9 o% B: _+ A8 v' ]
冒泡排序的执行流程
5 U/ O! L& U) j7 E
1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
! Z" _" P4 w1 P' j7 A' X) S9 A
2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序
8 T% o: `2 |% T0 x, J) t
来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                        for (int begin = 1 ; begin<end ; begin++) {
# q" h4 i8 L! Q; ]# D8 e! E0 C' `                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
# X7 B- c& v; ?+ o5 q                                        array[begin-1] = index;
                                }
                        }
                }
, i: a  R4 Q4 h2 L; c2 q4 Y                return array;
( b- K, q$ u6 k        }

. ^) S6 E2 \+ ~! W调用一下试试
- _0 l5 k3 ~4 \9 a# ^        public static void main(String[] args) {
. `3 e3 g0 T5 [( p! W$ }  G  o                BubbleSort b = new BubbleSort();
                int[] array = {9,8,7,4,5,6,1,2,3};
; m. u+ o. [/ c* F                System.out.println("排序前");
                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
% d0 b" J# U) S, V                        System.out.print(array);
1 r! z0 O( f% N: [( \- z                }
- J/ X- x. A0 b5 Q               
                b.bubbleSort(array);
               
# H+ b  Y4 Q$ M* ~1 |  g0 R5 P                System.out.println("\n排序后");
* ]6 `  t- v0 B& t/ A. E                for (int i = 0; i < array.length; i++) {
. Z" `- {2 E/ W/ w  w; v1 G" L6 D                        if(i!=0) System.out.print(" ");
9 ]* @6 m- o1 e                        System.out.print(array);
                }
$ _9 P% }, g' @  \        }


7 o, N' W6 U6 ^0 Q运行结果：运行结果：
) Z& T( \8 l) `0 N/ z2 `4 O     排序前
     9 8 7 4 5 6 1 2 3
     排序后
     1 2 3 4 5 6 7 8 9
! k- Q/ T1 Q" ]* w9 c  ]  z" P
6 {: Y+ j, |2 f* _这是冒泡排序的最简单的形式，下面我们来给他优化一下。

优化冒泡排序1

优化方案： 如果序列已经完全有序，可以提前终止排序
& U4 D% t" Q% ^$ F- t* [0 P* ~
# |4 W2 @( f: k$ Y; t3 c2 n来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                       
                        boolean b = true;
" `& p( K1 A, g* }$ p) e                       
; G2 O5 t. G# S0 Z6 C* e  z                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                       
                                        int index = array[begin];
2 T; B- O( x  f                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                       
                                        b = false;
! g! T; t4 Z" _5 |8 w5 R0 y7 s0 g( L' v                                }
                                if (b) break;
                        }
9 t9 x4 w: G& Z" \1 B6 M                }
9 r- k' B& ~$ |, l8 f3 L) D                return array;
        }
3 G1 }: C- h3 u9 \* L
& A& Y# O) X. P2 V5 i$ [& ?$ @优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。

当然这个排序还是可以有另外一种优化方式

优化冒泡排序2
& P0 y* N5 }  d# o3 c% C1 C2 C: S
优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。
9 q* n4 s1 k+ [9 z% e% g6 \
来看代码：        public int[] bubbleSort(int[] array ){
2 K5 @5 W$ U7 t# F5 A# Y" |8 o7 e" @1 r6 L                for (int end = array.length; end > 0; end--) {
                        int j = 1;
7 S6 q+ c# A3 F5 ^' b0 n                        for (int begin = 1 ; begin<end ; begin++) {
5 t2 `" X$ M0 `% {" V9 D                                if(array[begin]<array[begin-1]) {
) K4 i! E& `) e5 D                                        int index = array[begin];
1 e7 r& l& N, k                                        array[begin]=array[begin-1];
' j- P- f* e7 S. |5 e7 I; A                                        array[begin-1] = index;
                                       
                                        j = begin;
                                       
                                }
                                end = j;
                        }
* s4 x( J& ?  V" P                }
                return array;
1 G% {( c. n7 {" Q: z        }

1 W  ?9 B- z# k. l& u优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。

/ c0 V% E" Y0 y% v/ N冒泡排序属于稳定排序，为原地算法

3 s* i0 d  t# |# _/ _. @1 Z; r注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
8 k; l6 Y  `( b# ]* Y0 z7 Q! Y3 f原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872


( ]5 `8 _7 N; u2 k, Z* A1 x' @

柠檬草lll

发表回复