冒泡排序算法
2019-04-20 本文已影响0人
攻城狮l
一、冒泡排序
冒泡排序的英文Bubble Sort，是一种最基础的交换排序。
大家一定都喝过汽水，汽水中常常有许多小小的气泡，哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻，所以小气泡可以一点一点向上浮动。
二、实现思路
使用双重循环，循环比较相邻的两个数字，把较小的数字移动到右边，步骤如下：
- 第一次循环，相邻的两个数比较，小的数下沉到右边，循环比较length次，则会出现最小的数字在最后一位
- 第二次循环，相邻的两个数比较，小的数据下沉到右边，循环比较 length-1 次（因为第一次最小的数已在最右边，不要再比较最后一位），则会出现第二小的数字在倒数第二位
- 第n次循环，相邻的两个数比较，小的数据下沉到右边，循环比较 length-n 次，则会出现第二小的数字在倒数第n-1位
实现思路不清楚的可点此链接，有相关的图文介绍
三、代码实现
package xzg.algorithm;
/**
* 冒泡排序算法
*/
public class BubbleSort {
public static void main(String[] args) {
int score[] = {3, 8, 1, 13, 24, 14, 41, 26, 5, 2};
int[] bubbleSort = bubbleSort(score);
System.out.print("冒泡排序结果：");
for (int a = 0; a < score.length; a++) {
System.out.print(score[a] + "\t");
}
}
/**
* 双重循环实现冒泡排序<p/>
* 实现思路：<p/>
* 1.第一次循环，相邻的两个数比较，小的数下沉到右边，循环比较length次，则会出现最小的数字在最后一位<p/>
* 2.第二次循环，相邻的两个数比较，小的数据下沉到右边，循环比较 length-1 次（因为第一次最小的数已在最右边，不要再比较最后一位），则会出现第二小的数字在倒数第二位<p/>
* 3.第n次循环，相邻的两个数比较，小的数据下沉到右边，循环比较 length-n 次，则会出现第二小的数字在倒数第n-1位<p/>
*
* @param arr 待排序数组
* @return 排序完成的数组
*/
public static int[] bubbleSort(int arr[]) {
int length = arr.length;
for (int i = 0; i < length - 1; i++) {
//第i+1趟循环排序
for (int j = 0; j < length - 1 - i; j++) {//循环比较 length - 1 - i次（因为后i项数据已排序完毕）
if (arr[j] < arr[j + 1]) {//右边数据比左边的大，则交换位置
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.print("第" + (i + 1) + "次排序结果：");
for (int a = 0; a < arr.length; a++) {
System.out.print(arr[a] + "\t");
}
System.out.println();
}
return arr;
}
}
bubbleSort方法输出结果如下：
第1次排序结果：8 3 13 24 14 41 26 5 2 1
第2次排序结果：8 13 24 14 41 26 5 3 2 1
第3次排序结果：13 24 14 41 26 8 5 3 2 1
第4次排序结果：24 14 41 26 13 8 5 3 2 1
第5次排序结果：24 41 26 14 13 8 5 3 2 1
第6次排序结果：41 26 24 14 13 8 5 3 2 1
第7次排序结果：41 26 24 14 13 8 5 3 2 1
第8次排序结果：41 26 24 14 13 8 5 3 2 1
第9次排序结果：41 26 24 14 13 8 5 3 2 1
冒泡排序结果：41 26 24 14 13 8 5 3 2 1
Process finished with exit code 0
可以看到其实到第6次排序后，已经排序成功了，相关算法是否可以优化呢？
答案是肯定的，我们可以增加一个标示位，用于标示第n次排列时，是否有进行位置交换，如果没有进行交换(说明已排序完毕)，则终止排序即可。
优化后的代码如下：
public static int[] bubbleSortOptimize(int arr[]) {
int length = arr.length;
for (int i = 0; i < length - 1; i++) {
boolean isMove = false;//用于表示第i+1趟排序中是否有移动交换数据，如果没有则说明已排序完成，无需再次循环比较
//第i+1趟循环排序
for (int j = 0; j < length - 1 - i; j++) {//循环比较 length - 1 - i次（因为后i项数据已排序完毕）
if (arr[j] < arr[j + 1]) {//右边数据比左边的大，则交换位置
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
//有移动交换数据，修改标示
isMove = true;
}
}
if (!isMove){//如果没有移动交换数据则说明已排序完成，无需再次循环比较
System.out.println("冒泡排序完成，无需再次比较数据");
break;
}
System.out.print("第" + (i + 1) + "次排序结果：");
for (int a = 0; a < arr.length; a++) {
System.out.print(arr[a] + "\t");
}
System.out.println();
}
return arr;
}
以下是优化后的排序输出结果。
bubbleSortOptimize方法输出结果如下：
第1次排序结果：8 3 13 24 14 41 26 5 2 1
第2次排序结果：8 13 24 14 41 26 5 3 2 1
第3次排序结果：13 24 14 41 26 8 5 3 2 1
第4次排序结果：24 14 41 26 13 8 5 3 2 1
第5次排序结果：24 41 26 14 13 8 5 3 2 1
第6次排序结果：41 26 24 14 13 8 5 3 2 1
冒泡排序完成，无需再次比较数据
冒泡排序结果：41 26 24 14 13 8 5 3 2 1
Process finished with exit code 0
四、算法分析
冒泡排序总的平均时间复杂度为O(n^2)
