/*
输入n个整数和一个正整数k(1<=k<=n)，输出这些整数从小到大排序后的第k个(例如，k=1就是最小值)。n<=10^7.
快速排序的时间复杂度为：最坏情况下：O(n^2),平均情况下：O(nlogn).
查找数组中第k大的元素的平均时间复杂度为：O(n).
*/
#include
#include
#include
#include
#include
using namespace std;
int a[10] = { 2,1,7,9,13,11,20,12 };
void QuickSort(int* a, int low, int high)//将数组a[low...high]从小到大排序
{
if (low < high)
{
int i = low, j = high;
int pivot = a[low];//选取a[low]为基准
while (i < j)
{
while (ipivot) j--;//j从右向左找比pivot小的数
if (i < j) a[i++] = a[j];
while (i < j&&a[i] < a[j]) i++;//i从左向右找比pivot大的数
if (i < j) a[j--] = a[i];
}
a[i] = pivot;//将基准数插到“中间”
QuickSort(a, low, i - 1);//将左边排序
QuickSort(a, i + 1, high);//将右边排序
}
}
int find_kth_smathest(int* a, int low, int high, int k)//在数组a[low...high]中查找第k小的数
{
if (low < high)
{
int i = low, j = high;
int pivot = a[low];
while (i < j)
{
while (ipivot) j--;
if (i < j) a[i++] = a[j];
while(i < j&&a[i] < pivot) i++;
if (i < j) a[j--] = a[i];
}
a[i] = pivot;
if (i - low + 1 == k) return pivot;
else if (i - low + 1 < k) return find_kth_smathest(a, i + 1, high, k - (i - low + 1));
//第k小在右半部分，k变为k-(i-low+1),因为左半部分元素个数为(i-1)-low+1=i-low,还有一个基准元素pivot(a[i])
else return find_kth_smathest(a, low, i - 1, k);//第k小在左半部分，k不变
}
return a[low];//当low=high时，k必然也是1，这使要查询的数组中就一个元素，直接返回就可以了
}
int main()
{
printf("排序之前的数组：\n");
for (int i = 0; i < 8; i++)
printf("%d ", a[i]);
printf("\n");
QuickSort(a, 0, 7);
printf("排序之后的数组：\n");
for (int i = 0; i < 8; i++)
printf("%d ", a[i]);
printf("\n");
/*
for (int k = 1; k < 8; k++)
{
printf("第%d小的元素是%d\n", k, find_kth_smathest(a, 0, 7, k));
printf("查找之后的数组变为:\n");
for (int i = 0; i < 8; i++)
printf("%d ", a[i]);
printf("\n");
}
*/
return 0;
}
