// The_Least_K_number.cpp : 定义控制台应用程序的入口点。
//数组中第k小的数，例如a[1000]中第250小的数//

#include "stdafx.h"
#include <iostream>
using namespace std;

void swap(int *p, int *q)
{
	int temp = *p;
	*p = *q;
	*q = temp;
}

int patition(int a[], int first, int last)
{
	int key = a[last];
	int i , j;
	i = j = first;
	for (j = first; j < last; j++)
	{
		if (a[j]<=key)
		{
			swap(&a[j],&a[i]);
			i++;
		}
	}
	swap(&a[i],&a[last]);
	return i;
}

void quicksort(int a[], int first, int last)
{
	int k;
	if (first<last)
	{
		k = patition(a,first,last);
		quicksort(a,first,k-1);
		quicksort(a,k+1,last);
	}
}

int find_k_number_index(int a[], int first, int last,int k)
{
	
	int index;
	int m = patition(a,first,last);

	if (m==k)
		index = m;
	else if (m>k)
		index = find_k_number_index(a,first,m-1,k);
	else
		index = m + find_k_number_index(a,m+1,last,k-m-1)+1;

	return index;
	
}

int find_k_number(int a[], int first, int last, int k)
{
	int index = find_k_number_index(a,first,last,k);
	return a[index-1];
}

int _tmain(int argc, _TCHAR* argv[])
{
	int a[100];
	for (int i = 0; i < 100; i++)
	{
		a[i] = i;
	}
	
	
	cout<<find_k_number(a,0,99,98)<<endl;
	quicksort(a,0,99);
	for (int i = 0; i < 100; i++)
	{
		cout<<a[i]<<"\t";
	}
	return 0;
}

求数组中第k小的数，有快速排序的验证