常见的冒泡排序、顺序查找和对半查找

妖狐艹你老母 2023-03-14 10:51 115阅读 0赞

### 关于一维数组的排序和查找 ###

*  排序算法
 *   *  冒泡排序
     *  改进的冒泡排序
 *  查找算法
 *   *  顺序查找
     *  对半查找

先看例题
    
    从键盘上任意输入8个整数，用冒泡排序法对8个数排序（由小到大）

从键盘上输入整数，利用`for循环`输入

printf("输入要输入的整数个数：");
    scanf("%d",&max);
    int i，a[max];
    printf("输入数组元素：\n");
    for(i=0;i<max;i++)
    { 
    	scanf("%d",&a[i]);
    }

# 排序算法 #

## 冒泡排序 ##

思路：`升序`  
通过相邻之间的比较和交换，使值较小的数逐渐从底部移向顶部，值较大的数逐渐移向底部；

就像水底的气泡一样逐渐向上冒；

======================================
    原数据	第一轮	第二轮	第三轮	第四轮
    	2		2		2		2		1
    	5		4		3		1		2
    	4		3		1		3		3
    	3		1		4		4		4
    	1		5		5		5		5
    ======================================
    将原数据序列 2、5、4、3、1 按升序排列
    ------------------
    第一轮结束时，5沉底
    第二轮结束时，4沉底
    第三轮结束时，3沉底
    第四轮结束时，2沉底
    ------------------
    从而得到从小到大的序列

由`a[0] ~ a[n-1]`组成的n个数据，从小到大进行冒泡排序的过程描述

1.  首先将相邻的`a[0]`与`a[1]`进行比较，如果a\[0\]的值大于a\[1\]的值，则交换两者的位置，使较小的上浮，较大的下沉；接着比较a\[1\]与a\[2\]，同样使小1的上浮，大的下沉，以此类推，直到比较完`a[n-2]`和`a[n-1]`；此时，a\[n-1\]为最大值的元素，第一趟排序结束
2.  然后在`a[0] ~ a[n-2]`区间内，进行第二趟排序，使剩余元素中最大的元素下沉到`a[n-2]`
3.  直到整个数组有序，上述“下沉”的过程最多需要重复进行`n-1次`

#if 0
    简单的冒泡排序 
    #endif
    
    #include<stdio.h>
    int main(void)
    { 
    	int a[8]={ 19,9,87,12,-76,0,-45,123};	/*初始化数组*/
    	int i,j,t;	/*定义循环变量和临时变量*/
    	
    	printf("待排序数组：\t");
    	for(i=0;i<8;i++)
    	{ 
    		printf("%6d",a[i]);	/*宽度为6*/
    	}
    	
    	printf("\n");
    	
    	/*开始排序（冒泡排序）*/
    	for(j=0;j<8-1;j++)	/*外循环：控制循环次数（两个两个比较只需比较8-1次）*/
    	{ 
    		for(i=0;i<8-1-j;i++)	/*内循环：每趟参与比较的元素个数（每交换一次，减少一个需要比较元素）*/
    		{ 
    			if(a[i]>a[i+1])	/*升序排列*/
    			{ 
    				t=a[i];
    				a[i]=a[i+1];
    				a[i+1]=t;
    			}
    		}
    		
    		/*每趟循环结束打印一下排序的结果*/
    		printf("第%d趟比较结束：\t",j+1);
    		for(i=0;i<8;i++)
    		{ 
    			printf("%6d",a[i]);
    		}
    		printf("\n");	/*换行*/
    	}
    	
    	/*输出排序后的数据*/
    	printf("排序结束后：\t");
    	for(i=0;i<8;i++)
    	{ 
    		printf("%6d",a[i]);
    	}
    	printf("\n");
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjY2MTQy_size_16_color_FFFFFF_t_70]

## 改进的冒泡排序 ##

思路  
排序过程通过`嵌套for循环`完成，对8个元素的数组，一共进行7趟比较，每趟进行(7-j)次比较，以决出一个最大值

从上面的结果可以看出，在进行到第5趟时，数组已经排序完成，并必须要接着再循环，可以跳出，不用再判断了

#if 0
    改进的冒泡排序（flag判断数据是否发生交换） 
    #endif
    
    #include<stdio.h>
    int main()
    { 
    	int a[8]={ 19,9,87,12,-76,0,-45,123};	/*初始化数组*/
    	int i,j,t;	/*定义循环变量和临时变量*/
    	
    	printf("待排序数组：\t");
    	for(i=0;i<8;i++)
    	{ 
    		printf("%6d",a[i]);	/*宽度为6*/
    	}
    	
    	printf("\n");
    	
    	int flag=0;	/*flag用来判断是否有交换*/
    	for(j=0;j<8-1;j++)
    	{ 
    		for(i=0;i<8-1-j;i++)
    		{ 
    			if(a[i]>a[i+1])
    			{ 
    				t=a[i];
    				a[i]=a[i+1];
    				a[i+1]=t;
    				
    				flag=1;	/*上面的if语句成功执行，则说明数据发生交换*/ 
    			}
    		}
    		
    		if(flag==1)
    		{ 
    			flag=0;	/*若发生交换，则flag赋为0，以便下一次循环判断*/ 
    		}
    		else
    		{ 
    			break;	/*无交换，跳出循环，不再判断*/ 
    		}
    		
    		/*每趟循环结束打印一下排序的结果*/
    		printf("第%d趟比较结束：\t",j+1);
    		for(i=0;i<8;i++)
    		{ 
    			printf("%6d",a[i]);
    		}
    		printf("\n");	/*换行*/
    	} 
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjY2MTQy_size_16_color_FFFFFF_t_70 1]

