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

杨利霞

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

5 V' b/ _' T' F冒泡排序也叫起泡排序
% a" D3 p- o2 G- O' e  T: k) U! V
冒泡排序的执行流程

  ^0 q3 o. x* O7 y  s  v7 q6 f1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）

2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序
! v1 v* T9 \, g8 a
, G0 O9 ~( u2 j3 W7 d7 O来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
# s8 c: o' E9 m                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                }
* N) \6 o& Z$ @- Z                        }
                }
                return array;
" s7 `4 i/ Q8 |5 d* O        }

7 f4 i  l0 A4 e调用一下试试
! V+ V3 K" W1 z        public static void main(String[] args) {
                BubbleSort b = new BubbleSort();
                int[] array = {9,8,7,4,5,6,1,2,3};
" B, e% o9 j+ Y) E( P# R                System.out.println("排序前");
                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
4 `) \- O8 U6 s3 @. Z                        System.out.print(array);
                }
  W! J  @! l/ C6 k3 Z               
5 X4 v+ q7 k* _" A1 w                b.bubbleSort(array);
+ u  [6 i. v. X) x* {% z, ]% {- O" X8 B               
/ y: ]  ~3 f2 U2 F( s7 k# v                System.out.println("\n排序后");
6 l& Q6 n# H# E& f; J; ?( k, e: F                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
8 d7 w7 L/ w8 w  c9 ?* J                }
        }


运行结果：运行结果：
     排序前
+ \% W( F& d$ F1 k     9 8 7 4 5 6 1 2 3
  f/ o$ v, i+ u6 k; m     排序后
     1 2 3 4 5 6 7 8 9
8 i) n1 S% T8 ]5 l: |  \
1 n1 D5 E5 K, y! M# q0 A这是冒泡排序的最简单的形式，下面我们来给他优化一下。

( c# n! h7 M* D/ k优化冒泡排序1

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

来看代码：        public int[] bubbleSort(int[] array ){
0 d' q$ m. g& P" g                for (int end = array.length; end > 0; end--) {
                       
                        boolean b = true;
                       
# j; J$ Q4 W. y& `+ u                        for (int begin = 1 ; begin<end ; begin++) {
8 Y7 Q/ j% p" N( H, j                                if(array[begin]<array[begin-1]) {
) ]) G7 C9 S3 L; }: A8 H% Q                                       
2 ^9 W# h  v0 D; w                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
                                       
! o8 H' w, \4 W8 M8 ~" k( |                                        b = false;
                                }
                                if (b) break;
1 w3 m: B( e# v+ [                        }
                }
( ?; T# S9 e" M! r9 M- l6 |$ I                return array;
        }

优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。
! z$ j) R/ D# y/ S* F
当然这个排序还是可以有另外一种优化方式
) I5 r' S1 @8 x' ?( r! p4 D5 B
优化冒泡排序2
' J) X" T+ E* |+ D* D  i2 Y
/ G* k6 Q1 @1 E% F+ ^% R. T优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。
( \5 J1 y* w& n+ l3 k$ x
% u0 X6 G) a5 K+ g来看代码：        public int[] bubbleSort(int[] array ){
3 x  s$ K- }/ E: W3 q; Q                for (int end = array.length; end > 0; end--) {
9 b: R/ s# \( e5 A1 y                        int j = 1;
9 b2 j8 |. ]* u. D+ s; l                        for (int begin = 1 ; begin<end ; begin++) {
( L& _2 K% [) |, ]                                if(array[begin]<array[begin-1]) {
6 h( V+ W3 e4 e/ O( m! R3 z9 E4 \                                        int index = array[begin];
/ f; J. x1 E$ [0 M9 c( A$ |                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
& A' R# R/ d  l                                       
6 ]; m% D+ p, J, l                                        j = begin;
( T; g  }7 g) A( z) m  G9 L                                       
                                }
                                end = j;
                        }
' Y1 y2 k1 s4 d3 H8 Y5 }                }
8 F8 }% R8 m; r+ Y3 _                return array;
; t, J9 ^/ A8 S: n        }
- P) e# R" R; b, W& \, P  a
优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。

冒泡排序属于稳定排序，为原地算法

* L$ D  Y/ s2 o; y- Z注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
5 F" n: s1 H- K
+ A: L+ O* }! k9 @- z

柠檬草lll

发表回复