Java 排序算法-冒泡排序及其优化

什么是冒泡排序

这里引用一下百度百科上的定义:

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

冒泡排序在实际工作中用的并不多,多是面试题中会遇到。

下面用java代码来实现:

基本写法

为了看到后面优化后的效果,我加了count 和 num l两个变量来分布统计外循环和内循环的次数

/**
* 原始的冒泡排序
* @param values
*/
public static void bubbleSort(int[] values) {
System.out.println("排序前:" + Arrays.toString(values));
int tmp;// 循环外创建变量,减少垃圾产生,提高性能
int count = 0;// 比较了多少趟
int num = 0; // 比较次数
// 外层循环,n 个元素,最多需要 n -1 趟循环
for(int i = 0; i < values.length -1 ; i++) {
count ++;
// 内层循环, 每一次都从开始两个元素开始两两比较到最后
for (int j = 0; j < values.length - 1; j++) {
if(values[j] > values[j + 1]) {
tmp = values[j];
values[j] = values[j + 1];
values[j + 1] = tmp;
}
num ++;
}
}
System.out.println("排序后:" + Arrays.toString(values));
System.out.println("比较趟数:"+count + ",比较次数:" + num);
}

优化后写法

/**
* 优化了比较次数的冒泡排序
* @param values
*/
public static void bubbleSort2(int[] values) {
System.out.println("排序前:" + Arrays.toString(values));
int tmp; // 循环外创建变量,减少垃圾产生,提高性能
int count = 0;// 比较了多少趟
int num = 0; // 比较次数
// 外层循环,n 个元素,最多需要 n -1 趟循环
for(int i = 0; i < values.length -1 ; i++) {
count ++;
// 内层循环, 每一次都从开始两个元素开始两两比较到最后
/* 每一趟循环都可以找你最大的数,内循环可以比上一趟循环减少一次比较 */
for (int j = 0; j < values.length - 1 - i; j++) {
if(values[j] > values[j + 1]) {
tmp = values[j];
values[j] = values[j + 1];
values[j + 1] = tmp;
}
num ++;
}
}
System.out.println("排序后:" + Arrays.toString(values));
System.out.println("比较趟数:"+count + ",比较次数:" + num);
}

显然,每一趟循环都可以找你最大的数,内循环可以比上一趟循环减少一次,面试时写成这样基本OK了。

终极版本

实际中,用来比较的数据,可能就只有几个位置是无序的,如果也按照上面的写法进行 length -1 次循环就显得有点死板了。

因此我们可以假设数组已经排好序了,给程序一个标记变量,如果标记变量显示数组已排好序,则可以跳出循环。

/**
* 冒泡排序终极写法
* @param values
*/
public static void bubbleSort3(int[] values) {
System.out.println("排序前:" + Arrays.toString(values));
int tmp;// 循环外创建变量,减少垃圾产生,提高性能
int count = 0;// 比较了多少趟
int num = 0; // 比较次数
// 外层循环,n 个元素,最多需要 n -1 趟循环
for(int i = 0; i < values.length -1 ; i++) {
// 定义一个boolean 值,标记数组是否达到有序状态
boolean flag = true;
count ++;
// 内层循环, 每一次都从开始两个元素开始两两比较到最后
/* 每一趟循环都可以找你最大的数,内循环可以比上一趟循环减少一次比较 */
for (int j = 0; j < values.length - 1 - i; j++) {
if(values[j] > values[j + 1]) {
tmp = values[j];
values[j] = values[j + 1];
values[j + 1] = tmp;
// 如果本趟发生了交换,表明数组还是无序,需要进入下一轮循环
flag = false;
}
num ++;
}
// 根据标记的布尔值判断数组是否达到有序状态,如有序,则退出循环
if( flag) {
break;
}
}
System.out.println("排序后:" + Arrays.toString(values));
System.out.println("比较趟数:"+count + ",比较次数:" + num);
}

