冒泡排序之C语言实现

超、凢脫俗 2022-04-24 23:04 220阅读 0赞

### 改进版的冒泡排序 ###

*  具体代码
 *  过程分析
 *  性能分析

# 具体代码 #

#include<stdio.h>
    	
    	//输入数组名字和数组内的元素个数
    	void BubbleSort(int* R, int n)
    	{
        
    		
    		int i=n-1;		//i用来指示冒泡过程的结尾位置 
    		int j;			//j是用于遍历的
    		int temp;		//temp用于临时交换的容器
    		int index;		//标记最后依次发生位置交换的位置
    		
    		//开始循环操作
    		
    		while(i>0)		//当冒泡结尾的位置不是0的时候一直交换
    		{
        
    			index = 0;  //一开始默认设为0处，如果for中没发生交换改动，就直接结束  
    			
    			//在到结尾标志之前，一直冒泡
    			for(j=0;j<i;j++)	
    			{
        
    				//如果发生交换，同时标记下j的位置
    				if(R[j]>R[j+1])
    				{
        	 
    					temp = R[j]; 
    					R[j] = R[j+1];
    					R[j+1] = temp;
    					index = j;
    				}
    			}
    			//把index的值给i只是为了更方便while去判断和上面index=0的操作
    			i=index;
    		}
    	} 
    	
    	//用于测试的主函数
    	int main()
    	{
        
    		int M[6] = {
        1,6,2,5,4,7};	
    		BubbleSort(M,6);
    		for(int i=0;i<6;i++)
    		{
        
    			printf("%d  ", M[i]);	
    		}
    	}

# 过程分析 #

从下图中，箭头所指的位置就是对应代码部分的 i ，代表的是冒泡结尾的位置。也就是每轮里循环指针j+1指到的位置。由于第一次，整个数组都是乱序的，所以将结尾标记设置在最后面，其物理位置为6-1=5。

![在这里插入图片描述][20190429233930291.png]  
第一轮：j 从0到4（物理位置4，恰巧起值也是4），交换过后，index标记表示最后一次发生交换的 j 的位置，也就是3（物理位置3，交换过后值是4）。 把index的值赋给 i 来给while判断，可以继续循环，于是下一轮开始。

![在这里插入图片描述][20190429233951463.png]  
第二轮：现在的结束位置 i = 3 。其实结束位置的右边的数组都是已经有顺序的了（但是 i 这个位置并不能保证和后面是有顺序的，因为冒泡的时候这个位置的值还可能被冒了）。第二轮 j 从0冒到2。 结束标记变为2。

![在这里插入图片描述][20190429234014529.png]  
第三轮：再冒一轮，现在就已经是顺序的了！！！

但是按照程序还要冒第四轮。第四轮什么都不交换，所以index的值就是0，所以触发结束条件。冒泡完毕！

# 性能分析 #

相比于传动的冒泡排序一次只让冒泡结尾往前走一格相比，这个版本则会直接通过记录交换结尾来找到无序队列的最尾部（因为没发生交换的地方一定是交换的整整齐齐的了）。

最后，借用刘峤老师的一张ppt（因为我真的打不出那个sigma符号XD）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70]

[20190429233930291.png]: /images/20220212/1660948d53ae4079b192e3eb8af92957.png
[20190429233951463.png]: /images/20220212/3ecaf08972a344099484b4eec7768008.png
[20190429234014529.png]: /images/20220212/803ada3c996c490d9775d9b85af89324.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70]: /images/20220212/60e935e3241d4e5da4ae4024946b4420.png