冒泡算法及改进(Java实现).md

1.基本冒泡排序

1.概述:

冒泡排序是一种典型的交换排序,通过交换元素的位置进行排序,从这篇文章开始,逐一总结八大排序算法,做到烂熟于心。

2.Java实现

package demo;

import java.util.Arrays;
import java.util.Random;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[10];//初始化一个数组
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(10);
        }
        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];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            System.out.println("第"+(i+1)+"趟排序后的数组:");
            System.out.println(Arrays.toString(arr));
        }
    }
   
}

3.示意图

image

我们主要进行关心的就是双重for循环以及其中的交换操作,首先外层循环表示要进行比较的趟数,每一趟都会产生一个最大值或最小值,这也就是冒泡的由来,i的范围限定为i < arr.length - 1,为什么不是i < arr.length呢?由上图可知,当未排序的数组中只有一个元素时,不需要再进行比较了,这时整个数组已经是有序状态了。那么内层循环中,为什么 j 的限制条件 为j < arr.length - 1 - i呢?这个也比较好理解,首先第一次的时候,要把 j 的范围限制在j < arr.length - 1 -0,这样arr[j] > arr[j+1]这样的操作才不会出现数组越界,进行第二趟比较的时候,arr[length -1]位置的元素已经是最大的,不需要再进行比较,这时候就要写成j < arr.length - 1 - 1,总结起来就是j < arr.length - 1 - i

还需要进行拿捏得一个细节就是,arr[j] > arr[j+1]这个比较一定不要写成arr[j] >= arr[j+1],虽然在最终的结果上没什么影响,但是会破坏稳定性,使相同大小的元素前后顺序发生改变!!!

但是我们进一步探究,上面的代码是存在这样的弊端的:加入第二趟排序之后,数组就已经是有序状态了,那么后面的几趟比较是不是非常多余呢?下面介绍冒泡排序的改进


2.冒泡排序的改进

1.改进一:使用flag变量

直接上以实现代码:

package demo;

import java.util.Arrays;
import java.util.Random;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[10];//初始化一个数组
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(10);
        }
        int temp = 0;//用于交换
        boolean flag = false;
        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]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if(!flag){
                break;
            }else{
                flag = false;
            }
            System.out.println("第"+(i+1)+"趟排序后的数组:");
            System.out.println(Arrays.toString(arr));
        }
    }
}

代码都是自己在IDE中实现的,直接全部贴过来了,虽然看起来很冗长,其实关键的核心代码就那么几行,我们来看具体的改进方法,采用的方法就是设置一个flag变量,在当前这一趟比较中,如果发生了元素的交换,那么将flag设置为true,如果这趟比较从头到尾都没有进行过交换,那么最终的flag值为false,直接break退出循环。

2.改进二:鸡尾酒排序😄

直接上图演示:

20170312144555263

用我自己的话理解呢,这个改进就是在之前的单向寻找最大值的基础上,增加了反向寻找最小值,也就是双向冒泡,总体上来讲,鸡尾酒排序要比普通冒泡排序的交换次数要少,但是对于鸡尾酒排序,在算法的时间复杂度和空间复杂度上并没有改进,在完全逆序数组进行排序时,不管是普通的还是改进的,表现得都是非常差。

代码实现:

void Bubble_2 ( int r[], int n){
	int low = 0; 
	int high= n -1; //设置变量的初始值
	int tmp,j;
	while (low < high) {
		for (j= low; j< high; ++j) //正向冒泡,找到最大者
			if (r[j]> r[j+1]) {
				tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
			} 
		--high;					//修改high值, 前移一位
		for ( j=high; j>low; --j) //反向冒泡,找到最小者
			if (r[j]<r[j-1]) {
				tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;
			}
		++low;					//修改low值,后移一位
	} 
} 

3.性能总结

1.时间复杂度:

当原始序列为正序时,并且设置了flag变量,那么这时最好的情况为比较n-1次,时间复杂度为O(n)

当原始序列为逆序时, 对于n个元素,相邻元素均要比较,共有(n-1)次。经过一回合冒泡过程后,最大元素沉淀到最右位置。第二回合, 只剩下(n-1)个元素,只需要比较(n-2)次。依次类推,其他比较次数为(n-3),......,2,1. 所以总共比较次数为n(n-1)/2,而且是固定为这个数目。 至于交换次数,这个取决于初始序列的逆序数。对于数组A[1,...,n],如果对于i<j有A[i]>A[j],则称(A[i],A[j])是一个逆序对,序列中逆序对的个数称为逆序数。

冒泡排序每次交换,只改变了相邻两元素的位置,不影响和其他元素之间的逆序关系,因而,逆序数只减1。所以,冒泡排序交换次数等于初始序列的逆序数。最坏情况下的时间复杂度为O(n^2);

当原始序列杂乱无序时,冒泡排序的平均时间复杂度为O(n^2)。

2.空间复杂度

冒泡排序排序过程中需要一个临时变量进行两两交换,所需要的额外空间为1,因此空间复杂度为O(1)。

3.稳定性

上面已经提到,冒泡排序是一种稳定性算法。