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

杨利霞

10大排序算法——01冒泡排序（Java实现）
, Q* }, U/ W! t冒泡排序（Bubble Sort）

冒泡排序也叫起泡排序
# a, E+ W; W9 y! ~
冒泡排序的执行流程
' s  v$ O% b; }: y+ Y0 n
  I. j3 @' c4 [" o! N: t) E1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
% V; d$ I9 Q" V9 j8 F) e
2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序
& H% Z  f" n  |$ A* ^
来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
9 r  `5 _/ u; n+ m. [* _                        for (int begin = 1 ; begin<end ; begin++) {
7 n$ x' F; o# g6 _* b                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
9 O1 M6 k  ~+ |                                        array[begin-1] = index;
' @" |5 {4 w* c5 `; a  }                                }
: A) t6 A# I4 P. _$ V                        }
) {- s. H2 P5 H/ L' J0 m                }
( h) `" A# M7 L4 g; h& J0 u                return array;
        }

调用一下试试
        public static void main(String[] args) {
9 `, o* Q8 w3 u1 Y                BubbleSort b = new BubbleSort();
                int[] array = {9,8,7,4,5,6,1,2,3};
1 ^! o; n1 G3 f+ S8 D' i7 m& V( e                System.out.println("排序前");
                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
8 {7 F4 l6 q1 R) \) f                        System.out.print(array);
                }
               
9 V  d' a- V: l" I                b.bubbleSort(array);
               
                System.out.println("\n排序后");
" U  }( Y+ h* z4 }' r6 p                for (int i = 0; i < array.length; i++) {
3 v# M2 q7 G9 y$ h                        if(i!=0) System.out.print(" ");
; A: U% A$ u' P: Y7 T0 ?6 @2 c                        System.out.print(array);
                }
        }

+ J% I$ H6 O9 g
8 C1 P* E2 h+ A4 C运行结果：运行结果：
     排序前
7 E# Y" H+ D; l8 J" D1 G     9 8 7 4 5 6 1 2 3
     排序后
     1 2 3 4 5 6 7 8 9
4 @  I# Z. {, c* o3 C' p
这是冒泡排序的最简单的形式，下面我们来给他优化一下。
( {9 E$ g+ w( w
优化冒泡排序1

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

来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                       
; M$ s' Z% L7 _7 I2 Z# J5 Z4 E                        boolean b = true;
9 Q) n* l$ ^9 m/ y                       
* |1 z$ g/ r4 ?0 Q) T+ A                        for (int begin = 1 ; begin<end ; begin++) {
" s) b5 G# d0 n8 n1 \8 L                                if(array[begin]<array[begin-1]) {
* F- F: v6 T3 t8 u/ }& d+ H/ N                                       
                                        int index = array[begin];
: P0 w7 J" g0 P* D: P4 u+ p                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
" s- G/ ~0 p8 r; F) e( p  u' i& t                                       
                                        b = false;
3 K# K* H5 {5 }) O$ M                                }
3 E" [0 }' p; t, z6 G, N                                if (b) break;
                        }
. j" O( F8 U$ `5 ~/ O7 f# w: L                }
                return array;
' G: `/ h8 {8 |2 u+ B        }

, Y6 L4 N5 \' W5 y% A) l( i# J, n优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。

: b2 D" U* n7 A1 v当然这个排序还是可以有另外一种优化方式

优化冒泡排序2

7 C( S* h2 P+ m' ^优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

来看代码：        public int[] bubbleSort(int[] array ){
( G. H' j* J3 V# t$ c! {                for (int end = array.length; end > 0; end--) {
                        int j = 1;
2 i+ ]. t: N3 Y/ w$ n0 I0 Y6 G                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
$ T" q( X8 y% m* s9 i                                        array[begin]=array[begin-1];
* ]. h% R* Y$ l8 O1 p/ p. R                                        array[begin-1] = index;
                                       
                                        j = begin;
                                       
                                }
                                end = j;
' ?/ m6 D. g# \! {9 e                        }
                }
                return array;
& p1 [, B2 W, f. x5 y: Z        }

优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。
0 q  @0 q2 {4 a* z/ z
冒泡排序属于稳定排序，为原地算法
+ _/ J( q; E/ s$ I8 J7 |1 [/ q% ]
! K3 R8 T3 U' f' A6 s' j  v注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872

% v0 j0 [2 p( L+ T6 c* g
* O* c4 v; M- c$ `5 E$ e

柠檬草lll

发表回复