DSOJ Kth Number（第k大的數）

題目連結

#include<stdio.h>		//查找數組中第k小的元素
#define MAX 100
/*
算法思想：
模仿快排的做法，首先去數組中任何一個元素（不妨取第一個），将數組分為兩部分，s[0,..p-1],和s[p+1,...n-1],
其中左半部分的值都不大于s[p]，右半部分的值都不小于s[p]

此時如果p==k-1,則說明s[p]即為所要找的第k小的元素，傳回s[p]
否則，如果p>k-1，說明第k小的元素一定在s[0,...p-1]中則再在s[0,....,p-1]中查找
否則，說明第k小的元素在s[p+1,...,n-1]中，而且是s[p+1,...,n-1]中第k-p-1小的元素

綜上，利用遞歸即可實作
*/

int FindKth(int *Array, int n, int k)
{
	int left, right, pivot;
	left = 0;
	right = n - 1;
	pivot = Array[0];				//選取第一個數組元素作為軸值
	while (left < right)
	{
		while (left < right&&Array[right] >= pivot)
			right--;
		Array[left] = Array[right];
		while (left < right&&Array[left] <= pivot)
			left++;
		Array[right] = Array[left];
	}
	Array[left] = pivot;			//left即為軸值所在的位置
	if (left == k - 1)
		return Array[left];
	else if (left>k - 1)
		return FindKth(Array, left, k);
	else
		return FindKth(Array + left + 1, n - left - 1, k - left - 1);
}

int main()
{
	int Array[MAX];
	int k, n, i;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", Array + i);
	scanf("%d", &k);
	printf("%d\n", FindKth(Array, n, k));
	return 0;
}