C语言 数组的查找和排序方法 1.顺序查找 2.二分查找; 1.(简单)选择排序法 2.冒泡排序法 3.(直接)插入排序法

文章目录

  • 数组的定义和初始化
  • 查找
    • 1.顺序查找
    • 2.二分查找
  • 排序方法
    • 1.(简单)选择排序法
    • 2.冒泡排序法
    • 3.(直接)插入排序法
  • 二维数组的查找方法(《剑指offer》题目)
  • 指针和一维数组

数组的定义和初始化

   数组在定义是要注意:
  1.数组同变量一样,需要先定义后才能使用
  2.定义数组时,[ ]内不能用变量表示元素个数(在引用时可以,如for内初始化数组),也不能用实数表示元素个数

  一维数组初始化要注意,{ }只能在数组定义的同时使用。数组不初始化,里面的数据将会是随机数
  正确示范:

	/*正确示范1*/
	int a[5];
	a[0]=0;
	a[1]=1;
	a[2]=2;
	a[3]=3;
	a[4]=4;
	/*正确示范2*/
	int a[5]={0, 1, 2, 3, 4};	/*也可以写成下面这样*/
	int a[]={0, 1, 2, 3, 4};	/*只有在给数组全部元素赋初值时可以省略[ ]内的数组元素个数*/
	/*正确示范3*/
	int a[5]={};	/*数组a全部元素被初始化为0*/
	int a[5]={0};	/*数组a全部元素被初始化为0*/

  错误示范:

	/*错误示范1*/
	int a[5]=[0, 1, 2, 3, 4];	/*赋初值应用{ }括起来*/
	int a[5]={0, 1, 2, 3, 4};	/*应写成这样*/
	/*错误示范2*/
	int a[5];
	a={0, 1, 2, 3, 4};	/*{ }只能在定义的同时使用*/
	/*错误示范3*/
	int a[5]=1;		/*赋初值应用{ }括起来*/
	int a[5]={1};	/*应该写成这样,这样写只有a[0]值为1,a[1]-a[4]全为0*/

  
  

查找

1.顺序查找

  查找数组a有没有值为25的元素

#include 
main()
{
	int a[10]={1, 0, 24, 30, 5, 9, 30, 25, 55, 49};
	int i, j;
	for(i=0; i<10; i++)
		if(a[i]==25)	/*注意不要写成=,否则就是赋值了*/
			break;
	if(i>9)
		printf("没找到25");
	else
		printf("25的下标为%d", i);	

	return 0;
}

  
  

2.二分查找

  二分查找又称对分查找、折半查找。要使用二分查找有一个前提:数组中的数据必须由大到小或者小到大的有序顺序排列。

#include 
#include 
int main()
{
    /*值为25的元素下标为10,即第11个*/
    int array[]={0, 1, 3, 6, 9, 14, 18, 22, 23, 24, 25, 28, 30, 33, 38, 44, 50};
    int low=0,high=sizeof(array)/sizeof(array[0]);	/*high初始值为数组长度*/
    int mid=0;
    int target=25;

    while(low<=high)
    {
		mid=(low+high)/2;
		if(array[mid]<target)
			low=mid+1;		/*为什么不是low=mid,因为上一行已经排除mid,进一步缩小范围,更容易找到目标*/
		else if(array[mid]>target)
			high=mid-1;
		else
			break;		/*在找到array[mid]==target或者low>high时退出循环*/
	}
	if(low>high)
		printf("没找到25");
	else
		printf("找到了,下标是%d", mid);
		
    return 0;
}

  
  

排序方法

1.(简单)选择排序法

  找到元素最小值/最大值,把它放在数组头,接着找剩下元素里的最值,把它放在上次找到的最值后面,直到最后一个元素。
  方法一:始终保持a[i]是一个更小值,直到它为剩下元素里值最小

#include 
#include 
#include 
/*选择排序实例1*/
/*选择排序,要求:小的在前大的在后*/
int main()
{
	int a[100]={};
	int i, j, t;
	int n=sizeof(a)/sizeof(a[0]);	/*数组长度*/

	/*设置随机数种子*/
	srand(time(NULL));
	/*数组a的元素为随机的三位数*/
	for(i=0; i<n; i++)
		a[i]=rand()%1000;

	/*选择排序*/
	for(i=0; i<n-1; i++)
	{
		for(j=i+1; j<n; j++)
			if(a[j]<a[i])
				t=a[i], a[i]=a[j], a[j]=t;
	}

	/*打印数组*/
	for(i=0; i<n; i++)
		printf("%d ", a[i]);

	return 0;
}

  
  方法二:找到最小值的下标,然后和a[i]交换,使最小值位于前头

