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

杨利霞

10大排序算法——01冒泡排序（Java实现）
: i$ V' t- Q8 `$ t' l% Q1 B* {: w+ d  ^冒泡排序（Bubble Sort）
1 Z3 h" R. F! J* ~# l
0 x) j2 u. m1 ~冒泡排序也叫起泡排序
" }3 }7 x" M+ i, c1 a5 |, d
0 S2 i* E9 y8 ?9 t冒泡排序的执行流程

: ], N6 l7 ^# J2 W9 P1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）

2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
& z- x9 h; g, Y1 O2 z1 ?                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
) H4 `, ^% g& G6 N8 i2 @                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                }
                        }
9 d: G- H/ v  o( X9 x4 |                }
" Q. S* s% Y: L+ w; r                return array;
0 J% ?: ^4 X' G& U% e+ ?        }

调用一下试试
  A. r" J! f4 r* Z        public static void main(String[] args) {
                BubbleSort b = new BubbleSort();
                int[] array = {9,8,7,4,5,6,1,2,3};
                System.out.println("排序前");
0 D- `( d6 W# l7 b3 s9 u! O' o; T                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
               
( ^' C) b& ]# G3 y4 P9 T                b.bubbleSort(array);
# [) B$ w6 D: J' @7 ]! {- F               
                System.out.println("\n排序后");
, u+ H! ]' J2 B% o& ~2 ]( [" y; `                for (int i = 0; i < array.length; i++) {
' r2 x" Z4 E& }" \* l4 M( `                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
& o0 L8 o4 ?. _$ t8 K; {* D4 n                }
* B7 _! |6 n6 v4 }- x, y4 [        }

9 E5 t# I- k7 {! B$ ?  _
- B, z( ]7 Z$ B  L运行结果：运行结果：
& n0 f7 `/ Y  `, Y( u     排序前
9 h. s- T- a! `: Z! X9 W     9 8 7 4 5 6 1 2 3
' _1 `9 {/ K2 A' x$ Q  s! u6 s8 |3 ~: _     排序后
     1 2 3 4 5 6 7 8 9

* L. q1 U7 ?/ I. M4 @% i  p) m+ \这是冒泡排序的最简单的形式，下面我们来给他优化一下。

优化冒泡排序1

) @2 f# V8 n2 h7 l) w/ x# \) S7 j优化方案： 如果序列已经完全有序，可以提前终止排序
; k% t  I) Q# I2 I
来看代码：        public int[] bubbleSort(int[] array ){
8 {( H6 E( k* E& D# K! r. \                for (int end = array.length; end > 0; end--) {
( u0 {3 U" T2 }3 J1 I( \/ L                       
                        boolean b = true;
                       
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
7 E) W6 r( m0 [5 V+ u4 d: H3 {9 Q                                       
                                        int index = array[begin];
$ R0 _/ _+ h7 d% T$ {$ R                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
% l& [. n* i, v                                       
2 m7 [" D4 `5 N6 d" m                                        b = false;
9 |! n, F  X+ a1 e# ^9 R, N7 T" c                                }
                                if (b) break;
                        }
# [: v  ~  _1 y6 C  S                }
; N; Y+ Y3 R1 o7 m& u                return array;
        }
5 P9 i2 _" L- h) V, t8 z
优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。

当然这个排序还是可以有另外一种优化方式

: A/ E$ X& ~% T) \9 K优化冒泡排序2
' u0 t; ]# Z) F  g! W/ {; x+ x
5 i5 o4 k0 x6 X+ F  H优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。

来看代码：        public int[] bubbleSort(int[] array ){
5 [5 o/ D1 M- i2 \                for (int end = array.length; end > 0; end--) {
                        int j = 1;
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
! @& P  o8 v" ]) g                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
. l. [$ o  S6 ~" u" q. p" \                                       
                                        j = begin;
                                       
                                }
                                end = j;
                        }
3 ^( q' z% P) J1 ~4 C                }
                return array;
        }

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

; g0 E* k5 _$ i3 p4 @% R$ C冒泡排序属于稳定排序，为原地算法
4 ^9 w. B" m5 Q( t
注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
" f* Q  g0 z5 k/ G$ ?
! m1 [8 f$ S+ r0 c6 l" e7 k. C
& p$ d6 N2 M, d. {

柠檬草lll

发表回复