第K小元素问题（C++）

Description

用分治法编程解决在n个数当中找第K小元素问题（注意：不能用排序）。

Input

第一行输入n的值，第二行输入n个数，第三行输入K的值。

Output

n个数中的第K小元素。

Sample Input

5

8 1 3 6 9

3

Sample Output

6

#include <iostream.h>
int a[100];
void swap(int &a,int &b)
{
	int temp=a;
	a=b;
	b=temp;
}
int partition(int a[],int p,int r)
{	int x=a[r];
	int middle=p,j;
	for(j=p;j<r;j++)
	{   if(a[j]<x) 
		{	
			if(j!=middle) 
			{
				swap(a[middle],a[j]);
			}
			middle++; 
		} 
	}
	swap(a[middle],a[j]);
	return middle; 
}
void QuickSort(int a[],int p,int r)
{	if(p<r)
	{	
		int	q=partition(a,p,r); 
		QuickSort(a,p,q-1);
		QuickSort(a,q+1,r);
	} 
} 
int main()
{
	int n,i,k;
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
	}
	cin>>k;
	QuickSort(a,0,n);
	cout<<a[k]<<endl;
	return 0;
}

partition函数和QuitSort函数都来自百度百科快速排序算法的源代码，本文只需理解了快排的核心步骤，将全局数组改变一下即可，结果就是所要的数组。欢迎指正！

------------2018/4/29 更新----------------

经热心网友指出，当年本科在写这段代码的时候，没有认真审题（题目要求不能用排序的方法），但还是要用到快排的思想——快速排序每一次会将一个数位置定好，所以我们就做一个不完整的快速排序步骤。下面请看代码

#include <bits/stdc++.h>
using namespace std;
int quickSort(vector<int> &s, int l, int r)  //运用快排的思想，没有对数组进行全部排序
{  
    if (l < r)  
    {        
        int i = l, j = r, x = s[l];  
        while (i < j)  
        {  
            while(i < j && s[j]>= x)
 		// 从右向左找第一个小于x的数  
                j--;   
            if(i < j)  
                s[i++] = s[j];  
            while(i < j && s[i]< x) 
		// 从左向右找第一个大于等于x的数  
                i++;   
            if(i < j)  
                s[j--] = s[i];  
        }  
        s[i] = x;  
        return i;
    }  
}  

int main(){
	int n,k,i;
	cin>>n;
	vector<int> s(n, 0);
	for(i=0;i<n;i++)
	{
		cin>>s[i];
	}
	cin>>k;
	k = k - 1;
	int l = 0, r = n - 1;
	do{
		i = quickSort(s, l, r);
		if(i < k){
			l = i + 1;
		}
		else if(i > k){
			r = i - 1;
		}
		else{
			break;
		}
	}while(i != k);
	cout<<s[i]<<endl;
	return 0;
}