冒泡排序优化
拿去不谢,原理什么的我就不多解释,自己研究出来才是王道,才真正有成就感,这些代码才能成为你的竞争力
package match;
import java.util.Arrays;
/**
* @ClassName BestBubbleSort
* @Descriptiom TODO 冒泡排序最优算法
* @Author KING
* @Date 2019/1/11 9:53
* @Version 1.2.1
*
* 每次交换都进行标记,当标记不改变时则交换没有发生,此时数组即是有序,即可结束程序避免无
* 效运行
* 一次排序可以确定两个值,正向扫描找到最大值交换到最后,反向扫描找到最小值交换到最前面。 每次排序执行正反两次扫描
*
**/
public class BestBubbleSort {
public static void main(String[] args) {
int a[] = {16,20,65,77,45,23,96,1,3,0,57};
BestBubbleSort(a);
Arrays.stream(a).forEach(x -> System.out.print(x+ " "));//java8支持的流处理,用7的需要自行修改,
}
/**
* 冒泡排序最优算法
* @param arr 要排序的数组
*/
static void BestBubbleSort(int arr[])
{
int i = 0;
int j = 0;
int n = 0;//同时找最大值的最小需要两个下标遍历
int flag = 0;
int pos = 0;//用来记录最后一次交换的位置
int k = arr.length - 1;
for (i = 0; i < k; i++)//确定排序次数
{
pos = 0;
flag = 0;
//正向寻找最大值
for (j = n; j < k; j++)//确定比较次数
{
if (arr[j]>arr[j + 1])
{
//交换
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = 1;//加入标记
pos = j;//交换元素,记录最后一次交换的位置
}
}
if (flag == 0)//如果没有交换过元素,则已经有序,直接结束
{
return;
}
k = pos;//下一次比较到记录位置即可
//反向寻找最小值
for (j = k; j > n; j--) {
if (arr[j] < arr[j - 1]){
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
flag = 1;
}
}
n++;
if (flag == 0)//如果没有交换过元素,则已经有序,直接结束
{
return;
}
}
}
}
运行结果