--------------------

再看查找的题目
    
    假设数组a有10个互不相同且从小到大排列的数，
    从键盘上再输入一个同类型的数x，在数组中查找x，如果找到，输出相应的下标，否则输出“未找到”

# 查找算法 #

## 顺序查找 ##

过程：  
x与数组a中从第一个元素对比，若相等则结束查找；否则继续与第二和元素对比，重复上述过程直到数组的最后一个元素。若数组结束还未找到，则输出“未找到”

**注意！！！：当数据量过大时，查找效率较低**

#if 0
    顺序查找（找到输出下标，否则输出未找到） 
    #endif
    #include<stdio.h>
    int main()
    { 
    	int x,i,a[10]={ 2,3,5,8,12,13,14,16,18,25};
    	
    	printf("输入待查找数据：");
    	scanf("%d",&x);
    	
    	for(i=0;i<10;i++)	/*找到，则结束循环*/
    	{ 
    		if(x==a[i])
    		{ 
    			break;
    		}
    	}
    	if(i==10)	/*不管找不找得到，当遍历整个数组后，必须结束循环*/ 
    	{ 
    		printf("数组中未找到%d\n",x);
    	}
    	else
    	{ 
    		printf("找到了，%d是数组中的第%d个元素\n",x,i+1);
    	}
    }

![在这里插入图片描述][20200517185655584.png]  
![在这里插入图片描述][20200517185813222.png]

## 对半查找 ##

又称**折半查找**或者**二分法**，算法要求待查数组是有序排列的

过程：  
首先比较`x`和`数组a`的`中间元素`，如果相等则查找成功；否则，`若x较小`，则它只可能`在数组a的前半部分`，`反之则在后半部分`，这样每次比较结束，可将搜索范围缩小一半

核心思想：

设下界low=0,上界high=9
    当low<high时循环
    { 
    	计算中间元素下标值：mid=(low+high)/2
    	若x=a[mid],查找成功，结束循环
    	若x<a[mid],则调整上界high=mid-1
    	若x>a[mid],则调整下界low=mid+1
    }

#if 0
    对半查找（找到输出下标，否则输出未找到）
    也称【二分查找】
    
    要求数组是--有序排列 
    #endif
    #include<stdio.h>
    int main()
    { 
    	int x,i,a[10]={ 2,3,5,8,12,13,14,16,18,25};
    	
    	printf("输入待查找数据：");
    	scanf("%d",&x);
    	
    	int low,high,mid,n=0;
    	low=0;		/*设定查找范围*/
    	high=10-1;
    	
    	while(low<=high)
    	{ 
    		n++;	/*记录比较次数*/
    		mid=(low+high)/2;
    		printf("第%d次比较，low=%d,high=%d,mid=%d\n",n,low,high,mid);
    		
    		if(x==a[mid])
    		{ 
    			break;	/*找到，及跳出循环*/
    		}
    		else if(x<a[mid])
    		{ 
    			high=mid-1;	/*到前半部分查找*/
    		}
    		else
    		{ 
    			low=mid+1;	/*到后半部分查找*/
    		}
    	}
    	
    	if(low>high)
    	{ 
    		printf("数组中未找到%d\n",x);
    	}
    	else
    	{ 
    		printf("找到了，%d是数组中第%d个元素\n",x,mid+1);
    	}
    }

![在这里插入图片描述][20200517190657480.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjY2MTQy_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjY2MTQy_size_16_color_FFFFFF_t_70]: /images/20230312/7c9f4560c1e149a29914fd88a9dcbe64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjY2MTQy_size_16_color_FFFFFF_t_70 1]: /images/20230312/51c7f2bd31cf4294b8d05502cb383f1f.png
[20200517185655584.png]: /images/20230312/08d9d8b576cd4b0aa8af077112392914.png
[20200517185813222.png]: /images/20230312/9772ada203974d62a8ca17d805707d4f.png
[20200517190657480.png]: /images/20230312/2baf9e583bbf4892bc374dbe3887f51f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjY2MTQy_size_16_color_FFFFFF_t_70 2]: /images/20230312/d9e71ad2da2b40a2915c2b3e1a55d371.png