The-ith-Element

Brief: the-ith-element,given a array A with n element , return the i-th element of A.  A(n,i)

this problem can be solved using quick-sort idear, every time we choose a pivot ,after rearrangement, we know the pivot is the i-th element of A, so we can fixed this problem as the follow action.

i) choose  pivot, rearrangement array, get the pivot index of j;

ii) if j > i , then recursion the 1-th partition , A(1-th , i);

iii)if j < i, then recursion the 2-th partition, A(2-th, i-j);

int element(int *array, int left, int right, int index)
{
if(left >= right)
return array[left];
int pivot = array[left];
int i=0, j = 0; for(i=left+1,j = left+1; j <=right; ++j)
{
if(array[j] < pivot)
swap(array[i++], array[j]);
}
swap(array[left], array[i-1]); //pivot is the (i-left)-th element, and pivot's index is i-1 if(index == i-left)
return array[i-1];
else if(index < i-left)
return element(array, left, i-2, index);
else
return element(array, i,right, index-i+left);
}

  

上一篇:361189-66-4,Azido-PEG6-acid,N3-PEG6-acid,Azide-PEG6-COOH小分子叠氮化物


下一篇:Android系统编程入门系列之硬件交互——通信硬件Bluetooth