源码及测试

package com.xzlf.sort;

import java.util.Arrays;

public class TestSort {
public static void main(String[] args) {
int[] arr = {1,341,33,22,88,99,100};
int[] arr2 = {1,341,33,22,88,99,100};
int[] arr3 = {1,341,33,22,88,99,100};
bubbleSort(arr);
System.out.println("==================");
bubbleSort2(arr2);
System.out.println("==================");
bubbleSort3(arr3); }
/**
* 原始的冒泡排序
* @param values
*/
public static void bubbleSort(int[] values) {
System.out.println("排序前:" + Arrays.toString(values));
int tmp;// 循环外创建变量,减少垃圾产生,提高性能
int count = 0;// 比较了多少趟
int num = 0; // 比较次数
// 外层循环,n 个元素,最多需要 n -1 趟循环
for(int i = 0; i < values.length -1 ; i++) {
count ++;
// 内层循环, 每一次都从开始两个元素开始两两比较到最后
for (int j = 0; j < values.length - 1; j++) {
if(values[j] > values[j + 1]) {
tmp = values[j];
values[j] = values[j + 1];
values[j + 1] = tmp;
}
num ++;
}
}
System.out.println("排序后:" + Arrays.toString(values));
System.out.println("比较趟数:"+count + ",比较次数:" + num);
} /**
* 优化了比较次数的冒泡排序
* @param values
*/
public static void bubbleSort2(int[] values) {
System.out.println("排序前:" + Arrays.toString(values));
int tmp; // 循环外创建变量,减少垃圾产生,提高性能
int count = 0;// 比较了多少趟
int num = 0; // 比较次数
// 外层循环,n 个元素,最多需要 n -1 趟循环
for(int i = 0; i < values.length -1 ; i++) {
count ++;
// 内层循环, 每一次都从开始两个元素开始两两比较到最后
/* 每一趟循环都可以找你最大的数,内循环可以比上一趟循环减少一次比较 */
for (int j = 0; j < values.length - 1 - i; j++) {
if(values[j] > values[j + 1]) {
tmp = values[j];
values[j] = values[j + 1];
values[j + 1] = tmp;
}
num ++;
}
}
System.out.println("排序后:" + Arrays.toString(values));
System.out.println("比较趟数:"+count + ",比较次数:" + num);
}
/**
* 冒泡排序终极写法
* @param values
*/
public static void bubbleSort3(int[] values) {
System.out.println("排序前:" + Arrays.toString(values));
int tmp;// 循环外创建变量,减少垃圾产生,提高性能
int count = 0;// 比较了多少趟
int num = 0; // 比较次数
// 外层循环,n 个元素,最多需要 n -1 趟循环
for(int i = 0; i < values.length -1 ; i++) {
// 定义一个boolean 值,标记数组是否达到有序状态
boolean flag = true;
count ++;
// 内层循环, 每一次都从开始两个元素开始两两比较到最后
/* 每一趟循环都可以找你最大的数,内循环可以比上一趟循环减少一次比较 */
for (int j = 0; j < values.length - 1 - i; j++) {
if(values[j] > values[j + 1]) {
tmp = values[j];
values[j] = values[j + 1];
values[j + 1] = tmp;
// 如果本趟发生了交换,表明数组还是无序,需要进入下一轮循环
flag = false;
}
num ++;
}
// 根据标记的布尔值判断数组是否达到有序状态,如有序,则退出循环
if( flag) {
break;
}
}
System.out.println("排序后:" + Arrays.toString(values));
System.out.println("比较趟数:"+count + ",比较次数:" + num);
}
} 上面代码运行结果:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200315005725387.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3MDMz,size_16,color_FFFFFF,t_70) @[TOC](Java/java基础)
上一篇:java排序算法之冒泡排序(Bubble Sort)


下一篇:免费SMTP邮件服务:Mandrill,Sendgrid,Mailjet,Postmarkapp,MailChimp