数据结构java版之冒泡排序及优化

xiaoqibTn 发布于2019-08-16 15:09 / 3071人阅读

摘要：外层循环让内层循环继续排没有排序过的数组，排序过的不用再排。那么优化后的算法能快多少呢。我们都以数组长度为来计算传统冒泡排序步，优化后的冒泡排序步。因为优化后的冒泡排序，每排完一次，最后一个数已经是最大的，就不需要再比较了。

冒泡排序的时间用大O表示法是O(N^2).

传统的冒泡排序：

/**
* @param total 要排序的数组长度
*/
public void sort(int total){
int num[];
if(total <= 0){
System.out.println("请输入大于0的正整数");
}else{
num = new int[total];
for (int i = 0 ; i < total; i++){
//生成随机1到100之间的数
Random ra =new Random();
num[i] = ra.nextInt(100)+1;
}
System.out.println("要排序的数组为：" + Arrays.toString(num));
int sum = 0;
int out,in;
for (out = total - 1; out > 1; out--){
for (in = 0 ; in < out; in++){
sum ++;
if(num[in] > num[in+1]){
int temp = num[in];
num[in] = num[in+1];
num[in+1] = temp;
}
}
}
// 最原始的冒泡排序
for(int i = 0; i < total -1 ; i ++){
for (int j = 0 ; j < total -1 ; j++){
sum ++;
if(num[j] > num[j+1]){
int temp = num[j];
num[j] = num[j+1];
num[j+1] = temp;
}
}
}
System.out.println("排序完成的数组为：" + Arrays.toString(num));
System.out.println("总共用次数：" + sum);
}
}

优化过后的冒泡排序：

/**
* @param total 要排序的数组长度
*/
public void sort(int total){
int num[];
if(total <= 0){
System.out.println("请输入大于0的正整数");
}else{
num = new int[total];
for (int i = 0 ; i < total; i++){
//生成随机1到100之间的数
Random ra =new Random();
num[i] = ra.nextInt(100)+1;
}
System.out.println("要排序的数组为：" + Arrays.toString(num));
/**核心算法：
* 双重循环，外层循环用于控制排多少次序。
* 内层循环从第一位开始一直往后比较，内层循环一次后，可以将最大的数至于末尾。
* 外层循环让内层循环继续排没有排序过的数组，排序过的不用再排。
*/
int sum = 0;
int out,in;
for (out = total - 1; out > 1; out--){
for (in = 0 ; in < out; in++){
sum ++;
if(num[in] > num[in+1]){
int temp = num[in];
num[in] = num[in+1];
num[in+1] = temp;
}
}
}

System.out.println("排序完成的数组为：" + Arrays.toString(num));
System.out.println("总共用次数：" + sum);
}
}

大家对比可以发现，就是外层循环的时候有点变化，其他的代码都是一模一样的。

那么优化后的算法能快多少呢。我们都以数组长度为10来计算：

传统冒泡排序：9x9=81步，

优化后的冒泡排序：9+8+7+6+5+4+3+2=44步。

因为优化后的冒泡排序，每排完一次，最后一个数已经是最大的，就不需要再比较了。

服务器托管私有云 java冒泡排序代码 java二维数组冒泡排序优化插入排序java 冒泡排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73305.html

数据结构java版之大O表示法

摘要：二分查找法要查找的数数组长度设定的数组花了多少次找到最小值最大值当前猜的值打印猜的每个数找到了花了次如果猜的数大于选定的数，则把设为猜的数，否则把设为猜的数请输入大于等于的正整数且查找的数不能大于数组里最大的数调用方法执行结果找到了花了次大O表示法使用大写字母O，可以认为其含义为order of（大约是）。我们可以使用大O法来描述线性查找使用了O(N)级时间，二分查找使用了O(log...

wudengzan 2019-08-16 15:09 评论0 收藏0
数据结构与算法——冒泡排序

摘要：多练练排序算法，不仅能够让我们知道一些排序方法的底层实现细节，更能够锻炼我们的思维，提升编程能力。排序算法的稳定性一个稳定的排序，指的是在排序之后，相同元素的前后顺序不会被改变，反之就称为不稳定。 1. 导言因为这是排序算法系列的第一篇文章，所以多啰嗦几句。排序是很常见的算法之一，现在很多编程语言都集成了一些排序算法，比如Java 的Arrays.sort()方法，这种方式让我们可...

Yang_River 2019-08-16 15:51 评论0 收藏0
冒泡排序及优化详解

摘要：算法思想冒泡排序属于一种典型的交换排序。冒泡排序常规版代码实现下面详细分析一下常规版的冒泡排序，整个算法流程其实就是上面实例所分析的过程。算法思想　　冒泡排序属于一种典型的交换排序。　　交换排序顾名思义就是通过元素的两两比较，判断是否符合要求，如过不符合就交换位置来达到排序的目的。冒泡排序名字的由来就是因为在交换过程中，类似水冒泡，小（大）的元素经过不断的交换由水底慢慢的浮到水的...

evin2016 2019-08-19 10:16 评论0 收藏0
Java排序-冒泡排序、插入排序和选择排序

摘要：插入排序特殊从第二个元素开始，和第一个元素比较，如果满足排序的顺序，则交换顺序。优化后选择排序从第一个位置开始遍历待排序的元素，找到最小值和第一元素交换从位置开始往后遍历，找到之后元素中的最小值，和第个元素交换位置。插入排序1、特殊：从第二个元素开始，和第一个元素比较，如果满足排序的顺序，则交换顺序。2、一般：把待比较和他之前的所有元素相比（从右往左），如果满足排序的顺序，这交换。 ...

gityuan 2019-08-19 10:42 评论0 收藏0