int partition(const int * na, int low, int hight);
int new_qsort(const int * na, int low, int high, int nNeed);
/**
* find the k-th biggest element in a integer array, using a
* modified quick sort algorithm.
*
* Prarameters:
* narray : the start address of the integer array.
* n : the size of the integer array.
* k : the priority of the needed element.
*
* Return Value:
* -1 : array size error.
* -2 : k value invalid.
* other : the index of the k-th biggest element in the array.
*/
int new_qsort(const int * na, int low, int high, int nNeed);
/**
* find the k-th biggest element in a integer array, using a
* modified quick sort algorithm.
*
* Prarameters:
* narray : the start address of the integer array.
* n : the size of the integer array.
* k : the priority of the needed element.
*
* Return Value:
* -1 : array size error.
* -2 : k value invalid.
* other : the index of the k-th biggest element in the array.
*/
int find_orderk(const int * narray, const int n, const int k) {
if ( n < 1)
return -1;if ( (K < 1) || (K > n) )
return -2;// store a copy of the original int arrray.
int * pN = new int[n];
for (int i = 0; i < n; i++)
pN[i] = narray[i];// find the k-th biggest VALUE in the int array.
int nVal = new_qsort(pN, 0, n-1, k-1);// find the first position of the k-th biggest VALUE in the original array.
for (int i = 0; i < n; i++)
if ( narray[i] == nVal)
return i;
};
/**
* one pass of standard quik sort.
*
* Parameters:
* na : the start address of the integer array.
* low : the lower boundary of the elements needed to be processed.
* hight : the upper boundary of the elements needed to be processed.
*
* Return Value:
* the index of the pivot element after this pass.
*/
int partition(const int * na, int low, int hight) {
int nTmp = na[low];
while (low < high ) {
while (low < high && na[high] <= nTmp)
high--;
na[low] = na[high];
while (low < high && na[low] >= nTmp)
low++;
na[higt] = na[low];
}
na[low] = nTmp;
return low;
}
/**
* modified qsort, only sort the part that contains the
* nNeed-th biggest element. The return value is the value of
* the nNeed-th biggest element, not the position.
*
* Parameters:
* na : the start address of the integer array.
* low : the lower boundary of the elements needed to be processed.
* hight : the upper boundary of the elements needed to be processed.
* nNeed : the priority of the needed element.
*
* Return Value:
* the value of the nNeed-th biggest element in the given integer array.
*/
int new_qsort(const int * na, int low, int high, int nNeed) {
int nFound = partition(na, low, high);
if (nFound == nNeed) {
return na[nFound];
} if (nFound < nNeed) {
return new_qsort(na, nFound, high);
} if (nFound > nNeed) {
return new_qsort(na, low, nFound);
}
}
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=548753