2019-05-17：什么是冒泡排序？如何优化？
Moosphan opened this issue · 13 comments
你猜？😏
.
.
.
.
.
.
通过一个标识符，判断内层循环，循环结束时没有进行数据交换操作，表示已经有序，结束循环
你猜？😏
.
.
.
.
.
.通过一个标识符，判断内层循环，循环结束时没有进行数据交换操作，表示已经有序，结束循环
你猜我猜不猜
冒泡排序算法原理：（从小到大排序）
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，交换一趟后，最后的元素会是最大的数
3.针对所有的元素重复以上的步骤，除了最后一个
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
优化方案1（定义一个变量l来保存一趟交换中两两交换的次数，如果l==0,则说明排序已经完成，退出for循环）
优化方案2（假如有一个长度为50的数组，在一趟交换后，最后发生交换的位置是10，那么这个位置之后的40个数必定已经有序了，记录下这位置，下一趟交换只要从数组头部到这个位置就可以了）
定义一个变量n来保存一趟交换中最后一次发生交换的位置，并把它传递给下一趟交换
冒泡排序算法原理：（从小到大排序）
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，交换一趟后，最后的元素会是最大的数
3.针对所有的元素重复以上的步骤，除了最后一个
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较优化方案1（定义一个变量l来保存一趟交换中两两交换的次数，如果l==0,则说明排序已经完成，退出for循环）
优化方案2（假如有一个长度为50的数组，在一趟交换后，最后发生交换的位置是10，那么这个位置之后的40个数必定已经有序了，记录下这位置，下一趟交换只要从数组头部到这个位置就可以了）
定义一个变量n来保存一趟交换中最后一次发生交换的位置，并把它传递给下一趟交换
很棒～
/**
* 排序**:
* 对一组数字进行从小到大或者从大到小的进行排序。
* 它是通过让相邻的两个元素进行比较，大的元素向下沉，小的元素向上冒
* arr[0]与arr[1]进行比较，如果前者大于后者，则交换位置
* 然后arr[1]与arr[2]进行比较，以此类推。当进行到n-1轮后，排序完成。
*/
import java.util.Arrays;
public class Sort {
public static void main(String[] args){
int arr[]= {100,90,101,23,13,75};
int temp=0;
for(int i=0;i<arr.length-1;i++) {
for(int j=0;j<arr.length-1-i;j++) {
if(arr[j]>arr[j+1]) {
temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
System.out.println("第["+(i+1)+"]轮，排序结果:"+ Arrays.toString(arr));
}
System.out.print("================================");
int arr2[]= {100,90,101,23,13,75};
sort2(arr2);
}
/**
* 优化思路：
* 假如在第1轮比较当中，发现所有的元素都没有进行交换，则说明此原数据就是有序的，不需要再进行排序
* @param arr
*/
public static void sort2(int arr[]){
int temp=0;
int flag=0;
for(int i=0;i<arr.length-1;i++) {
flag=0;
for(int j=0;j<arr.length-1-i;j++) {
if(arr[j]>arr[j+1]) {
temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
//如果有交换的行为,则flag=1
flag=1;
}
}
//说明上面 内for循环中，没有交换任何元素。
if(flag==0) {
break;
}
System.out.println("第["+(i+1)+"]轮，排序结果:"+Arrays.toString(arr));
}
}
}
有在实践中应用过冒泡排序的吗？
冒泡排序：
1.相邻两个元素进行比较，大的元素往下沉，小的元素往上冒。
2.index[i]与index[i+1]进行比较，大的数据在下；小的数据在上；
反复进行比较；直到index[n-1]结束。
冒泡排序：
首先计算长度。
有两层循环。第一层循环控制比较的趟数，第二层则进行比较。
比较规则如下：
第一个元素和后面的元素挨个比较。完成之后，就是第二个元素和后面元素依次进行比较。知道倒着第一个和倒着的第二元素比较完后， 排序结束.
int[] ints = {52,7,2,9,1,7,653,1,47,55,5};
for (int i = 0; i < ints.length; i++) {
for (int j = i; j < ints.length; j++) {
if (ints[i] > ints[j]){
int temp = ints[i];
ints[i] = ints[j];
ints[j] = temp;
}
}
}
冒泡排序图解
上图 很形象啊
打卡打卡
很形象，打卡
打卡，上图点赞
首先冒泡排序，每次都与前一个进行比较，然后交换。所以，它的时间复杂度是：4*O(n^2)
重点解释一下这个常数，它是每次比较以及交换所消耗的次数。
对冒泡排序最直接的优化是：“插入排序”；它的**是，假设【0，k，n】当前位置是k，那么【0，k-1】是有序的，k在【0，k-1】中的某一个位置插入，假设位置是i，则将【i，k】往后搬移即可。它的时间复杂度是：O(n^2)
因为，它不需要比较然后交换，所以常数系数要小很多。作为同是稳定的排序算法，插入排序比冒泡排序效率高3.5倍左右（有人测试过）
对冒泡排序还有其它的优化方式，但原理已经相差比较大了。例如：并归排序、快速排序、堆排序
另外说明：记录一个flag，满足条件退出，并不算算法上的优化。