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

杨利霞

10大排序算法——01冒泡排序（Java实现）
) ?8 K2 ~1 E0 H7 V4 F8 X冒泡排序（Bubble Sort）

冒泡排序也叫起泡排序

, |# x8 \8 L0 }' @冒泡排序的执行流程

. W! s: D+ F/ [" V2 N' Q1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
' Z% X/ C2 b  I. z4 i0 X8 ^
2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

来看代码：        public int[] bubbleSort(int[] array ){
) h% p1 b$ |1 D: r% X; a                for (int end = array.length; end > 0; end--) {
                        for (int begin = 1 ; begin<end ; begin++) {
$ H$ ~3 i9 I# R* H' }7 m                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
. P% B; q; }, |3 d& S( c  t7 {                                        array[begin-1] = index;
4 C; n- j/ n: b" V; v: T7 t                                }
) b' N7 j9 v) j3 D5 [, @                        }
                }
) w( [, p9 i" T/ H. L                return array;
        }
/ v1 {7 I4 p! t- H$ O
调用一下试试
        public static void main(String[] args) {
& ]' u3 b! V5 H3 \% W                BubbleSort b = new BubbleSort();
                int[] array = {9,8,7,4,5,6,1,2,3};
& x+ M  ?; D5 {6 |" L                System.out.println("排序前");
+ q+ C$ P% l4 }+ K3 m5 \% b: e5 o                for (int i = 0; i < array.length; i++) {
& f4 h( Z( f  ?& s  Q                        if(i!=0) System.out.print(" ");
; ?) T6 [: k' B: S7 _# M! D                        System.out.print(array);
                }
               
                b.bubbleSort(array);
! k3 x- m0 C0 x  }5 i) P- g               
                System.out.println("\n排序后");
1 P9 C* P$ X% v2 [, I: O3 S                for (int i = 0; i < array.length; i++) {
6 e& |" [( `3 W* E: E                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
' \4 ~5 v9 k- r4 n9 v                }
        }
* f" E; h  E/ }8 e8 M2 B
) K; q; F7 T' T; X; ^
运行结果：运行结果：
     排序前
+ S3 T5 ?/ T4 n3 j! i. B     9 8 7 4 5 6 1 2 3
2 t( w3 m! p1 P6 d     排序后
  C) D. G4 \5 B( i     1 2 3 4 5 6 7 8 9
4 l1 O$ B& i% o( O
这是冒泡排序的最简单的形式，下面我们来给他优化一下。

7 x# Q8 [4 d8 N/ U. A8 ^优化冒泡排序1
+ W6 h0 y8 _6 z( u% Q* B
优化方案： 如果序列已经完全有序，可以提前终止排序

来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                       
                        boolean b = true;
                       
                        for (int begin = 1 ; begin<end ; begin++) {
8 b: c( N; f1 R! d% \8 A* Q  ~7 N                                if(array[begin]<array[begin-1]) {
                                       
                                        int index = array[begin];
3 o% v8 k1 ]2 N7 z4 N                                        array[begin]=array[begin-1];
9 C" o. }" L3 g                                        array[begin-1] = index;
                                       
                                        b = false;
                                }
& X* `# ?, f/ r/ D  N6 p                                if (b) break;
2 \- F) Q9 G& T7 j4 @                        }
                }
                return array;
4 v. m1 j) q$ I5 v! }6 _6 x6 C5 L% p' J        }
, E( V& V) c1 W1 N; v3 I  b
优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
$ R9 B0 J8 C3 p5 w3 M4 P
当然这个排序还是可以有另外一种优化方式

6 w5 k6 Y' ?& U! `# E& R" _8 N优化冒泡排序2
2 H0 Q3 C5 Q  V5 u4 g9 ?
& D; N) L9 Y4 z( \9 ?# a6 E; h" t优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

3 a! u, ~% i1 R1 M7 i* z来看代码：        public int[] bubbleSort(int[] array ){
, d' A( C9 x/ `5 P7 f( ?                for (int end = array.length; end > 0; end--) {
* K+ d: f* @6 \: \9 L0 s# c  F- Z7 h                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
. V# N0 z9 _; T  K5 D5 \% |- a                                        int index = array[begin];
$ W# |, O7 n& ?7 Q                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
7 A" D6 k. m2 H+ H( c) @                                       
                                        j = begin;
# L- S" p. Z2 z1 R4 o8 Z                                       
' C, G8 d2 @3 L& [# s2 K9 R                                }
) h* a. H6 [/ z) i* }. A6 m                                end = j;
0 v" o* F5 _4 E2 l. S                        }
# \/ c( f4 |% t0 @! S: K7 y                }
: E3 c$ m% F  i) g& x# E                return array;
$ Y/ F1 M& B1 p5 p        }

1 W, @: u* O* O/ J6 J优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。
, D/ E: ~2 V6 \( r
冒泡排序属于稳定排序，为原地算法

; Q5 G  K7 Z: [注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
1 x7 ?8 h" `( r3 g原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
1 O$ p! c) U" |8 L# D3 G3 t* }

. y% Q! P- A$ L6 O! \! @$ M5 s9 A% R6 u

柠檬草lll

发表回复