# Divide and conquer strategy -- find the k-th smallest element in the array

2022-04-29 04:47:06

#include <stdio.h>

/* First, we give a partition function （ Quick sort Division ）*/
int partition(int* ar, int left, int right)
{

int i = left;
int j = right;
int tmp = ar[i];
while (i < j)
{

while (i<j && ar[j] > tmp)
{

j--;
}
if (i < j) ar[i] = ar[j];
while (i < j && ar[i] <= tmp)
{

i++;
}
if (i < j) ar[j] = ar[i];
}
ar[i] = tmp;
return i;
}
// recursive
int Selectk(int* ar, int left, int right, int k)
{

if (left == right && k == 1)
{

return ar[left];
}
int index = partition(ar, left, right);//index Is the physical subscript
int pos = index - left + 1;//pos Is to combine the physical subscript with the k Element position correspondence
if (k <= pos) return Selectk(ar, left, index, k);
else
{

return Selectk(ar, index + 1, right, k - pos);// When looking in the right part , Pay attention to the original article k The element will become k-pos
}
}

int Select_k_Min(int* ar, int n, int k)
{

if (ar == NULL || n < 1 || k<0 || k>n) return -1;
return Selectk(ar, 0, n-1, k);
}

int main()
{

int num,i,k;
scanf("%d %d", &num,&k);
int a[num];
for(i=0;i<num;i++)
scanf("%d",&a[i]);
printf(" The first %d The small element is %d",k,Select_k_Min(a,num,k));
return 0;
}
/********** End **********/