在面试的时候我们经常会被问到排序,比如有插入排序,冒泡排序等等,我们今天就讲下冒泡排序以及优化。
一想到冒泡排序马上就会想起使用双循环来实现:
先定义一个数组 int[] array = {3,4,2,1,5,7,6};
然后定义方法
public static void sort1(int[] array){
int temp;
for(int i=0;i<array.length-1;i++){
for(int j=0;j<array.length-1-i;j++){
if(array[j]>array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
System.out.println(Arrays.toString(array));
}
}
这样就是我们最常见的冒泡排序,但是通过每次排完需,我们会发现有点问题,比如上面这个方法的执行过程:
[3, 2, 1, 4, 5, 6, 7]
[2, 1, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
我们会发现从第4次开始,后面每次打印的都是一样的结果,这显然效率不高,既然这样,那肯定可以优化的。
我们先观察下排序后的结果,第一次排序后的结果是:
[3, 2, 1, 4, 5, 6, 7]
在排序的过程中,第j 都会和第j+1位做比较,这其实是可以不用这样的,
我们可以加个标记,也就是在第一个for循环中加个标记,标记当前是否是有序数组,若是,则跳出循环;
我们在定义一个方法,对刚才的排序进行优化:
public static void Optimize1(int array[]){
int temp=0;
for(int i=0;i<array.length;i++){
//有序标记,每一轮的初始是true
boolean isSorted = true;
for(int j=0;j<array.length-i-1;j++){
if(array[j] > array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
//有元素交换,所以不是有序,标记为false
isSorted = false;
}
}
if(isSorted){
break;
}
System.out.println(Arrays.toString(array));
}
}
排序的执行过程如下:
[3, 2, 1, 4, 5, 6, 7]
[2, 1, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
只执行了三次就排好了,这比第一种方法效率要高;
但是这还不是最高效的,我们再观察下,发现第一次排完序后
[3, 2, 1, 4, 5, 6, 7]
4,5,6,7 已经是一个有序数列了,那可不可以这样,每次排完序后,标记最后一次排序的位置,下次再对比的时候,只要对比到上次
最后的一个位置即可,因为上次排完序后的最后一个位置开始,到数组完,一定是一个有序数列。
所以冒泡排序最优版如下:
public static void sort(int array[]){
int temp =0;
//记录每次最后一次交换的位置
int lastExchangeIndex =0;
//无序数列边界,每次比较只需比到这里为止
int sortBorder = array.length-1;
for(int i=0;i<array.length;i++){
//有序标记,每一轮的初始是true
boolean isSorted = true;
for(int j=0;j<sortBorder;j++){
if(array[j]>array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
//有元素交换,所以不是有序,标记为false
isSorted = false;
//把无序数列的边界更新为最后一次元素交换的位置
lastExchangeIndex = j;
}
}
//更新无序数列边界
sortBorder = lastExchangeIndex;
if(isSorted){
break;
}
System.out.println(Arrays.toString(array));
}
}
分享到:
相关推荐
冒泡排序的优化算法,提高了效率int main(){ int a, m; cin>>m; int *p; p = new int[m]; for(int i=0;i;i++) cin>>p[i]; int temp; for(int i=0;i;i++){ a = true; for(int j=m-2;j>=i;j--) if(p[j+1][j...
python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的...
对冒泡排序法进行优化,比较的次数减少,效率提高
用java 编写的冒泡排序算法,并涵盖了冒泡排序算法的几种优化方式,以及在冒泡排序上的二分查找法。
对于教学非常的方便使用,在原来普通算法的基础上做一个优化,可以节省很多的时间
本文和大家分享一个基于C语言优化冒泡排序的核心代码。
js代码-冒泡排序优化
冒泡排序和选择排序均用两种方法实现,原始方法和在原始方法上的改进和优化,对应博客地址:http://blog.csdn.net/ns_code/article/details/20065107
上传了一个最近学到的冒泡排序法的优化写法,大家可自行查阅学习
php优化版本的冒泡排序算法
S7-200SMART冒泡排序-优化版(可选择升序降序及数据类型等)
冒泡排序-排序过程 设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"漂浮",如此反复进行,...
python冒泡排序程序,优化代码。。,python冒泡排序程序python冒泡排序程序python冒泡排序程序python冒泡排序程序python冒泡排序程序
此资源是本人演示冒泡排序及其优化方案的示例代码,欢迎大家下载。关于冒泡排序的介绍,也可以参考本人博文https://blog.csdn.net/Abel_Liujinquan/article/details/88880483
//冒泡排序 for(int i=0;i;i++){ for(int j=i+1;j;j++){//注意j的开始值是i+1,因为按照排序规则,比a[i]大的值都应该在它后面 if(a[i] > a[j]){ int temp = a[j]; a[j] = a[i]; a[i] = temp; ...
自己刚刚开始学习排序算法,第一个排序算法:冒泡排序。以及在学习过程中做的一些笔记。
C#语言编写的双向冒泡排序,优化了简单的冒泡排序,减少了循环次数,排序效率更高
python冒泡排序 冒泡排序的时间复杂度为O(n^2),其中n是列表的长度。这是因为对于每个元素,我们可能需要与其后面的所有元素进行比较和交换。尽管冒泡排序在某些情况下可能不是最优的...下面是优化后的冒泡排序代码: