冒泡算法：
（对一些部分有序的数组，效率高）
时间复杂度：n^2;
一般入门时是这样写的：
int [] datas= new int[]{6,5,4,3,2,1};
for (int i=0;i<datas.length;i++){
for (int j=0;j<datas.length-1;j++){
if (datas[j]>datas[j+1]){
int minV=datas[j];
datas[j]=datas[j+1];
datas[j+1]=minV;
}
}
}
for (int data : datas) {
System.out.print(data+" ");
}
得道结果是12346；没问题；
但是加上打印每一步骤的结果值，发现还有些执行相同的
多次，导致浪费计算次数。于是想到了优化；
image.png
冒泡算法的优化：
优化1
1.首先是第二个for循环的总次数：
由打印的日志分析知道，每执行一次内层的循环一次，就可以将大的值给冒泡交换到最后面了。最大数，第一遍就给放到最后面了，因此可以不用再交换后面排好序的位置了。
由打印结果规律，归纳推导，发现外层遍历的下标刚好是内层循环排好序的个数。于是内层的遍历可以在后面便利的总数减去外层遍历下标。
2.内层循环遍历时，有一个最小比对值，需要频繁的申明，使用，再释放。因此可以放到最外面，两个循环的初始下标计量也可以放入外边统一声明。
于是得到如下：
int [] datas= new int[]{6,5,4,3,2,1};
int change,m=0,n;
for (;m<datas.length;m++){
n=0;
for (;n<datas.length-1;n++){
if (datas[n]>datas[n+1]){
change=datas[n];
datas[n]=datas[n+1];
datas[n+1]=change;
}
System.out.format("第 %d 遍的第%d 次交换：", m+1,n+1);
for(int count:datas) {
System.out.print(count+" ");
}
System.out.println();
}
System.out.format("第 %d 遍最终结果：", m+1);
for (int data : datas) {
System.out.print(data+" ");
}
System.out.println();
}
结果是：
image.png
发现最后的结果明显内循环每次都减少了次数。
优化2
但是如果数据是321456呐？
结果还是会走那么多次数，而且再有些步骤中就已经排好序了，可是外层循环还要继续排序。
image.png
于是，为了这个想去优化问题，我们可以设置一个标志位，用来表示当前第m趟是否有交换，如果有则要进行m+1 趟，如果没有，则说明当前数组已经完成排序。实现代码如下
int [] datas= new int[]{3,2,1,4,5,6};
int change,m=0,n;
boolean flag;
for (;m<datas.length;m++){
n=0;
flag=true;
for (;n<datas.length-1-m;n++){
if (datas[n]>datas[n+1]){
change=datas[n];
datas[n]=datas[n+1];
datas[n+1]=change;
//如果还有没排好序的，将标志位设置为false;
flag=false;
}
System.out.format("第 %d 遍的第%d 次交换：", m+1,n+1);
for(int count:datas) {
System.out.print(count+" ");
}
System.out.println();
}
System.out.format("第 %d 遍最终结果：", m+1);
for (int data : datas) {
System.out.print(data+" ");
}
System.out.println();
//如果没有要交换位置的，就证明排好序了，直接退出整个循环
if (flag){
return;
}
}
打印结果：
image.png
发现好多了，少外层的两次循环。
优化3
但是还有一个问题，就是上图中，明明第二次遍历，第一次的交换就已经完成了，但是后面还要继续交换，造成了一定的时间浪费。
对于这种问题，我们可以想到一个解决方案，利用一个标志位，记录一下当前第m趟所交换的最后一个位置的下标，在进行第m+1 趟的时候，只需要内循环到这个下标的位置就可以了，因为后面位置上的元素在上一趟中没有换位，这一次也不可能会换位置了。基于这个规律，我们可以进一步优化我们的代码：
int [] datas= new int[]{3,2,1,4,5,6};
int change,m=0,n,changelen=datas.length-1,tempIndex=0;
boolean flag;
for (;m<datas.length;m++){
n=0;
flag=true;
for (;n<changelen;n++){
if (datas[n]>datas[n+1]){
change=datas[n];
datas[n]=datas[n+1];
datas[n+1]=change;
//如果还有没排好序的，将标志位设置为false;
flag=false;
tempIndex=n;
}
System.out.format("第 %d 遍的第%d 次交换：", m+1,n+1);
for(int count:datas) {
System.out.print(count+" ");
}
System.out.println();
}
changelen=tempIndex;
System.out.format("第 %d 遍最终结果：", m+1);
for (int data : datas) {
System.out.print(data+" ");
}
System.out.println();
//如果没有要交换位置的，就证明排好序了，直接退出整个循环
if (flag){
return;
}
}
打印结果：
优化三
从打印输出来看，明显减少了很多不必要的计算。比原来的更加优良，减少了时间复杂度。
选择排序：
（适用于无序不重复的数列）
时间复杂度：n^2;
原理：
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
代码：
public void selectSort(){
int change,m=0,n;
int [] datas= new int[]{8,1,48,92,12,77,66,6};
for (;m<datas.length;m++){
change=datas[m];
for (n=m+1;n<datas.length;n++){
if (datas[n]<change){
change=datas[n];
datas[n]=datas[m];
datas[m]=change;
}
}
}
for (int data : datas) {
System.out.print(data+" ");
}
}
打印结果：
1 6 8 12 48 66 77 92 ；
网友评论