求交集

intersection.c

//answer to google 2011 school interview at zju
int quick_partition(int array[], int start, int end)
{
	int x = array[end];
	int i = start - 1;
	int tmp;
	for (int j=start; j<end; ++j)
	{
		if (array[j]<=x)
		{
			i++;
			tmp = array[j];
			array[j] = array[i];
			array[i] = tmp;
		}
	}
	i++;
	tmp = x;
	array[end] = array[i];
	array[i] = tmp;
	return i;
}

void quick_sort(int array[], int start, int end)
{
	int p;
	if(start < end)
	{
		p = quick_partition(array, start, end);
		quick_sort(array, start, p-1);
		quick_sort(array, p+1, end);
	}
}

int intersection(int dest[], int a[], int alen, int b[], int blen)
{
	int i,j,k;
	//quicksort
	quick_sort(a, 0, alen-1);
	quick_sort(b, 0, blen-1);
	i = j = 0;
	k = 0;
	while (i<alen && j<blen)
	{
		if (a[i] == b[j])
		{
			dest[k++] = a[i];
			i++;
			j++;
		}
		else if (a[i] < b[j])
		{
			i++;
		}
		else
			j++;
	}
	return k;
}