本文共 2539 字，大约阅读时间需要 8 分钟。

这个问题就是求无序数组中的第K小的问题方法一：直接冒泡K次，第一次得到第一小的，第K次得到第K小的方法二：对数组进行预排序方法三：二分快查方法四：分组二分快查

注：这里的代码只经过自己构造的数据检验，如果有误，敬请谅解！！！

方法一：直接冒泡K次

对于这个算法，可以发现，当数组规模为 n 时，如果要求的是第 1 小或者是第 n 小（第1大）那么问题相对来说会简单一点，因为只要进行一次冒泡就行了，但是当求第 n / 2 的问题时，相对而言工作量会是最大的，而对于第 k 小，如果第 n - k 大的工作量比原来小，那么应该采取工作量相对来说小的方案来进行，所以定义两个函数void get_k_small(int n, int k, int * a){   	int i;	while(k)	{   		for(i = 0; i < n - 1; ++i)		{   			if(a[i] < a[i + 1])			{   				swap(a[i], a[i + 1]);			}		}		--n;		--k;	}	cout << a[n];}void get_k_big(int n, int k, int * a){   	int i;	while(k)	{   		for(i = 0; i < n - 1; ++i)		{   			if(a[i] > a[i + 1])			{   				swap(a[i], a[i + 1]);			}		}		--n;		--k;	}	cout << a[n];}	分别是求第 K 小和第 K 大的代码，主函数中只需要根据 K 和 K的补 那个相对而言工作量少来做选择就行了

方案二：预排序

如果对于 k = n / 2 的情况，那么方案一的代码就需要【(n - 1) + (n - 2) + --- + (n - n / 2)】 = O(n ^ 2)，时间复杂度相对于传统的排序（默认为 n * log n 的排序算法）就会相对而言较高，所以这个时候可以选择先对数据进行预排序，最后直接输出 a[k - 1] 即可（下标并不一定是这个，要按照你自己的排序算法灵活掌握）	由于排序算法相对来说较为基础，这里就不再添加代码了

方案三：二分快查

对于这个算法来说，其实也是使用二分排序的思维，先随机选取一个位置上的数，将他交换到第一个（为了尽量避免一个元素始终不动的情况），然后按照二分排序的算法将这个元素放到他对应大小的位置上，如果这个位置刚刚好是 K ，那么直接返回该元素即可，如果这个元素大于 K，那么对左边再进行二分快查找到第 K 小的元素，如果该位置小于 K，那么就向右查找第 K - 该位置 小的元素查找函数：int Potion(int * a, int l, int r) // 原地分区算法  {   	int x = a[l];	int m = l, mid = l;	// m 指向中轴	for(int i = l + 1; i <= r; ++i)	{   		if(a[i] < x)		{   			if(m == mid)	// 由于在移动的时候总是会出现开始元素移动的现象，所以用 mid 专门保存这一元素位置			{   				mid = i;			}			else if(i == mid)			{   				mid = m;			}			swap(a[i], a[m]);			++m;		}	}	swap(a[mid], a[m]);	return m;}	这里返回的 m 就是该元素对应的位置的下标，如果要找第 K 个元素，那么要将 K - 1 作为目标值的下标。所以在主函数里可以这么调用（略去数组的输入）int main(){   	int m = -1, l = 0, r = n - 1;	while(m != k - 1)	{   		m = Potion(a,l, r);		if(k - 1 < m)		{   			r = m - 1;		}		else if(m < k - 1)		{   			l = m + 1;		}	}	cout << a[m];	return 0;}	这个代码在制作的时候，我专注于去右边找第 K - 该位置 小的元素，结果发现下标总是会出现问题，最后如果是个有序序列的话，总是会指向第一个，由此想到，为什么一定要去右边找第 K - 该位置 小的数呢？所以这个代码的思路是这样的	如果该位置小于 K，那就去右边找 K，如果该位置大于 K，那么就去左边找 K，这是迭代的思维，或许上面的那种去右边找第 K - 该位置 小的这种思维该写成递归函数，而不是这种迭代的方式，事实证明，也的确如此递归代码：void get(int * a, int n, int k){   	int m = Potion(a, 0, n - 1);	if(m == k - 1)	{   		cout << a[m] << endl;		return ;	}	else if(k - 1 < m)	{   		get(a, m, k);	}	else	{   		get(&a[m + 1], n - m - 1, k - 1 - m);	}}

方案四：分组找分界点

对于方案三，有可能会出现所有元素都不动的情况，这时的二分时间复杂度就是O(n ^ 2)，为了尽量避免这种情况，我们对二分查找的算法进行了优化，就是先采取 C （C为常数）个一组选出最中间元素，然后将这些元素放到数组的首，再选取这些元素里面的最中间元素，以此元素为划分元素，进行二分查找，这样的话，每一次都能保证排序后的两边都是容量相当的小的数组，这样的话二分查找（方案三）的速度就会相对来说达到最优了，同时也避免了元素位置不动的最坏情况，这样的话，最坏也不过分成 0.75n 和 0.25n 两部分。	这个方法的代码的话，和方案三大致类似，只需要在调用Potion()函数的时候将我们选出来的元素放到 a[l] 就可以了，需要额外再定义一个排序返回中间元素下标的函数就可以了。

原理图示：

转载地址：http://bbeoz.baihongyu.com/