冒泡排序与选择排序的实现与分析

矫情吗；* 2022-05-10 13:48 159阅读 0赞

冒泡排序与选择排序是两种非常基础的排序方式，也是许多程序员入门的排序算法。很多数据结构或者算法教材清晰明了地描述了两种排序的工作原理，复杂度等，但纸上得来终觉浅，为了摸清楚两种算法的性能，我还是亲自动手操作了一波~~~

下面请跟上我的思路~~~

冒泡排序作为最最基础的排序方法，应该连小学生也能弄懂它的原理（如果你看不懂的话建议重新去小学深造，开个玩笑）：

1.  比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2.  对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

为了说明这一情况，我们先写个程序来跑一下：

************************************************
    public static void main(String[] args){
    		int[] a={10, 7, 5, 4, 8, -3, 6};
    		bubble_sort.sort(a);
    	}
    ************************************************
    下面是每一次排序的过程（一段算一次）
    7 10 5 4 8 -3 6 
    7 5 10 4 8 -3 6 
    7 5 4 10 8 -3 6 
    7 5 4 8 10 -3 6 
    7 5 4 8 -3 10 6 
    7 5 4 8 -3 6 10 
    
    5 7 4 8 -3 6 10 
    5 4 7 8 -3 6 10 
    5 4 7 8 -3 6 10 
    5 4 7 -3 8 6 10 
    5 4 7 -3 6 8 10 
    
    4 5 7 -3 6 8 10 
    4 5 7 -3 6 8 10 
    4 5 -3 7 6 8 10 
    4 5 -3 6 7 8 10 
    
    4 5 -3 6 7 8 10 
    4 -3 5 6 7 8 10 
    4 -3 5 6 7 8 10 
    
    -3 4 5 6 7 8 10 
    -3 4 5 6 7 8 10 
    
    -3 4 5 6 7 8 10
    ***************************************************
    可以看到，每一次排序，相邻元素里面大的那个都会跑到后面去
    尽管有的排序（因为元素已经有序）算不上真正意义上的排序，
    比如后两次，这依赖于输入元素的次序。
    ***************************************************
    冒泡排序算法：
    public static void sort(int[] a){
    		int n=a.length;
    		for (int i=0; i<n-1; i++)
    		{
    			for (int j=0; j<n-i-1; j++)
    			{
    				if (a[j]>a[j+1])
    				swap(a, j, j+1);
    			}//for 2
    		}//for 1
    	}
    ***************************************************

说完了冒泡，我们来说一下选择排序：

原理很简单。首先，找到数组中最小的那个元素，其次，将它和数组的第一个数交换；再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。以此类推，直到数组全部有序。总的来说就是在不断地选择剩余元素中的最小者。

来看怎么排的：

***************************************************
    public static void main(String[] args){
    		int[] a={10, 7, 5, 4, 8, -3, 6};
    		select_sort.sort(a);
    	}
    ***************************************************
    第0次排序
    10 7 5 4 8 -3 6 
    min=5, a[min]=-3
    
    第1次排序
    -3 7 5 4 8 10 6 
    min=3, a[min]=4
    
    第2次排序
    -3 4 5 7 8 10 6 
    min=2, a[min]=5
    
    第3次排序
    -3 4 5 7 8 10 6 
    min=6, a[min]=6
    
    第4次排序
    -3 4 5 6 8 10 7 
    min=6, a[min]=7
    
    第5次排序
    -3 4 5 6 7 10 8 
    min=6, a[min]=8
    
    第6次排序
    -3 4 5 6 7 8 10 
    min=6, a[min]=10
    *****************************************************
    和冒泡排序相比，选择排序省去了相邻元素的移动，每次排序只
    交换a[min]和a[i]的位置，大大减少了时间开销。
    *****************************************************
    选择排序算法:
    public static void sort(int[] a){
    		int n=a.length;		
    		for (int i=0; i<n; i++)
    		{
    			int min=i;
    			for (int j=i+1; j<n; j++)
    				if (a[j]<a[min])
    					min=j;//for 2	
    			swap(a, min, i);
    		}//for 1
    	}
    *****************************************************

直观上，我们认识了两种排序算法。现在我们来定量分析它们：

首先说【冒泡排序】，外层循环确定每次排序的结果，内层循环不断交换目的元素。

冒泡排序的性能很大程度上依赖于输入，假设数组初始为正序的，那么一趟扫描即可完成排序。

