寻找最大的K个数

寻找最大的K个数

最小堆解法

void heap_adjust(int *data, int i,int len)
{
	int lchild = 2 * i;
	int rchild = 2 * i + 1; 
	int max = i; 
	if (i <= len / 2)
	{
		if (lchild <= len && data[lchild - 1]<data[max - 1])
		{
			max = lchild;
		}
		if (rchild <= len && data[rchild - 1]<data[max - 1])
		{
			max = rchild;
		}
		if (max != i)
		{
			swap(data[i - 1], data[max - 1]);
			heap_adjust(data, max, len);
		}
	}
}

void heap_sort_find_k(int *data, int len,int k)
{		
	int *buff = new int[k];
	for (int i = 0; i < k; ++i)
		buff[i] = data[i];

	for (int i = k / 2; i >= 1; --i)
		heap_adjust(buff, i, k);

	for (int i = k; i<len; ++i)
	{
		if (data[i]>buff[0])
		{
			buff[0] = data[i];
			heap_adjust(buff, 1, k);
		}
	}

	for (int i = 0; i < k; ++i)
		printf("%d ", buff[i]);

	printf("\n");

	delete[] buff;
}

快速排序解法

int quick_sort_part(int *data, int left, int right)
{
	if (left >= right)
		return left;

	int mid = left + (right - left) / 2;

	swap(data[mid], data[right]);

	int small_idx = left;

	for (int i = left; i < right; ++i)
	{
		if (data[i] < data[right])
		{
			swap(data[i], data[small_idx]);
			++small_idx;
		}
	}

	swap(data[small_idx], data[right]);

	return small_idx;
}

void quick_sort_find_k(int *data, int len, int k)
{
	int start = 0;
	int end = len - 1;

	int index = quick_sort_part(data, start, end);

	while (index != len - k)
	{
		if (index < len - k)
		{
			start = index + 1;
			index = quick_sort_part(data, start, end);
		}
		else
		{
			end = index - 1;
			index = quick_sort_part(data, start, end);
		}
	}

	for (int i = 0; i < k; ++i)
	{
		printf("%d ", data[len - 1 - i]);
	}
	printf("\n");

}