#include 
#include 
#include 
/*选择排序实例2*/
/*选择排序,要求:小的在前大的在后*/
int main()
{
	int a[100]={};
	int i, j, k, t;
	int n=sizeof(a)/sizeof(a[0]);	/*数组长度*/

	/*设置随机数种子*/
	srand(time(NULL));
	/*数组a的元素为随机的三位数*/
	for(i=0; i<n; i++)
		a[i]=rand()%1000;
	
	/*选择排序*/
	for(i=0; i<n-1; i++)	/*i比j小1,所以i范围是0~n-1*/
	{
		k=i;	/*最小值下标*/
		for(j=i+1; j<n; j++)
			if(a[j]<a[k])	/*因为k是j的变化值,只有在第0次循环时才是a[i]和a[j]比*/
				k=j;		/*后面碰到a[j]比a[i]小的值,a[i]就会被换掉,再后面就是a[j]和a[j]之间比了*/
		t=a[i], a[i]=a[k], a[k]=t;
	}

	/*打印数组*/
	for(i=0; i<n; i++)
		printf("%d ", a[i]);

	return 0;
}

  
  

2.冒泡排序法

  冒泡排序,顾名思义,元素会像水里的泡泡一样,从底部一直上升到顶部,即前后元素相比较,大值元素被安排到数组尾部,小值元素在交换的时候自然而然的会排在头部。

#include 
#include 
#include 

/*冒泡排序,要求:小的在前大的在后*/
int main()
{
	int a[100]={};
	int i, j, t;
	int n=sizeof(a)/sizeof(a[0]);	/*数组长度*/

	/*设置随机数种子*/
	srand(time(NULL));
	/*数组a的元素为随机的三位数*/
	for(i=0; i<n; i++)
		a[i]=rand()%1000;	
	
	/*冒泡排序*/
	for(i=0; i<n-1; i++)		/*冒泡次数为n-1次*/
		for(j=0; j<n-1-i; j++)	/*a[j]要和a[j+1]比较,所以范围是0~n-1,由于每冒泡一次,下一个元素的比较次数就会-1*/
			if(a[j+1]<a[j])
				t=a[j], a[j]=a[j+1], a[j+1]=t;
	

	/*打印数组*/
	for(i=0; i<n; i++)
		printf("%d ", a[i]);
		
	return 0;
}

  
  

3.(直接)插入排序法

  跟打扑克牌时差不多,把选中元素插入到有序序列合适的位置中。

#include 
#include 
#include 

/*插入排序,要求:小的在前大的在后*/
int main()
{
	int a[100]={};
	int i, j, k, data;
	int n=sizeof(a)/sizeof(a[0]);	/*数组长度*/

	/*设置随机数种子*/
	srand(time(NULL));
	/*数组a的元素为随机的三位数*/
	for(i=0; i<n; i++)
		a[i]=rand()%1000;	
	
	/*插入排序*/
	for(i=1; i<n; i++)		/*只有一个元素的序列就是排列好的了,所以从第二个开始*/
	{
		data=a[i];
		for(j=0; j<i; j++)	/*遍历序列,找到合适的下标k*/
			if(a[j]>data)	/*因为序列有序,所以元素都是从小到大排放大*/
				break;
		k=j;
		for(j=i; j>k; j--)	/*后续元素后退一个,方便插入元素*/
			a[j]=a[j-1];
		a[k]=data;
	}
	

	/*打印数组*/
	for(i=0; i<n; i++)
		printf("%d ", a[i]);
		
	return 0;
}

  
  

二维数组的查找方法(《剑指offer》题目)

  关于二维数组的二分查找、暴力搜索查找、线性查找(剑指offer题目,右上角解法),可以查看这篇文章:C语言 二维数组的查找方法(←点击查看原文)

  
  

指针和一维数组

  指针就是地址(一种只能存放地址的数据类型),关于指针可以看看我写的另一篇文章~指针详解、指针和一维数组、实例(←点击查看原文)

你可能感兴趣的