正序情况下，设所需关键字的比较次数为C，记录的移动次数为M，数组长度为n-1，则C=Cmin=n-1，M=Mmin=0。由此可见，冒泡排序的时间复杂度最优为O(n)。你可能会猜到，对于冒泡排序来说，最坏的情况莫过于初始状态为逆序了。的确如此，当数组逆序时，需要n-1趟排序，每趟排序需要n-i次关键字比较，且每次比较都必须交换相邻元素（1次交换看做3次移动），此时C=Cmax=n(n-1)/2，M=Mmax=3Cmax=3n(n-1)/2，其时间复杂度为O(n^2)。为了验证以上推论，我们还是通过程序来说明：

******************************************************
    public class bubble_sort {
    	public static void sort(int[] a){
    		int n=a.length;
    		int C=0, M=0;
    		for (int i=0; i<n-1; i++)
    		{
    			C++;
    			for (int j=0; j<n-i-1; j++)
    			{
    				if (a[j]>a[j+1])
    				{
    					swap(a, j, j+1);
    					M+=3;
    				}	
    			}//for 2
    		}//for 1
    		System.out.println("C="+C+", M="+M);
    	}
    }
    ******************************************************
    正序：
    输入int[] a={1, 2, 3, 4, 5, 6, 7};
    测试：C=6, M=0
    
    逆序：
    输入int[] a={7, 6, 5, 4, 3, 2, 1};
    测试：C=6, M=63
    
    乱序：
    输入int[] a={10, 7, 5, 4, 8, -3, 6};
    测试：C=6, M=45
    
    =>冒泡排序性能：正序>乱序>逆序
    ******************************************************

接下来看【选择排序】

从原理来看，对于长度为n的数组，选择排序一定会交换n次元素。并且0到n-1的任意i都会进行一次交换和n-i-1次比较，所以总的比较次数为n(n-1)/2，时间复杂度依然是O(n^2)。请看代码：

******************************************************
    public class select_sort {
    	public static void sort(int[] a){
    		int n=a.length;	
    		int C=0, M=0;
    		for (int i=0; i<n; i++)
    		{
    			C++;
    			int min=i;
    			for (int j=i+1; j<n; j++)
    				if (a[j]<a[min])
    					min=j;//for 2	
    			swap(a, min, i);
    			M+=3;
    		}//for 1
    		System.out.println("C="+C+", M="+M);
    	}
    }
    ******************************************************
    正序：
    输入int[] a={1, 2, 3, 4, 5, 6, 7};
    测试：C=6, M=21
    
    逆序：
    输入int[] a={7, 6, 5, 4, 3, 2, 1};
    测试：C=6, M=21
    
    乱序：
    输入int[] a={10, 7, 5, 4, 8, -3, 6};
    测试：C=6, M=21
    
    选择排序性能和输入无关，且数据移动次数最少
    ******************************************************

可能对于上面测试数据那样小规模的输入，两种算法都可以在一瞬间做完工作。但对于成千上万个数据来说，算法的性能就能决定你的心情。不信的话来测试一下：

设n为随机数组的长度，对于两种不同排序算法分别进行t次运行时间测试
    最后取平均值（单位s）。设t=100
    
    test1：
    n=100
    选择排序：0.011000000000000003
    冒泡排序：0.014000000000000005
    
    test2：
    n=200
    选择排序：0.027000000000000017
    冒泡排序：0.024000000000000014
    
    test3:
    n=400
    选择排序：0.030000000000000013
    冒泡排序：0.045000000000000026
    
    test4:
    n=1600
    选择排序：0.23700000000000018
    冒泡排序：0.42700000000000027
    
    test5:
    n=6400
    选择排序：3.3909999999999996
    冒泡排序：7.593000000000002
    
    test6:
    n=20000
    选择排序：34.11899999999999
    冒泡排序：116.45700000000005
    
    test7:
    已失去耐心

数据证明了对于小规模的排序，冒泡和选择差别并不大。当数据越来越大时，二者耗时的差距也越来越大，但两个算法的时间复杂度都是O(n^2)，为什么冒泡会比选择慢这么多呢？究其原因，在于冒泡的移动元素次数实在太多，如果你的电脑买的便宜，还是选一种快一点的算法吧！但冒泡也具有优越性，那就是它具有稳定性，也就是说相同键值的元素相对位置在排序前后并不改变（这一点通过代码自己体会），而选择排序就不具有稳定性。

当然你可以测试冒泡排序在正序情况下的样例，那样没有交换操作。