冒泡排序的原理

  将一维数组中每一个元素从左到右分别和其后所有的元素比较,需要内(i)外(j)两层循环进行遍历比较,按照降序(升序)的方式将元素排列。
  这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

#include <stdio.h>


//功能:从终端获取一个纯数字的一维数组,将其内数字按照(升序/降序)排序


void mymaopao(int*a,int len,int p){    //定义指针参数a 指向一维数组的首地址
                                       //整形参数len,p 分别对应数组的长度和判断排序的方式
        int i = 0;
        int j = 0;
        int temp = 0;
		if(p == 0){
        	for(i = 0; i < len-1; i++){    //防止最后一次比较越界 循环次数 -1            	        
                for(j = 0; j < len-1-i; j++){    //排好的元素无需重复比较 
                                                    //循环次数 -1 - 外循环
            	if(*(a+j)>*(a+j+1)){        //使用“三杯水交换”进行值传递
					temp = *(a+j);
					*(a+j) = *(a+j+1);
					*(a+j+1) = temp;
            	}
        	}
    	}
	}else if(p == 1){
        	for(i = 0; i < len-1; i++){
            	for(j = 0; j < len-1-i; j++){ 
            	if(*(a+j)<*(a+j+1)){
					temp = *(a+j);
					*(a+j) = *(a+j+1);
					*(a+j+1) = temp;
            	}
        	}
    	}
	}
		printf("排序后为:\n");
        for(i = 0; i<len; i++){
        printf("%d ",*(a+i));
}
        printf("\n");
        return;
 }
int main(){
        int s[64] = {0};    //数组定义的大小会影响输入数组的长度和数组元素的个数
        int len = 0;
		int i = 0;
		int p = 0;
		printf("输入数组长度\n");
		scanf("%d",&len);
		printf("输入排序方式(升序0降序1)\n");
		scanf("%d",&p);
		printf("输入数组元素\n");
		for(i=0; i<len; i++){
			scanf("%d",s+i);
		}
        mymaopao(s,len,p);
    return 0;
}

注意:

1.终端输入数组长度受主函数中数组大小的限制,需要定义足够大的数组大小。

2.数组名可作为数组的首地址,可以做为函数指针参数的实参。

运行结果:

1.升序:

2.降序:

关于冒泡函数的优化:

        根据大O记法🔍我们可以得出冒泡排序的时间复杂度为O(n²)。

        但是我们在冒泡排序中会遇到两个特殊情况,就是数组元素本身的顺序。

        eg:s1[10] = {1,2,3,4,5,6,7,8,9,10};

                s2[10] = {10,9,8,7,6,5,4,3,2,1};

        针对这两个数组在我们以升序或者降序排序的时候,都会面临一个问题。

        是否要排序?

        就像我们在将s1升序排序/s2降序排序,这样的排序就没有意义。但是程序的时间复杂度仍然是O(n²)。所以我们需要对代码进行优化。

        优化方式:增加标志位

        通过增加标志位的方式,我们可以让冒泡排序在特殊情况下(本身顺序排好)的情况下,程序的时间复杂度变为O(n)。

 代码实现:

#include <stdio.h>

int main(int argc, const char *argv[])
{
    int s[10] = {23,10,2,3,56,123,55,12,19,90};
    int flag = 0;   //定义标志位
    for (int i = 0; i < 9-1; i++)
    {
        for (int j = 0; j < 9-1-i; j++)
        {
            if (s[j] > s[j+1])
            {
                flag = 1;   //如果数据需要排序,令标志位为 1
                int temp;
                temp = s[j];
                s[j] = s[j+1];
                s[j+1] = temp;
            }
        }
        if(0 == flag)   //如果不需要排序,flag默认为0,跳出排序 此时j已改变,不再重复排序
        break;
    }
    return 0;
}
Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