C++求无序序列中第k小的元素
 
利用优先队列（priority_queue）求出一个无序整数列中第k小的元素
 先输入序列长度
 再输入该整数列
 最后输入第k小元素位置 k
 
实验例子：
 5 //序列长度
 2 4 3 6 5 //该整数列
 2 //第k小元素位置
 3 //输出结果
 
代码如下
 
#include<queue>
#include<iostream>

using namespace std;
int thk(int *a,int n,int k){
	int i,j=0;
	priority_queue<int,vector<int>,greater<int> > pq;
	for(i=0;i<n;i++){
		pq.push(a[i]);
	}
	for(i=1;i<=k;i++){
		j=pq.top();
		pq.pop();
	}
	return j;
} 
int main(){
	int x;		//输入的整数个数
	cin>>x;		//输入x
	int *a=new int[x];
	for(int i=0;i<x;i++){	//输入a[x]
		cin>>a[i];
	}
	int y;		//需要输出的第k=y大的数
	cin>>y;	
	int n=x;
	for(int k=1;k<=n;k++){
		if(k==y){
			cout<<thk(a,n,k);	
			break;
		}
		else continue;
	
	}
	return 0;
}

寻找一个无序序列中第k小的元素
 
【问题求解】假设无序序列存放在a[0...n-1]中，若将a递增排序，则第k小的元素为a[k-1]。采用类似快速排序的思想。
 
源代码如下：
 
#include <iostream>
using namespace std;


//寻找一个序列中第k小的元素
//运用快速排序和二分查找相结合的方法进行查找
int SearchK(int a[],int low,int high,int k) {
	//这里是利用快速排序的原理
	int i = low, j = high;
	int tmp;
	if (low==high&&low==k-1){              //递归出口，区间内只有一个元素且为a[k-1]
		return a[k - 1];
	}else if(low < high){                 //区间至少存在两种元素的情况
		tmp = a[low];                    //选取区间的第一个元素作为基准
		while (i!=j) {                       //从区间的两端交替向中间扫描，直到i=j为止
			while (j>i&&a[j]>=tmp) {           
				j--;                               //从右向左扫描，找第一个关键字小于tmp的a[j]
			}
			a[i] = a[j];                         //将a[j]前移到a[i]的位置
			while (i<j&&a[i]<=tmp) {
				i++;                               //从左向右扫描，找第一个关键字大于tmp的a[i]
			}
			a[j] = a[i];                       //将a[i]后移到a[j]的位置
		}
		a[i] = tmp;


		//这里是利用二分查找的原理
		if (k-1==i) {
			return a[i];
		}
		else if (k-1<i) {
			SearchK(a, low, i - 1, k);             //在左区间中递归查找
		}
		else {
			SearchK(a, i+1,high, k);              //在右区间中递归查找
		}
	}
}


int main() {
	int n = 0;
	cout << "请输入数组元素的个数：" << endl;
	cin >> n;
	int *a = new int[n];
	cout << "请输入数组元素" << endl;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cout << "请输入要查找的第k小的元素的序号" << endl;
	int k = 0;                                            //输入k
	cin >> k;
	int y=SearchK(a, 0, n - 1, k);
	cout << "第" << k << "小的元素为：" << y << endl;

	system("pause");
	return 0;
}
 
输出：
 
请输入数组元素的个数：
 9
 请输入数组元素
 9 6 3 8 5 2 7 4 1
 请输入要查找的第k小的元素的序号
 5
 第5小的元素为：5
 请按任意键继续. . .
  

       在一个无序的序列中，要查找第i小的元素最简单的方法就是将所有元素排序，就可以直接找到地i小的元素，然而比较排序算法最快也只能是O(nlogn)，比如堆排序、归并排序、快速排序。这里研究了只要时间复杂度为O(n)的算法。
 
       利用快速排序算法中的枢轴元素，即枢轴元素的左边全是小于等于它的元素，枢轴元素的右边全是大于等于它的元素，则枢轴元素的位置k就是它在序列中第k小的元素，然后用k和要查找的i比较判断即可。这里用到了分治算法，每次递归调用都可以排除掉部分元素：枢轴元素的全部左部分元素或枢轴元素的全部右部分元素。这样使时间复杂度降低到了O(n)。
 

#include <stdio.h>

int Partition(int A[], int low, int high);

int Find_imin(int A[], int length, int i);
int Findi(int A[], int low, int high, int i);

int main(int argc, char *argv[])
{
  int i = 0;   
  int imin = 0; 
  int A[] = {5, 2, 4, 6, 1, 3, 9, 10, 8, 7};
  int length = sizeof(A) / sizeof(A[0]);
  imin = 7;
  int result = Find_imin(A, length, imin); 
  printf("the %d min elements is %d\n", imin, result);
  
  for(i=0; i < length; i++)
  {
        printf("%d  ", A[i]);
  }
  
  printf("\n");
  
  printf("Press enter to continue ...");
  getchar();	
  return 0;

}


int Find_imin(int A[], int length, int i)
{ 
    return Findi(A, 0, length-1, i);
}

//在(low~high)范围内查找第i小元素 
int Findi(int A[], int low, int high, int i)
{
    //当范围缩小到只有一个元素时，就是这个元素 
    if(low == high)
    {
        return A[low];
    }
    else if(low < high)
    {
        //选取一个枢轴元素，求取它在排序后的数组中的位置 
        int pivot = Partition(A, low, high);
        
        int k = pivot - low + 1; //求取枢轴元素在(low~high)范围内是第几小元素 
        
        if( i == k )  //所要找的第i小元素正好是枢轴元素 
        {
            return A[pivot];
        }
        else if( i < k ) //第i小元素小于枢轴元素，应在左部分继续递归查找 
        {
            return Findi(A, low, pivot-1, i);
        }
        else  //第i小元素大于枢轴元素 ，应在右部分继续递归查找，这时要更新i 
        {
            return Findi(A, pivot+1, high, i-k);
        }
    }
    else 
        return -1;
}

int Partition(int A[], int low, int high)
{
    int pivotvalue = A[low];
    
    while(low < high)
    {
        while( (low < high) && (A[high] >= pivotvalue) )
        {
            high--;
        }
        A[low] = A[high];
        
        while( (low < high) && (A[low] <= pivotvalue) )
        {
            low++;
        }
        A[high] = A[low];
    }
    A[low] = pivotvalue;
    return low;
}
 

  

package com.xhu.edu.utils;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class DButil {
	public static void main(String[] args) {
		List<Integer> a=new ArrayList<Integer>();
		Random random=new Random();
		Set<Integer> set=new LinkedHashSet<Integer>(a);
		while(set.size()<12){
			set.add(random.nextInt(12)+1);
		}
		Iterator<Integer> iterator;
		iterator=set.iterator();
		while(iterator.hasNext()){
			System.out.println(iterator.next());
		}
		System.out.println(set.toString());
	}
}