查找数组中第K大的数，使用快排（可能是最易懂的写法）

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列从小到大排序后的第k个数。

下面给出代码并讲解：

#include <iostream>
#define swap(a,b) {int temp=a;a=b,b=temp;}

using namespace std;


int partition(int* a, int left, int right)//快排中最核心的步骤，把数组中最右边的数作为分割点进行分割，每次分割返回值i为当前第i-left+1大的数
{
 int i = left;
 int  j;
 for (j = left; j < right; j++)
 {
  if (a[j] > a[right])
  {
   swap(a[j], a[i]);
   i++;
  }
 }
 swap(a[i], a[right]);
 return i;
}

void quick_sort(int* a, int left, int right)//此处用不到这个函数，此函数为了说明标准快排写法
{
 if (left < right)
 {
  int k = partition(a, left, right);
  quick_sort(a, left, k - 1);
  quick_sort(a, k + 1, right);
 }
 return;
}

int find_k(int* a, int left, int right, int k)//找到第K大的数
{
 int find=partition(a, left, right);//首先进行一次排序，找到第find-left+1大的数
 if (find-left+1 == k) return a[find];//如果刚好是第K大，则返回
 if (find-left+1 < k)//如果找到的数比K小，则说明第K大的数在该数右边，去右边找第k-find+left-1大的数
 {
  find_k(a, find+1, right, k-find+left-1);
 }
 if (find-left+1 > k)//如果找到的数比K大，则说明第K大的数在该数左边，去左边找第k大的数
 {
  find_k(a, left, find - 1,  k);
 }
}

int main()
{
 int a[10] = { 10,9,8,7,6,5,4,1,2,3 };
 int k=find_k(a, 0, 9,1);
 cout << k << endl;
}