以下介绍来自百度百科：
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
冒泡排序算法的原理如下：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
时间复杂度
冒泡排序总的平均时间复杂度为 
。
冒泡排序最好的时间复杂度为
。
算法稳定性
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
以下是Java实现：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226package com.jandmin.demo.leetcode.sort; import java.util.Random; /** * @description: 冒泡排序 * @author: JandMin **/ public class BubbleSort { private static int countInner = 0; private static int countOut = 0; private static int countInner1 = 0; private static int countOut1 = 0; private static int countInner2 = 0; private static int countOut2 = 0; private static int countInner3 = 0; private static int countOut3 = 0; private static int countInner4 = 0; private static int countOut4 = 0; /** * 初始化数组 * @param len 数组长度 * @return */ private static int[] initArray(int len){ if(len <= 0){ return new int[0]; } int[] array = new int[len]; Random random = new Random(); int ordinal = 0; if (len > 100){ // 为了让后面100个位顺序的数字 ordinal = len; len = len -100; } for(int i=0; i<len; i++){ array[i] = random.nextInt(len); } for(int i=len; i<ordinal; i++){ // 最后 100 个是顺序的 array[i] = i + 1; } // System.out.println("原数组： "+ JSONObject.toJSONString(array)); return array; } public static void main(String[] args) { int len = 10000; int[] array = initArray(len); // 方案0 int[] array0 = array.clone(); long start = System.currentTimeMillis(); bubbleSort(array0); System.out.println(" 0耗时："+(System.currentTimeMillis()-start)+" ms,countInner:"+countInner+",countOut:"+countOut); // System.out.println("方案零： "+ JSONObject.toJSONString(array0)); // 方案一 int[] array1 = array.clone(); start = System.currentTimeMillis(); bubbleSort1(array1); System.out.println(" 1耗时："+(System.currentTimeMillis()-start)+" ms,countInner:"+countInner1+",countOut:"+countOut1); // System.out.println("方案一： "+ JSONObject.toJSONString(array1)); // 方案2 int[] array2 = array.clone(); start = System.currentTimeMillis(); bubbleSort2(array2); System.out.println(" 2耗时："+(System.currentTimeMillis()-start)+" ms,countInner:"+countInner2+",countOut:"+countOut2); // System.out.println("方案二： "+ JSONObject.toJSONString(array2)); // 方案3 int[] array3 = array.clone(); start = System.currentTimeMillis(); bubbleSort3(array3); System.out.println(" 3耗时："+(System.currentTimeMillis()-start)+" ms,countInner:"+countInner3+",countOut:"+countOut3); // System.out.println("方案三： "+ JSONObject.toJSONString(array3)); // 方案4 int[] array4 = array.clone(); start = System.currentTimeMillis(); bubbleSort4(array4); System.out.println(" 4耗时："+(System.currentTimeMillis()-start)+" ms,countInner:"+countInner4+",countOut:"+countOut4); // System.out.println("方案四： "+ JSONObject.toJSONString(array4)); } /** * @Description: 冒泡排序方案：每一个元素和后面每一个元素比较，大就换到后面去 * @param array 数组 * @return: void */ private static void bubbleSort(int[] array) { int len = array.length; for(int i=0; i<len-1; i++){ // 遍历每一个元素 for(int j=i+1; j<len; j++){ // 每一个元素跟后面的每一个数进行对比 // 大就往后移 if(array[i] > array[j]){ exchange(array,i,j); } countInner++; } countOut++; } } /** * @Description: 冒泡排序方案一:每两个相邻的元素一一比较，大的往后移 * @param array 数组 * @return: void */ private static void bubbleSort1(int[] array) { int len = array.length; for(int i=0; i<len-1; i++){ // 遍历每一个元素 for(int j=0; j<len-i-1; j++){ // 后面的每两个元素进行比较，大的往后移 // 大的往后移 if(array[j] > array[j+1]){ exchange(array,j,j+1); } countInner1++; } countOut1++; } } /** * @Description: 冒泡排序方案二：每两个相邻的元素一一比较，大的往后移，当没有出现移动时，说明已经是顺序，结束循环 * @param array 数组 * @return: void */ private static void bubbleSort2(int[] array) { int len = array.length; boolean hasChange; for(int i=0; i<len-1; i++){ // 遍历每一个元素 hasChange = false; for(int j=0; j<len-i-1; j++){ // 后面的数两两进行对比，后面顺序的数据不需要再比较 // 大的往后移 if(array[j] > array[j+1]){ exchange(array,j,j+1); hasChange = true; } countInner2++; } if(!hasChange){ // 如果没有交换，说明是顺序，结束遍历 break; } countOut2++; } } /** * @Description: 冒泡排序方案三：每两个相邻的元素一一比较，大的往后移，当后面一部分是顺序时，每次都不在跟后面的比较，只比较前半部分 * @param array 数组 * @return: void */ private static void bubbleSort3(int[] array) { int len = array.length; boolean hasChange; int maxIndexStart = len - 1; // 初始最值的位置 int maxIndex; // 移动过程中记录最大值的位置 for(int i=0; i<len-1; i++){ // 遍历每一个元素 hasChange = false; maxIndex = i; for(int j=0; j<maxIndexStart; j++){ // 后面的数两两进行对比，后面移好的数据不需要再比较 // 大的往后移 if(array[j] > array[j+1]){ exchange(array,j,j+1); hasChange = true; maxIndex = j; } countInner3++; } if(!hasChange){ // 如果没有交换，说明是顺序，结束遍历 break; } maxIndexStart = maxIndex; countOut3++; } } /** * @Description: 冒泡排序方案四：每两个相邻的元素一一比较，前后同时循环，大的往后移，小的往前移，当前一部分(和后一部分)已经是顺序时，每次都不在跟前面（后面)的比较，只比较中间部分 * @param array 数组 * @return: void */ private static void bubbleSort4(int[] array) { int len = array.length; boolean hasChange; int maxIndexStart = len - 1; // 初始最值的位置 int maxIndex; // 移动过程中记录最大值的位置 for(int i=0; i<len-1; i++){ // 遍历每一个元素 hasChange = false; maxIndex = i; // 正向比较 for(int j=0; j<maxIndexStart; j++){ // 后面的数两两进行对比，后面移好的数据不需要再比较 // 大的往后移 if(array[j] > array[j+1]){ exchange(array,j,j+1); maxIndex = j; hasChange = true; } countInner4++; } if(!hasChange){ // 如果没有交换，说明是顺序，结束遍历 break; } maxIndexStart = maxIndex; for(int j=maxIndexStart; j>0; j--){ if(array[j] < array[j-1]){ exchange(array,j-1,j); hasChange = true; } } if(!hasChange){ // 如果没有交换，说明是顺序，结束遍历 break; } countOut4++; } } /** * @Description: 数组两个位置上的数互换 * @param array 数组 * @param i 小的值下标 * @param j 大的值小标 * @return: void */ private static void exchange(int[] array, int i, int j) { if(i == j){ return; } int temp = array[i]; array[i] = array[j]; array[j] = temp; } }
执行结果：
0耗时：222 ms,countInner:49995000,countOut:9999
1耗时：218 ms,countInner:49995000,countOut:9999
2耗时：193 ms,countInner:49983675,countOut:9848
3耗时：353 ms,countInner:48972670,countOut:9848
4耗时：164 ms,countInner:20549226,countOut:2501
len = 10时，执行结果如下：
原数组： [6,5,6,2,1,2,0,7,8,9]
0耗时：0 ms,countInner:45,countOut:9
方案零： [0,1,2,2,5,6,6,7,8,9]
1耗时：0 ms,countInner:45,countOut:9
方案一： [0,1,2,2,5,6,6,7,8,9]
2耗时：0 ms,countInner:42,countOut:6
方案二： [0,1,2,2,5,6,6,7,8,9]
3耗时：0 ms,countInner:24,countOut:6
方案三： [0,1,2,2,5,6,6,7,8,9]
4耗时：0 ms,countInner:21,countOut:3
方案四： [0,1,2,2,5,6,6,7,8,9]
最后
以上就是无聊蚂蚁最近收集整理的关于【排序】冒泡排序及优化的全部内容，更多相关【排序】冒泡排序及优化内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复