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

杨利霞

10大排序算法——01冒泡排序（Java实现）
6 w; v5 W$ P# S* Z冒泡排序（Bubble Sort）

$ {; d( ?9 M) U$ |冒泡排序也叫起泡排序

6 D, \% ~' i6 ~$ \: ]6 i7 w冒泡排序的执行流程
. P! K" }+ U% [$ b/ B
1.从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置。（执行完第一轮，最后的那个元素就是最大的元素）
; _. g- Z5 c- O& P5 A2 H
2.忽略从步骤1中找到的那个最大元素，然后重复执行步骤1，直到元素有序

来看代码：        public int[] bubbleSort(int[] array ){
9 P  Z+ ~  r8 C: {9 c5 ~4 c  `5 o                for (int end = array.length; end > 0; end--) {
) M2 q$ [) {+ l, o8 x3 Y7 u                        for (int begin = 1 ; begin<end ; begin++) {
/ l$ G$ ^4 d9 E; [# g# I( ?. {                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
. Z: D" d% ~9 G                                }
' D. P# h! B' |- L# t3 w                        }
                }
4 s+ P8 h1 _% {( H9 c5 J" T) h                return array;
# j9 L2 K3 }2 a! O        }

调用一下试试
        public static void main(String[] args) {
                BubbleSort b = new BubbleSort();
5 x# I* v) V- k! x& b' U2 X                int[] array = {9,8,7,4,5,6,1,2,3};
5 n. h7 Z2 ?% {7 }0 V0 L* A. W/ r; o3 \                System.out.println("排序前");
  X8 w- P! p+ u                for (int i = 0; i < array.length; i++) {
! m) }5 Z/ c! O4 ~4 H0 ~                        if(i!=0) System.out.print(" ");
                        System.out.print(array);
                }
               
2 ^6 s, u+ m' b                b.bubbleSort(array);
               
: o/ k/ X3 c+ m" i! q, V/ A8 x                System.out.println("\n排序后");
$ Y  l% n! W6 `: z5 S                for (int i = 0; i < array.length; i++) {
                        if(i!=0) System.out.print(" ");
) g4 M' ]' m9 Z  {3 z1 ?                        System.out.print(array);
                }
        }


运行结果：运行结果：
  d9 Z" E$ y/ t     排序前
$ x7 W+ n1 c* c     9 8 7 4 5 6 1 2 3
     排序后
     1 2 3 4 5 6 7 8 9
# O5 d/ Q. i% ?- @7 X& `3 h
这是冒泡排序的最简单的形式，下面我们来给他优化一下。
0 v3 P: K' U  Q2 f- e* q
优化冒泡排序1
$ S" e1 N/ {" m+ _; o! Z  I/ b
) N1 [7 |9 \7 E5 Y) e优化方案： 如果序列已经完全有序，可以提前终止排序
2 e  i/ Y0 L2 [- J  g: W
来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
                       
/ m. e4 A, [$ {* g                        boolean b = true;
                       
                        for (int begin = 1 ; begin<end ; begin++) {
                                if(array[begin]<array[begin-1]) {
4 [" C# E1 c/ B! o! n$ [                                       
% e- W9 N2 o) }) v4 j) M- U                                        int index = array[begin];
6 t3 A  ^: M' u: E  G4 m                                        array[begin]=array[begin-1];
% F8 V- I8 ?4 \- p+ ^                                        array[begin-1] = index;
7 {" H, O: {% z9 K$ E                                       
( O" c% O- h7 q$ N+ D; @                                        b = false;
                                }
, g$ I9 }" _& n+ o$ o                                if (b) break;
                        }
, N0 z8 D2 x: u% L, V; t& _                }
& N2 Y" {2 ?! ?3 S4 G: k& H2 c1 G                return array;
        }

优化代码和未优化的代码的区别就是，优化代码添加了一个boolean类型，用来判断如果在for循环一圈后，都没有触动if语句，说明这个数组已经不需要排序了。然后直接结束排序。

0 R5 Z, G1 A6 p, T3 l! H当然这个排序还是可以有另外一种优化方式
. ^9 F( u; M. ~0 L# N
优化冒泡排序2

优化方案： 如果序列已经局部有序，可以记录最后一次交换的位置，减少交换次数。
' p7 \) k4 C2 S+ V& y
来看代码：        public int[] bubbleSort(int[] array ){
                for (int end = array.length; end > 0; end--) {
* ~; r7 Y# M, w/ \( |9 z% r! c                        int j = 1;
0 |3 h* ^: b  T$ f$ g                        for (int begin = 1 ; begin<end ; begin++) {
5 p3 I- e; u  E5 e1 h) J                                if(array[begin]<array[begin-1]) {
                                        int index = array[begin];
4 z( I) h' E) z+ \                                        array[begin]=array[begin-1];
                                        array[begin-1] = index;
5 j/ ~7 a, J, {& s9 w                                       
  s1 q; i- r2 J: n                                        j = begin;
                                       
                                }
8 C% W7 U' I+ C' K, k- d                                end = j;
                        }
                }
                return array;
        }
8 \" M( P' H4 @; W. I
: X' b  ~2 W& u2 `  o优化代码和未优化的代码的区别就是，优化代码添加了一个int类型，用来判记录最后交换的位置，然后直接可以让索引指向这个位置，下一次在进行循环可以直接从这个位置作为应该索引，这个位置后面的元素就可以不去遍历。

冒泡排序属于稳定排序，为原地算法
  c1 X) c/ f* s- t4 x* Q, o4 @0 ]
( Z# g3 N4 u& W$ }' Y/ y注：本文博主学习自腾讯课堂的小码哥的“数据结构与算法”，所以如有和小码哥课程中类似方案，纯属必然！！！
0 b8 G! x& @5 E原文链接：https://blog.csdn.net/qq_41242174/article/details/105006872
" c: |! x: c- z

柠檬草lll

发表回复