冒泡排序算法的实现和优化~
冒泡排序算法：
算法思想：
反复扫描待排序记录序列，在扫描的过程中，顺次比较相邻的两个元素的大小，若逆序就交换位置
文字描述该算法：
以升序为例：
依次比较数组中相邻两个元素大小，若a[j]>a[j+1],则交换两个元素，两两都比较一遍称为一轮冒泡，结果是让最大的元素排至最后，重复该步骤，直至整个数组称为一个升序数组
初步实现：
package bin_find;
import java.util.Arrays;
public class bubble_sorted {
public static void main(String[] args) {
int arr[]={3,19,10,21,1,87,55,34};
bubble(arr);
}
//冒泡排序的过程
public static void bubble(int[] arr){
//本次冒泡排序的目的是将数组的元素从小到大排序
for(int j=0;j<arr.length-1;j++) {//控制要进行冒泡排序的次数--->n个数进行冒泡排序需要进行n-1轮
for (int i = 0; i < arr.length - 1; i++){//一次for完成一轮排序
if (arr[i] > arr[i + 1]) {//前者大于后者--->交换位置
swap(arr, i, i + 1);
}
System.out.println("比较的次数为"+(i+1));
}
System.out.println("第"+(j+1)+"轮冒泡排序结果"+Arrays.toString(arr));
}
}
//冒泡排序----核心算法
public static void swap(int[] a,int i,int j){
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
输出如下所示：
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第1轮冒泡排序结果[3, 10, 19, 1, 21, 55, 34, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第2轮冒泡排序结果[3, 10, 1, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第3轮冒泡排序结果[3, 1, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第4轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第5轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第6轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第7轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
优化版本1：减少冒泡次数
方法如下：
输出：
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第1轮冒泡排序结果[3, 10, 19, 1, 21, 55, 34, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
第2轮冒泡排序结果[3, 10, 1, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
第3轮冒泡排序结果[3, 1, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
第4轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
第5轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
第6轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
第7轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
优化版本2：减少比较次数
方式1：
对于第一次到的优化输出结果，细心的小伙伴应该都发现了，其实第五次数组就已经是有序数组了，而最后两次元素之间的次序并没有任何的变化，这无疑增加了不必要的比较次数，那么接下来，我们通过判断该数组是否还存在元素交换，进而去确定，它是否需要进行下一轮的排序。
代码如下：
package bin_find;
import java.util.Arrays;
public class bubble_sorted {
public static void main(String[] args) {
int arr[]={3,19,10,21,1,87,55,34};
bubble(arr);
}
//冒泡排序的过程
public static void bubble(int[] arr){
for(int j=0;j<arr.length-1;j++) {
boolean swapped=false;
for (int i = 0; i < arr.length - 1-j; i++){
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
swapped=true;//只要某一轮中有进行交换的现象----将该变量设置为true
}
System.out.println("比较的次数为"+(i+1));
}
System.out.println("第"+(j+1)+"轮冒泡排序结果"+Arrays.toString(arr));
//若swapped此时还为false：说明一轮冒泡结束，没有任何的两个元素发生交换---说明该数组已经变为有序数组
if (!swapped){
break;
}
}
}
//冒泡排序----核心算法
public static void swap(int[] a,int i,int j){
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
输出如下：
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第1轮冒泡排序结果[3, 10, 19, 1, 21, 55, 34, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
第2轮冒泡排序结果[3, 10, 1, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
第3轮冒泡排序结果[3, 1, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
第4轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
第5轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
对比第一次的优化结果，我们会发现，比较次数整整少了两次，这里我们的好像还不能完全体现出该优化的优点，但是在原本就是有序数组的情况下，我们就能够体会到这个优点
举例：
对于任意的有序数组：
int arr[]={1,2,3,4,5,6,7,8};
输出如下：
它只比较了一次！
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第1轮冒泡排序结果[1, 2, 3, 4, 5, 6, 7, 8]
方式2：
对于某些数组，当第一轮排序过后，可能不仅是一个元素到达了最终的位置，也许是好几个，如下所示的这种情况：
当第一轮比较完成之后，我们会发现元素7 8 9都已经到达了最终的位置，那么第二轮乃至以后在比较的过程中，大可不必比较这三个元素的的大小，但是我们要怎么才能实现呢？
优化方式为：每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为0，表示整个数组有序，直接退出外层循环，结束冒泡排序
拿上面这种情况解释，也就是说，下一次，我们第一轮结束之际，需要记录元素3的索引，也就是4，第二轮比较的时候，只需要将前五个元素一一进行比较。
代码如下：
package bin_find;
import java.util.Arrays;
public class bubble_sorted {
public static void main(String[] args) {
int arr[]={5,2,7,4,1,3,8,9};
bubble(arr);
}
//冒泡排序的过程
public static void bubble(int[] arr){
int n=arr.length-1;
while (true){
//用于记录最后一次交换时，较小索引的值,由于last的值在不断的变化，因此使用变量n进行记录
int last=0;
for (int i = 0; i < n; i++){//n即为下一次参与比较的元素个数，即为本轮last的值
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
last=i;//由于是较小索引的值，因此将i赋值给last，而不是i+1
}
System.out.println("比较的次数为"+(i+1));
}
System.out.println("冒泡排序结果"+Arrays.toString(arr));
n=last;
if (n==0){//表示结束排序
break;
}
}
}
//冒泡排序----核心算法
public static void swap(int[] a,int i,int j){
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
输出如下：
我们会发现第二次只比较了4次，也就是前5个元素参与比较并进行排序了
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
冒泡排序结果[2, 5, 4, 1, 3, 7, 8, 9]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
冒泡排序结果[2, 4, 1, 3, 5, 7, 8, 9]
比较的次数为1
比较的次数为2
比较的次数为3
冒泡排序结果[2, 1, 3, 4, 5, 7, 8, 9]
比较的次数为1
比较的次数为2
冒泡排序结果[1, 2, 3, 4, 5, 7, 8, 9]