signed

QiShunwang

“诚信为本、客户至上”

一维数组的常用基本操作操作

2021/3/21 12:02:53   来源:

本博文以数组存储整型变量为例

目录

逆置

排序(升序)

冒泡排序法

选择排序法

去重(删除重复数据)

无序

有序

 有序数组的归并

本地归并(数据覆盖原有数组)

异地归并(数据存放到新数组里)

交集(本地) 

逆置

对于数组逆置最常见的方法便是,定义一个变量temp作为载体,定义两个变量i,j分别从头/尾遍历,交换两个数组。已知数组a和数组规模n。

void Reverse(int* a, int n)
{
	int i, j, temp;
	for (i = 0, j = n - 1; i < j; i++, j--)
	{
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

在不定义新变量temp的情况下,也可以通过对两个数组进行相加相减操作,达到数据交换的效果(可以节省一个变量的空间,但是现在的计算机已经可以无视多一个变量的空间了)

void Reverse(int* a, int n)
{
	int i, j;
	for (i = 0, j = n - 1; i < j; i++, j--)
	{
		a[i] = a[i] + a[j];
		a[j] = a[i] - a[j];
		a[i] = a[i] - a[j];
	}
}

排序(升序)

比较常见的排序法有冒泡排序法和选择排序法,两者排序所用的时间空间一致

冒泡排序法

通过双重排序进行n次遍历,每次排序的过程中大的数据都会向后移动(即冒泡),每次遍历完最大的都会排在最后

void sortdata(int* a, int n)
{
	int i, j, min;
	for (i = 0; i < n - 1; i++)
	{
		for (j = 0; j < n - 1 - i; j++)
			if (a[j + 1] < a[j])
			{
				a[j + 1] = a[j + 1] + a[j];
				a[j] = a[j + 1] - a[j];
				a[j + 1] = a[j + 1] - a[j];
			}

	}
}

选择排序法

通过双重排序进行n次遍历,每遍历完一次都能选出最小的数据进行交换

void sortdata(int* a, int n)
{
	int i, j, min;
	for (i = 0; i < n - 1; i++)
	{
		min = i;
		for (j = i+1; j < n; j++)
			if (a[j] < a[min])
				min = j;
		if (min != i)
		{
			a[i] = a[i] + a[min];
			a[min] = a[i] - a[min];
			a[i] = a[i] - a[min];
		}

	}
}

去重(删除重复数据)

比较暴力的方法就是每次遍历删除,删除的数据全部都得前置一位,十分占用运行时间。

无序

现在我们将数组分为两部分,左边部分为进行比较过没有重复的数据,右边部分为还未进行比较的数据,将右边的数据分别与左边的所有数据进行比较,若没有数据相同则将该数据移动到左边数据的下一个,成为左边数据的一员,这样将节省大量的数据比对时间(返回的k为去重后的数据规模)

int delrepeat(int* a, int n)
{
	int i,k,j;
	for(i=1,k=1;i<n;i++)
	{
		for(j=0;j<k;j++)
		{
			if(a[i]==a[j])
				break;
		}
		if(j>=k)
		{
			a[k]=a[i];
			k++;
		}
	}
	return k;
}

有序

经过排列的数组在比较时十分方便,这样就不需要将右边的数据去对比左边的所有数据了,只需要跟左边最后一个数据比较就行。

int delrepeat(int* a, int n)
{
	int i, k;
	for (i = 1, k = 1; i < n; i++) 
	{ 
		if (a[i] != a[k - 1]) 
		{ 
			a[k] = a[i];
			k++; 
		} 
	}  
	return k;
}

 有序数组的归并

即求两个数组的并集

本地归并(数据覆盖原有数组)

int Merge(int* a, int* b, int m, int n)
{  
	int i,j,k;  
	for (i = 0, j = 0; i < m && j < n;)
	{
		if (a[i] < b[j])
			i++;
		else if (a[i] > b[j])
		{
			for (k = m - 1; k >= i; k--)
			a[i] = b[j];
			i++;
			j++;
			m++;
		}
		else
		{
			i++;
			j++;
		}
	}	  
	while(j<n)  
	{   
		a[m]=b[j];   
		j++;   
		m++;  
	}  
	return m;  
}

异地归并(数据存放到新数组里)

int Merge(int* a, int* b, int* c, int m, int n)
{
	int i, j, k;  
	for (i = 0, j = 0, k = 0; i < m && j < n;)
	{
		if (a[i] < b[j]) 
		{ 
			c[k] = a[i];    
			i++;    
			k++; 
		}
		else if (a[i] > b[j]) 
		{ 
			c[k] = b[j];    
			j++;    
			k++; 
		}
		else 
		{ 
			c[k] = a[i];    
			i++;    
			j++;    
			k++; 
		}
	}
	while (i < m) 
	{ 
		c[k] = a[i];   
		i++;  
		k++; 
	}
	while (j < n) 
	{
		c[k] = b[j];   
		j++;  
		k++;
	}  
	return k;
}

交集(本地) 

int common(int* a, int* b, int m, int n)
{
	int i, j, k;
	for (i = 0, j = 0, k = 0; i < m && j < n;)
	{
		if (a[i] < b[j])    
			i++;   
		else if (a[i] > b[j])    
			j++;
		else 
		{
			a[k] = a[i]; 
			k++;    
			i++;    
			j++;
		}
	}  
	return k;
}