冒泡排序与选择排序

2020-03-28

一、冒泡排序

1、经典冒泡排序:

经典冒泡排序算法，从头开始比较每一对相邻元素，把大的元素往后调，并且只是两两交换。我们默认从第二个元素（即索引为1的元素）开始比较，因为只会交换比它大或者小的元素，因此冒泡排序是一个稳定的排序算法。

代码如下

public class Main {

    public static void main(String[] args) {
        int arr[]={1,5,6,10,14,3,8,42,21};
        for(int j=arr.length-1;j>0;j--){
            for(int i=1;i<=j;i++){

                if(arr[i-1]>arr[i]){
                  //交换操作
                    int temp=arr[i];
                    arr[i]=arr[i-1];
                    arr[i-1]=temp;
                }
            }
        }
    }
}

2、通过以上分析，不管后一个元素是不是比前一个元素大，我们都要进行两两比较。这时候我们是否可以通过设置一个参数，来提醒程序跳过这个步骤。

public class Main {

    public static void main(String[] args) {
        int arr[]={1,5,6,10,14,3,8,42,21};
        for(int j=arr.length-1;j>0;j--){
            //表明不需要交换
            boolean flag=true;
            for(int i=1;i<=j;i++){
                if(arr[i-1]>arr[i]){
                    int temp=arr[i];
                    arr[i]=arr[i-1];
                    arr[i-1]=temp;
                    //如果进入到这个步骤，改变flag
                    flag=false;
                }
            }
            if(flag=true)
                break;
        }
    }
}

通过增加一个参数，我们可以明显的减少比较次数，从而提升冒泡排序的性能。

想象一个最好的情况，如果这组元素在一开始就是有序的，那么此优化方式是有效的！

3、但是，上面的优化不一定有效。此时我们想象最差的情况，如果是逆序的话，那么上面的优化则毫无效果。即我们总是要交换最多的次数，接下来我们进行第二次优化。即每一次大循环后，排在最后的一定是最大的元素。我们可以记录最后交换的位置。这样可以减少交换次数。

public class Main {
	
  public static void main(String[] args) {
	    int arr[]= {1,6,2,8,19,23,54,21,17};
	    for(int j=arr.length-1;j>0;j--) {
	    	//这个初始值是为完全有序做准备的
	    	int sortIndex=j;
	    	 for(int i=1;i<=j;i++) {
	   		  if(arr[i-1]>arr[i]) {
	   			  int temp=arr[i];
	   			  arr[i]=arr[i-1];
	   			  arr[i-1]=temp;
	   			  sortIndex=i;
	   		  }
	   	  }
	    	 j=sortIndex;
	    }	  
}

}

总结：冒泡排序算法在最好的情况下，即元素是有序的情况下，此时时间复杂度为O（n）。

在最差情况下，即元素是逆序时，时间复杂度是O（n^2）。

平均下来，冒泡排序的时间复杂度是O（n^2）. 空间复杂度为O(1)。

二、选择排序

所谓选择排序。就是从一串数字中选择一个最大或者最小的数字。如果我们选择那个最大的数据，将其放在这组数据的末尾，如果我们选择最小的那个数据，将其放在这组数据的开头。其大致过程和冒泡排序类似。都是经过以上的“两重循环”。按照选择最大的那个数据为例，我们记录那个数据的位置maxIndex。如果碰到比他大的数字，就交换索引，直到得到最大元素的那个索引。然后在与数组中最后一个元素交换位置。

public class Main {
	
	public static void main(String[] args) {
		
		  int arr[]= {1,6,2,8,19,23,54,21,17};
		    for(int j=arr.length-1;j>0;j--) {
		    	int maxIndex=0;
		    	 for(int i=1;i<=j;i++) {
		    		 if(arr[i]>=arr[maxIndex]) {
		    			 maxIndex=i;
		    		 }
		   	  }
		    	 int temp=arr[j];
		    	 arr[j]=arr[maxIndex];
		    	 arr[maxIndex]=temp;	 
		    }
		    
	}

}

对于以上的选择排序，我们不难看出其实质跟冒泡排序差不多，而且时间复杂度也是O(n^2),空间复杂度，由于没有引入新的内存，为O（1）。

我们可以将其进行优化。选择排序的实质是选出里面最大或者最小的元素，那么，有什么数据结构可以轻而易举的实现呢。这时候我们就想起了堆，利用最大堆（最小堆）我们可以以O（logn）的复杂度拿出最大（最小元素）。而原地起堆的复杂度为O（n），这时候我们就以O（nlogn）的复杂度实现了另外一种“选择排序”，其实是堆排序（在这里就不详细讨论了）。