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

杨利霞

10大排序算法——01冒泡排序（Java实现）
/ W& c9 Y( Q* `4 k冒泡排序（Bubble Sort）

冒泡排序也叫起泡排序

% w/ d4 z" @; k: ]  h7 m- \冒泡排序的执行流程

6 z0 M/ b7 ~2 y% e1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
* q% O) c% S. u! D" g5 g$ K
2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

$ k$ k% t8 s8 Q来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
+ L8 A, q% i0 q                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
% R! P8 u) i/ d8 ?/ Q, S2 `6 |8 z                                        array[begin]=array[begin-1];
# m% F) U, }  Q, P                                        array[begin-1] = index;
                                }
                        }
/ `0 F$ M- q9 e& N* c                }
                return array;
: n1 F* x4 r% D9 `- e& E$ c        }
$ f$ [' R( z# v% F
调用一下试试
        public static void main(String[] args) {
2 U8 u3 k0 \0 ~( V+ P4 f                BubbleSort b = new BubbleSort();
                int[] array = {9,8,7,4,5,6,1,2,3};
                System.out.println("排序前");
3 k% C# b& u' o                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
9 G# {. A% T! U1 L% M               
                b.bubbleSort(array);
1 B( M% |* y4 U7 i% \# X               
                System.out.println("\n排序后");
                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
5 Y9 a! J8 y8 i5 G) l: g4 f                        System.out.print(array);
                }
        }


运行结果：运行结果：
( x) {+ y0 `+ z( G) {; T5 `  I) X     排序前
     9 8 7 4 5 6 1 2 3
     排序后
     1 2 3 4 5 6 7 8 9

这是冒泡排序的最简单的形式，下面我们来给他优化一下。
  h" W$ q; u8 i* O: b  `5 n) c
优化冒泡排序1

优化方案： 如果序列已经完全有序，可以提前终止排序
# i* N0 z& G  P, o( Y+ `' X8 z
来看代码：        public int[] bubbleSort(int[] array ){
# v/ X) [  l. W- ], b                for (int end = array.length; end > 0; end--) {
" j3 ^3 J' X6 ~* b* J4 S                       
' _, `9 D0 Z3 J. _! Q# n) E                        boolean b = true;
                       
                        for (int begin = 1 ; begin<end ; begin++) {
2 P; R3 W( h  x, l( {                                if(array[begin]<array[begin-1]) {
0 L3 F  o2 V* p# @+ e0 Z                                       
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                       
. N, j6 Q. G! i+ P6 w                                        b = false;
                                }
                                if (b) break;
                        }
                }
                return array;
        }

优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
8 @8 T- Y9 l$ e- c
当然这个排序还是可以有另外一种优化方式

优化冒泡排序2
: z6 C& i2 t: |) y0 W0 u
优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

+ ?: c& l& Y9 q9 M4 c1 S/ B) F来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
$ t) ^. l. |+ r/ }/ {0 b                        int j = 1;
# Z  S( M; M' c( |( {5 r- ~                        for (int begin = 1 ; begin<end ; begin++) {
3 o' z& a4 [( K. l3 F7 S7 V                                if(array[begin]<array[begin-1]) {
4 z: r1 `7 |. {; w$ b: J5 L& ~$ n                                        int index = array[begin];
% p( I1 \* H6 Y  o; p                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
5 g4 Q' ^2 K- o3 G                                       
                                        j = begin;
                                       
                                }
6 D  g' W% b! l                                end = j;
                        }
' n& J3 U# o6 D- R- r+ z                }
                return array;
# p6 J8 S0 C+ d, Q1 K        }
! R/ G( u! l9 B
2 C$ o2 o- F! b& s- ^优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。
6 L* [" A$ e. Q& g
冒泡排序属于稳定排序，为原地算法

注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
; @2 U" `: b2 p" n' b! t3 r原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872

& f, |9 b8 e6 l8 ]: ]. z2 k
! }3 ~9 i4 I' a! b; V* x8 A% e

柠檬草lll

发表回复