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

杨利霞

10大排序算法——01冒泡排序（Java实现）
5 M' M9 J8 j, Y6 a冒泡排序（Bubble Sort）

: M2 x$ y* l- D3 S6 @: Q8 \# W' q冒泡排序也叫起泡排序

) V5 v/ |+ G( e; k+ `冒泡排序的执行流程
' p" ]& h4 ~. C- a
  l# M4 _6 X4 n( j5 C" h' E1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）

+ R' S/ h4 [1 N) q! o8 a2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

- ~: {! O) Y- @7 J# o/ a& v) v来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
" J" ^1 P8 B4 t* i) Y                        for (int begin = 1 ; begin<end ; begin++) {
) ]+ Z; X( |; i) A                                if(array[begin]<array[begin-1]) {
) \4 K9 M; o  ~2 F5 s; w( A: ]4 D                                        int index = array[begin];
+ c, R1 b$ L) ^% X7 l9 V                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                }
$ d: X% t% N# V1 C: h( r! K                        }
# w2 p, ~+ t, ^) J                }
5 V3 o, ]" Q: z8 r; h5 G- _; p                return array;
        }

8 L1 }! _1 |+ T+ o' X$ \调用一下试试
6 i$ C! u; I' H! n) H% f        public static void main(String[] args) {
                BubbleSort b = new BubbleSort();
; s8 q. E& u; H0 y, i/ L$ ~                int[] array = {9,8,7,4,5,6,1,2,3};
                System.out.println("排序前");
9 n) W. T' L2 x' {, t+ P                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
               
                b.bubbleSort(array);
4 Q: D8 W: {5 H" s               
! ~4 H% n- ^0 {  W6 j                System.out.println("\n排序后");
$ \; T) }6 J% G) e7 J                for (int i = 0; i < array.length; i++) {
7 ]4 o% e( r+ p( f' ?                        if(i!=0) System.out.print(" ");
! g4 k' r$ H, c                        System.out.print(array);
                }
        }


运行结果：运行结果：
  F) u" L# ~6 j/ y     排序前
/ X8 {' N' {! {& h2 w# l& B5 @     9 8 7 4 5 6 1 2 3
     排序后
     1 2 3 4 5 6 7 8 9

2 {1 v% n7 e2 `5 S! i8 I, r1 N8 i8 l这是冒泡排序的最简单的形式，下面我们来给他优化一下。

优化冒泡排序1

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

来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
: D* ?, ?% k# c6 Z2 r( z) H                       
                        boolean b = true;
! z" R  l4 q+ z" L                       
5 {" F2 r7 D/ Q7 H' {: `( u$ G% K                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
) U- t3 w% h. L8 w/ {4 y0 A, `. ]* B                                       
0 R/ N/ A/ D5 f8 p9 \                                        int index = array[begin];
2 s. E8 t/ P+ f                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                       
                                        b = false;
                                }
                                if (b) break;
) h- A% T5 M4 v. G6 Q! {                        }
& n/ I2 E; ~1 k8 P* A) R                }
                return array;
        }

优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
6 ]* t8 N& ]) x
当然这个排序还是可以有另外一种优化方式

$ H: z" j4 r! m' D  U9 X优化冒泡排序2
0 u+ H% l3 G. j4 f3 |# B% @, _
# _, i4 j  N& m! e! P0 e3 r优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。
7 [) x3 L) [+ S; d2 W1 E4 G! Y
! u& t8 p/ S# f7 s$ P# Q( ~来看代码：        public int[] bubbleSort(int[] array ){
; T2 o: ]9 h' G! Y, \4 z# H" ~( j                for (int end = array.length; end > 0; end--) {
                        int j = 1;
$ d8 r+ D; E" ?& b* r* x                        for (int begin = 1 ; begin<end ; begin++) {
- E" b& L  k9 T                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
  n7 x" ~9 Z; \9 {; W% l                                        array[begin]=array[begin-1];
4 ]* D, U' k6 A$ `' A2 j, B                                        array[begin-1] = index;
7 z& P/ X& P/ a# z0 P                                       
                                        j = begin;
                                       
                                }
! R8 M! u5 X1 ]8 a                                end = j;
" \* w. u8 o% ^6 E                        }
                }
                return array;
        }

优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。
" w, V) }  z+ G$ C' k
冒泡排序属于稳定排序，为原地算法

/ o# O, N. G' \* b3 b3 B注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
* J! E, y+ d; Q原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
3 W8 P! ?  L. c( \! P- g
/ w8 u" E7 p6 e& @8 R

柠檬草lll

发表回复
0 m. E% K9 g6 p5 B/ \6 l$ \7 R: N2 y