算法之每日一题：找出无序数组中第k大的数字

#include <iostream>
#include <string>
#include <conio.h>
using namespace std;

#define arrayLen(arr) (sizeof(arr)/sizeof(arr[0]))


int* sort(int data[],int len) {  
int temp;  
bool flag = false;  
for (int i = 0; i < len - 1; i++) {  
flag = true;  
for (int j = 0; j < len - i - 1; j++) {  
if (data[j] < data[j + 1]) {  
temp = data[j];  
data[j] = data[j + 1];  
data[j + 1] = temp;  
flag = false;  
}  
}  
if (flag) {  
break;  
}  
}  
return data;  
}  

 void show(int data[],int len) {  

for (int q = 0; q < len; q++) {  
printf("%d ",data[q]);
}  
printf("\n");
}  

 /*
 http://t.jobdu.com/thread-98593-1-1.html
 题目：
 找出无序数组中第k大（or小）的数字

 扩展：
 找出无序数组中第k大的数字，并输出其所在的位置。例如{2，4，3，10，7}中，第2大的数是7，位置在4【百度面试题】。
 */
int main( int argc, char* argv[] )
{

int datas[]={2,4,3,10,7};//这里可以改成用户从cmd终端输入
//int len = sizeof(datas)/sizeof(int);
int len = arrayLen(datas);
printf("%d\n",len);
show(datas,len);

//拷贝数组
int b[25];
for(int i=0;i<len;i++){
*(b+i) = *(datas+i);
}

sort(datas,len);
show(datas,len);
//show(b,len);

int k=-1;//第k大
cout<<"输入第k大"<<endl;
cin>>k;
if(k<0|| k>len)
{
cout<<"输入无效整数"<<endl;
return -1;
}
int loc=-1;
for(int i=0;i<len;i++){
if(b[i]==datas[k-1])
{
loc=i;
}
}

cout<<"输入第"<<k<<"大数是"<<datas[k-1]<<",位置在"<<loc<<endl;
getch();

return 0;
}

结构体数组初始化和遍历

#include <iostream>
#include <string>
#include <conio.h>
using namespace std;

#define arrayLen(arr) (sizeof(arr)/sizeof(arr[0]))
#define entitysLen 5

struct Entity{
int oldindex;
int value;
};


Entity* sort(Entity data[],int len) {  
Entity temp;  
bool flag = false;  
for (int i = 0; i < len - 1; i++) {  
flag = true;  
for (int j = 0; j < len - i - 1; j++) {  
if (data[j].value < data[j + 1].value) {  
temp = data[j];  
data[j] = data[j + 1];  
data[j + 1] = temp;  
flag = false;  
}  
}  
if (flag) {  
break;  
}  
}  
return data;  
}  

//遍历结构体数组
 void show(Entity data[],int len) {  


for (int q = 0; q < len; q++) {  
printf("%d ",data[q].value);
}  
printf("\n");
}  

 /*
 http://t.jobdu.com/thread-98593-1-1.html
 题目：
 找出无序数组中第k大（or小）的数字

 扩展：
 找出无序数组中第k大的数字，并输出其所在的位置。例如{2，4，3，10，7}中，第2大的数是7，位置在4【百度面试题】。
 */
int main(int argc, char* argv[] )
{

int datas[]={2,4,3,10,7};//这里可以改成用户从cmd终端输入

//结构体数组初始化
Entity entitys[entitysLen]={0};
//Entity entitys[12]={{0,12},{1,23}};
for(int i = 0; i < entitysLen; i++){
//printf("%d\n", entitys[i].oldindex);
scanf("%d",&entitys[i].value);
entitys[i].oldindex=i;
}

show(entitys,entitysLen);


sort(entitys,entitysLen);

show(entitys,entitysLen);


int k=-1;//第k大
cout<<"输入第k大"<<endl;
cin>>k;
if(k<0|| k>entitysLen)
{
cout<<"输入无效整数"<<endl;
return -1;
}
cout<<"输入第"<<k<<"大数是"<<entitys[k-1].value<<",原来位置在"<<entitys[k-1].oldindex<<endl;
getch();

return 0;
}