冒泡排序算法及其优化

ゞ浴缸里的玫瑰 2022-08-22 15:11 134阅读 0赞

冒泡排序算是排序算法里面的一种较为简单的算法，也是我接触的第一种排序算法，有升序与降序之分，如果面试的时候面试官问道这个题目，一定要问清楚是升序还是降序，这样会给你加分。

下面，我以升序来讲一下它的运作。

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

算法思想图：

假设有个数列为 3 1 5 6 2，我们以升序对它进行排序。

![Center][]

冒泡排序第一版：

#include<stdio.h>
    #include<stdlib.h>
    void bubblesort(int *p,int len)
    {
    int i = 0;
    int j = 0;
    for(i = 0;i<len-1;i++)
    {
    /*每排序一趟，则至少有一个元素已经有序，
    用 j<len-i-1 可以缩小排序范围 */
    for(j = 0;j<len -1-i;j++)
    {
    /*当前面的元素大于后面的元素时，交换位置*/
    if(p[j]>p[j+1])
    {
    int tmp = p[j];
    p[j] = p[j+1];
    p[j+1] = tmp;
        }
    }
    }
    }
    int main()
    {
    int num[5]={3,1,5,6,2};
    int i=0;
    bubblesort(num,5);
    for(i=0;i<5;i++)
    {
    printf("%d ",num[i]);
    }
    return 0;
    } 
    printf("%d ",num[i]);
    }
    return 0;
    }

当数列在基本有序的情况下时，例如数列：

1 2 3 5 4 6 7 8 9 10

在第一趟排序 5 和 4 交换之后数列就已经有序了，所以剩下的8趟排序就是多余的。再用上面的算法处理这个数列，效率就显得低了。所以，我们对它添加一个检视flag。

冒泡排序优化版：

#include<stdio.h>
    #include<stdlib.h>
    void bubblesort(int *p,int len)
    {
    int i = 0;
    int j = 0;
    int flag;  
    for(i = 0;i<len-1;i++)//
    {
    /*flag初始化为0*/
    flag = 0;
    /*每排序一趟，则至少有一个元素已经有序，
    用 j<len-i-1 可以缩小排序范围 */
    for(j = 0;j<len -1-i;j++)
    {
    /*当前面的元素大于后面的元素时，交换位置*/
    if(p[j]>p[j+1])
    {
    int tmp = p[j];
    p[j] = p[j+1];
    p[j+1] = tmp;
    /*若程序进入if语句,则必然会发生交换，
    当发生交换时把flag置成 1 */ 
    flag = 1;
    }
    }
    /*判断,如果flag=0，说明上一趟排序没有发生交换，
    数列已经有序，break*/ 
    if(flag == 0)
    {
    break;
    }
    }
    }
    int main()
    {
    int num[10]={1,2,3,5,4,6,7,8,9,10};
    int i=0;
    bubblesort(num,10);
    for(i=0;i<10;i++)
     { printf("%d ",num[i]);
       }
    return 0;
      }

其实上面的算法还可以进行优化，来看下面一组数据：1 2 7 4 6 3 5 8 9

首先我们要知道：

![Center 1][]

当它每完成一趟排序的适合，我们记住它最后一次交换的位置，也就是flag最后一次置1的位置，我们假设这个位置为P，P之后的元素已经有序，P之前的元素还可能无序。所以我们只需要对P之前的元素再进行排序就可以了

![Center 2][]

我们将前面无序区的数列当做一个新的数列，把它的新长度传给第一层循环，这样就可以大大减少循环次数，提升效率。

冒泡排序最终优化版：

#include<stdio.h>
    #include<stdlib.h>
     void bubblesort(int *p,int len)
     {
     	int i = 0;
     	int j = 0;
     	int k = len-1; 
     	int m = 0;
     	int flag;  
     	/*用k来保存新的判断条件*/ 
     	for(i = 0;i<k;i++)
     	{
    	 /*flag初始化为0*/
     	 flag = 0;
     	 m = 0;
     	/*每排序一趟，则至少有一个元素已经有序，
    		 用 j<len-i-1 可以缩小排序范围 */
    	for(j = 0;j<len-1-i;j++)
    	{
    	/*当前面的元素大于后面的元素时，交换位置*/
            if(p[j]>p[j+1])
    	{
    	int tmp = p[j];
    	p[j] = p[j+1];
    	p[j+1] = tmp;
    	 /*若程序进入if语句,则必然会发生交换，
    		    当发生交换时把flag置成 1 */ 
    	flag = 1;
    	/*记住最后一次交换的位置*/ 
            m = j;
    	 }
    	}	
    	/*判断,如果flag=0，说明上一趟排序没有发生交换，
    	数列已经有序，break*/ 
    	if(flag == 0)
    	{
    	 break;
    	}
    	/*将新的长度赋值给k*/	
    	k = m;	
    	}
     }
     int main()
     {
       int num[10]={1,2,7,4,6,3,5,8,9};
       int i=0;
       bubblesort(num,9);
       for(i=0;i<9;i++)
       {
        printf("%d ",num[i]);
       }
     	return 0;
      }

[Center]: /images/20220722/1b4c676a82de420e9337cbd485d28ea1.png
[Center 1]: /images/20220722/91a8d257842348a3894b418cb8670f68.png
[Center 2]: /images/20220722/bb7e83b72efe40a6bffa11ff8db53311.png