二分查找

二分查找又称为折半查找，这种查找方法查找速度快，但是要求线性表必须采用顺序存储结构。
下面就以十个整数数组中查找关键数字，并且输出其所在数组的下标。（假设这个数组中关键字只出现过一次）完整代码如下：

#include<stdio.h>
int main(){
int mid,low=1,high=10;
int i,a[10],key;
printf("请输入要查找的数字：");
scanf("%d",&key);
printf("请输入10个整数：");
for(int i=1;i<=10;i++)
scanf("%d",&a[i]);
while(low<=high){
mid=low+(high-low)/2;
if(a[mid]>key)
high=mid;
if(a[mid]<key)
low=mid;
if(a[mid]==key){
printf("%d",mid);
break;
}
}
return 0;
}
//二分查找的实现，先确定每次数组的最高处下标和最低处下标，把关键数与两者中间值下标进行比较，确定新的low和high值
//二分查找算法结束的条件是，low大于high

注意二分查找中有一步是mid=(low+high)/2;这种运算方式如果是在非常的数组中使用，会导致设定的int型mid值溢出而导致程序运行失败，使用mid=low+(high-low)/2;就可尽可能避开这样的问题。文章举的例子非常特殊，真正使用还需要更多的考虑。

冒泡法排序

冒泡法排序名字的由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样。

冒泡法的实现就是从简单的两个数字组合开始进行升序或者降序排序，然后不断加上数组的后一位数字，再对新产生的数组重新进行一次排序，依次类推。

#include<stdio.h>
int main()//冒泡法升序排序 
{
	int a[10]={3,46,8,22,6,43,1,23,9,12};
	int i,j,t;
	for(i=0;i<10;i++)
	for(j=0;j<9-i;j++)
	{
		if(a[j+1]<a[j])
		{
		t=a[j+1];
		a[j+1]=a[j];
		a[j]=t;
		}
	}
	for(i=0;i<=10;i++)
	printf("%d  ",a[i]); 
	return 0;
}

快速排序 <快排>

快速排序是冒泡法排序的改进。快速排序的第一趟排序是把数据分成独立分割的两部分，然后再分别对两部分的数据再进行快速排序。换个说法，快排就是先选择一个数组中的一个数字，然后创建左右两个指向从左右两边尽头开始，依次加一向中间靠拢，如果在左边找到一个需要交换到右边的数，在右边找到一个需要交换到左边的数，就进行数字的左右交换。当左右两边指向重合结束第一趟循环，再单独对左右两边的数进行以上操作，直到左指向指向右指向初始，右指向指向左指向的初始。

当然快速排序的具体实现还有其他大同小异的算法思想，有想法的可以补充在评论区。

 #include<stdio.h>
int a[10];//把数组作为全局变量 
void sort(int l,int r)
{
	int temp,mid,j,i;
	j=l;	i=r;
	mid=a[(j+i)/2];//选择中间的某个值是用来比较的关键数据 
	do{
		while(mid>a[j])		j++;//找到中间数值左边第一个比关键数字大的数 
		while(mid<a[i])		i--;//找到中间数值右边第一个比关键数字小的数 
		if(j<=i){       //如果数组下标还符合则把两数进行交换 
			temp=a[i];
			a[i]=a[j];
			a[j]=temp;
			j++;i--;//左右两边都向中间靠拢，直到两者数值重合 
		}
	}while(j<=i);//当左右两边的指向重合的时候结束循环 
	if(j<r) 	sort(j,r);//对关键数字的左边数列进行排序 
	if(i>l)		sort(l,i);//对关键数字的右边数列进行排序 
}
int main()
{
	int i;
	printf("请输入十个正整数：");
	for(i=1;i<=10;i++)
	scanf("%d",&a[i]);
	sort(1,10);
	for(i=1;i<=10;i++)
	printf("%d ",a[i]); 
	return 0;
}

选择排序

选择法排序有点类似于冒泡法排序，都是进行了n-1次排序。先初始最小值下标位置，通过选择数组内最小或者最大的数来进行交换，最终实现升序或降序排序。

#include<stdio.h>
int main()//选择法排序的升序排序
{
	int min,j,i,n;
	int t;
	int a[]={3,46,8,22,6,43,1,23,9,12}; 
	n=sizeof(a)/sizeof(a[0]);//计算数组的长度 
	for(i=0;i<n-1;i++)       //外循环 
	{
		min=i;              //初始最小的值下标
		for(j=i+1;j<n;j++)   //内循环实现选择一定数组中大的或者是小的数放在最左边i的位置上 
		{
			if(a[min]>a[j])
			min=j;
		}
		if(min!=i)//判断i和最小值的下标是否相同 ，不同则交换两个数 
		{
			t=a[min];
			a[min]=a[i];
			a[i]=t;
		}
	}
	for(i=0;i<10;i++)
	printf("%d ",a[i]);
	return 0;
}

归并法排序

归并法排序是分治思想的典范，首先将n个元素分为含n/2个元素的子序列，使用归并排序法实现子序列的递归排序，可以把整个原序列分为n个子序列，最后合并两个排好序的序列。

#include<stdio.h>
#include<stdlib.h>
void merge(int a[],int low,int mid,int high)
{
	int *tmp=(int*)malloc((high-low+1)*sizeof(int));
	int left_low=low;//左边序列的起始点 
	int left_high=mid;//左边序列的终点 
	int right_low=mid+1;//右边序列的起始点 
	int right_high=high;//右边序列的终点 
	int k,i;
	//两个部分的数据依次比较大小，“合” 
	for(k=0;left_low<=left_high &&right_low<=right_high;k++){
	if(a[left_low]<=a[right_low])
	{
	tmp[k]=a[left_low++];
    }
	else
	{
	tmp[k]=a[right_low++];
    }
    }
    //判断左右两侧数据是否有剩余，如果有，则直接复制粘贴在排列好的数组后面 
	if(left_low<=left_high)//左边序列有剩余 
	{
	for(i=left_low;i<=left_high;i++)
	tmp[k++]=a[i];
   }
	if(right_low<=right_high)//右边序列有剩余 
	{
		for(i=right_low;i<=right_high;i++)
		tmp[k++]=a[i];
	}
	for(i=0;i<high-low+1;i++)//把排序好的序列重新放回原数组中 
	a[low+i]=tmp[i];
	free(tmp);
	return ;
}
void mergesort(int a[],unsigned int first,unsigned int last)
{
	int mid;
	if(first<last)//把数据不断对半分，大致是“分”的思想 
	{
		mid=(first+last)/2;
		mergesort(a,first,mid);
		mergesort(a,mid+1,last);
		merge(a,first,mid,last);
	}
	return;
}
int main()
{
	int i;
	int a[10]={3,46,8,22,6,43,1,23,9,12}; 
	mergesort(a,0,9);
	for(i=0;i<10;i++)
	printf("%d ",a[i]);
	return 0;
 }