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

杨利霞

10大排序算法——01冒泡排序（Java实现）
冒泡排序（Bubble Sort）
9 u% s5 m6 s: ]6 @% c  n6 B* l2 m2 |2 ^
8 b/ g. k8 B( _: ]' g! @冒泡排序也叫起泡排序

冒泡排序的执行流程

3 H5 l! t# Z1 f3 W& J( t1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）

) a8 |2 c" T- k  F3 A2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

' {( A8 s: |7 }' I7 q0 j& {" T来看代码：        public int[] bubbleSort(int[] array ){
6 G" U& y$ b+ ~! G8 b# @                for (int end = array.length; end > 0; end--) {
                        for (int begin = 1 ; begin<end ; begin++) {
6 {1 }  Y+ [' Z1 T( h) Z/ C: ^( h                                if(array[begin]<array[begin-1]) {
. P" m7 l7 v! M                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
- t3 t' A6 m- x; H                                }
$ h% n+ {* i2 j- @$ J) A                        }
                }
8 T- u: T& x9 f" }                return array;
: v6 L& ~( s! b2 J  n: B" ?% I1 v        }

调用一下试试
        public static void main(String[] args) {
                BubbleSort b = new BubbleSort();
                int[] array = {9,8,7,4,5,6,1,2,3};
                System.out.println("排序前");
                for (int i = 0; i < array.length; i++) {
/ I; H7 G4 Z" J* \8 e; e% n9 M                        if(i!=0) System.out.print(" ");
4 u3 r7 I8 J  I& _) T. ~" \  ?1 a                        System.out.print(array);
3 v7 X7 ^4 J+ _; Y. ^                }
               
5 ^- Y, K/ d' Y0 ^) ]  t                b.bubbleSort(array);
8 F7 @& Z; }" L, J# S0 B               
9 {7 q7 W* D, ]! _* U5 ^6 e                System.out.println("\n排序后");
                for (int i = 0; i < array.length; i++) {
, _8 R. B' a0 u, h                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
7 H0 @9 l8 ~* }4 o# [' y- b                }
        }

/ e- i4 _7 e& k8 H
运行结果：运行结果：
     排序前
  h1 M$ u& [, q2 M5 u7 Q     9 8 7 4 5 6 1 2 3
. Y+ i  Q, L" ~7 {3 v     排序后
     1 2 3 4 5 6 7 8 9

0 W% G% D$ `' g* n0 Z/ n# f这是冒泡排序的最简单的形式，下面我们来给他优化一下。

优化冒泡排序1
+ G/ v2 N; J5 v* ?
9 o& i3 C3 U9 [- O3 Y, [优化方案： 如果序列已经完全有序，可以提前终止排序
) ?9 ]+ G( D1 I) k
来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
" w! {3 s( C2 u# u* R: I8 Z                       
7 C" F; h. E! _/ Y6 H' ?  d3 {                        boolean b = true;
                       
* g' O6 |8 K' P8 l1 W! b  C  N                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                       
  n+ `* H9 q- e2 y                                        int index = array[begin];
                                        array[begin]=array[begin-1];
/ _& W4 n2 _' Y8 u, ]9 {/ O                                        array[begin-1] = index;
. _% b/ u7 Z1 w( n* }                                       
" y* t- `' o" |0 E" H+ j' B                                        b = false;
                                }
                                if (b) break;
" a) ?( G, t  i9 {0 o( K9 U' B9 a                        }
1 z/ m  C' T& w9 H; H: V% l                }
( w( o8 q: O% H  ^! w4 |; X                return array;
/ T, n; y" [$ \/ X9 T2 Q3 i        }

% c7 i$ Z+ {7 A- Y$ S# I优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
1 ^2 {* J' [  T* \2 J
当然这个排序还是可以有另外一种优化方式

2 A8 V/ J% C2 u7 e2 ~8 c9 S9 l优化冒泡排序2
7 D5 o, s& Q* f! U7 W. S: [
9 a: i& h( c" f' q6 [优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。
+ W) d/ j1 h4 z1 ~3 @* e; q4 y
+ R: ]+ X7 o) \+ C# n来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
6 k7 h& b- I* D+ @+ W* x7 r                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
, v# w, w/ s; l; b2 {) w                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
0 ~2 G! p# ]4 d' [# ]                                        array[begin]=array[begin-1];
6 K2 Z) {. M( x" K                                        array[begin-1] = index;
                                       
                                        j = begin;
) N; a$ D8 |$ ]5 A& y( b! Z- b0 d  _                                       
; z/ K2 y. t7 S! G  N                                }
                                end = j;
                        }
9 ^+ o: D9 {$ w$ s. O/ s, ]                }
% X% s; {, p' h  @2 H% L                return array;
$ g! R6 _3 L% ^/ O8 w. `        }
- h0 p4 j9 q# m" D% n6 L
. }$ G) w: E; g& C优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。

冒泡排序属于稳定排序，为原地算法
& _  a0 O5 Z9 c$ O, V
注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872

柠檬草lll

发表回复
3 v5 n5 z9 Z/ B8 m