日志
部分排序---寻找数组中最大的10个数
|
2012图像所复试编程题二(1), 有一个浮点型数组记录了1000个浮点数(float fData[1000]).
编写C/C++代码, 求出这1000个数中最大的10个数.
/*************************************************************************function:
to find the first 10 biggest data in a data array
IPRAI, HUST, 2012, April, 10
****************************************************************************/
#include <stdio.h>
#include <stdlib.h> // only for rand()
#include <time.h> // only for time()
#include <string.h> // only for memset()
/*MySort1(float fpData[10], int npIndex[10], float fpSortedData[10])
function: to sort 10 data in increasing order
input: float fpData[10] --- the 10 data need to be sorted
int npIndex[10]--- the index of the data
output:float fpSortedData[10] --- the 10 sorted data in the increasing order
int npIndex[10] --- the index of the 10 sorted data
return: void
functions used: memset(), sizeof()
*/
void MySort1(float fpData[10], int npIndex[10], float fpSortedData[10])
{
int nRank[10][10];
int i,j;
float fTemp;
int nLocation;
int nRecord[10];
memset(nRank, 0, sizeof(nRank));
// record the relevance comparing result
for(i=0; i < 9; i++)
{
fTemp = fpData[i];
for(j=i+1; j<10; j++)
{
if(fTemp >= fpData[j])
{
nRank[i][j] = 1;
nRank[j][i] = 0;
}
else
{
nRank[i][j] = 0;
nRank[j][i] = 1;
}
}
}
// get the location of data in the sorted array
for(i=0; i<10; i++)
{
nLocation = 0;
for(j=0; j<10; j++)
{
nLocation += nRank[i][j];
}
nRecord[nLocation] = npIndex[i];
fpSortedData[nLocation] = fpData[i];
}
for(i=0; i<10; i++)
{
npIndex[i] = nRecord[i];
}
return;
}
/*MySort2(float fpData[10], int npIndex[10], float fpSortedData[10])
function: to sort 10 data in increasing order in which the last 9 data are sorted in increasing order
input: float fpData[10] --- the 10 data need to be sorted and the last 9 data are sorted
int npIndex[10]--- the index of the data
output:float fpSortedData[10] --- the 10 sorted data in the increasing order
int npIndex[10] --- the index of the 10 sorted data
return: void
functions used:
*/
void MySort2(float fpData[10], int npIndex[10], float fpSortedData[10])
{
int i,j;
float fTemp;
int nLocation;
// rank
fTemp = fpData[0];
for(i=1; i < 10; i++)
{
if(fTemp > fpData[i])
{
nLocation = npIndex[i];
npIndex[i] = npIndex[i-1];
npIndex[i-1] = nLocation;
}
else
{
break;
}
}
for(j=9; j>=i; j--)
fpSortedData[j] = fpData[j];
for(j=0; j<i-1; j++)
fpSortedData[j] = fpData[j+1];
fpSortedData[i-1] = fTemp;
return;
}
int main(void)
{
int nSizeData = 1000; // the size of data array
float fData[1000];
int nSizeRank = 10; // the size of the sorted data
float fRank[10]; // the 10 sorted data in increasing order
float fDataTemp[10]; // the 10 data need to be sorted
int nIndex[10]; // the index of the 10 sorted data in increasing order
int i;
// -----------input the data array------------
// set the seed of random
srand( (unsigned)time( NULL ) );
// get the data array randomly
for(i=0; i < nSizeData; i++)
{
fData[i] = (float)(rand()*0.1);
}
// show some test data
int nSortNum = 1000; // the size for test data
printf("\nThe %d data need to be sorted are: \n", nSortNum);
for(i=0; i< nSortNum; i++)
{
printf(" %f ", fData[i]);
if( (i+1)%5 == 0 )
printf("\n");
}
// initialize the sorted data array
for(i=0; i < nSizeRank; i++)
{
fDataTemp[i] = fData[i];
nIndex[i] = i;
}
MySort1(fDataTemp, nIndex, fRank);
// insert sort
for(i=nSizeRank; i < nSortNum; i++)
{
if(fData[i] > fData[nIndex[0]])
{
fRank[0] = fData[i];
nIndex[0] = i;
MySort2(fRank, nIndex, fRank);
}
}
printf("\nThe first %d biggest data are: \n", nSizeRank);
for(i=nSizeRank-1; i>= 0; i--)
{
printf(" %f ", fData[nIndex[i]]);
if( i%5 == 0 )
printf("\n");
}
printf("\nThe first %d biggest data in incresing order are: \n", nSizeRank);
for(i=0; i< nSizeRank; i++)
{
printf(" %f ", fRank[i]);
if( (i+1)%5 == 0 )
printf("\n");
}
return 0;
}
全部作者的其他最新日志
- • 异或的应用
- • 删链表中的当前节点
- • 排序--不知具体数值,但知相对大小关系
- • 精确计算大数的阶乘
发表评论 评论 (1 个评论)
- 回复 snowhorse712
- 2012图像所复试编程题2
