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

杨利霞

10大排序算法——01冒泡排序（Java实现）
冒泡排序（Bubble Sort）
/ w6 o" s- c- g
/ D# I) I; {$ S7 z冒泡排序也叫起泡排序
7 Q7 o  X2 S. }; Y6 s
1 W$ a5 q  J8 _' w. z冒泡排序的执行流程

1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
, l) ^- G: z& _# h) Z6 j( b
* A6 B; A7 _! D/ c0 T, p2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序
% K* q$ \  C' ^" S: |$ r, q4 f" }1 K, G
来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
4 c1 j  z3 j8 s: Y9 d& s                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
" O! Y- ?0 Z# D/ Y( _, G! D                                        int index = array[begin];
                                        array[begin]=array[begin-1];
% b1 O, J* P, s                                        array[begin-1] = index;
7 ]0 u' G# R. q/ P; h                                }
! A1 \. C( R/ \" Y, C8 {: n3 H                        }
' O" l( Z/ |/ D( `* D                }
                return array;
% z- f/ n5 Q. E- Q3 R* T        }

: L" \) d% }, M6 X  S$ a* m调用一下试试
- U- M7 Y5 _& {- p& ^( F9 J7 b        public static void main(String[] args) {
! ^1 x7 b4 p# Q8 m$ z  ?1 B                BubbleSort b = new BubbleSort();
                int[] array = {9,8,7,4,5,6,1,2,3};
: C5 \# f; T1 N" _4 Z                System.out.println("排序前");
$ N# b; {+ Y; D                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
, `; ]: b$ @4 @+ u# ?                }
               
1 a) \1 B4 W) E                b.bubbleSort(array);
               
5 d5 M% ]) w7 G                System.out.println("\n排序后");
                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
8 C) L8 G( x4 v8 z                        System.out.print(array);
6 {. n# ~$ V! h                }
# l; E5 r5 W' B; ?        }
. R3 a8 E0 k* Z% C% Z0 x

4 \" k2 G0 s  I: R4 G运行结果：运行结果：
     排序前
$ c  }% f& Z& C5 H3 ?     9 8 7 4 5 6 1 2 3
7 ]: b: ]6 K2 m0 e) u* r2 F     排序后
! J! j4 G) }3 N" E8 L     1 2 3 4 5 6 7 8 9
5 E+ a  w4 Z' W$ h, {
" E  p4 q: L, e这是冒泡排序的最简单的形式，下面我们来给他优化一下。

优化冒泡排序1

9 J3 I) |6 _. `优化方案： 如果序列已经完全有序，可以提前终止排序
1 K7 A4 h8 Q- [4 F( ~1 U* S
来看代码：        public int[] bubbleSort(int[] array ){
. o4 Y% d4 Q. z1 q/ b3 t  a+ ]                for (int end = array.length; end > 0; end--) {
. a" Z' a3 v9 B% Z' }# T                       
4 b. p8 a# B' G) _& t/ Y8 J2 N4 D                        boolean b = true;
                       
' i% x( M1 r# }+ D! b                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                       
8 h4 N& |1 \" q7 s                                        int index = array[begin];
/ e+ I  u1 p( O                                        array[begin]=array[begin-1];
, j1 B* y, F/ ~7 c                                        array[begin-1] = index;
0 \; b# l* d! C                                       
8 F6 ?: H- A- Q3 ~3 _% q/ g5 X                                        b = false;
) T" G4 B+ H( s1 B0 q                                }
! _- K/ S: O, }3 S9 G                                if (b) break;
6 S( u+ X1 n9 C! Z1 ?                        }
4 }# q' r+ {# p0 \, P% n/ m                }
                return array;
        }

优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
4 I3 x3 k" N$ V* z, b+ s2 t
# r# u4 v# m7 b5 ]/ U' [当然这个排序还是可以有另外一种优化方式
$ ?& {. N, [5 l$ j6 S( S5 i
* W* Y9 r: ?% ]优化冒泡排序2
7 G, k3 R; ~: K1 E
; Q( z2 c6 Y# b0 ]优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

" m- `% c. g" [8 O来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
4 T2 E+ m, P) `8 W  X                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
; N* s1 F! T# j# R. \9 H                                        int index = array[begin];
( Z5 M& T3 R$ A2 Z+ \                                        array[begin]=array[begin-1];
' [  @9 M$ y) R: U7 q) @                                        array[begin-1] = index;
# F) O4 i( K2 }+ H" `+ n3 G8 v# R                                       
3 d: j5 Y! C6 |                                        j = begin;
                                       
                                }
8 d9 s* g0 n, s6 E1 m5 C                                end = j;
/ U; a$ q6 P$ U5 B& H) ^0 ?                        }
                }
  q% `: h' S0 O' [& R8 A                return array;
        }

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

冒泡排序属于稳定排序，为原地算法
+ C/ a7 I0 r* y3 f/ x5 {2 f& e
注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872

柠檬草lll

发表回复