Question

求一个算法把n个数中的第k大的数求出来，要求时间复杂度为O（n）

rt

Answer 1

int heapsort(int *data1, int n, int bigk)//利用堆排序，存在一种优化方案：建立K大的堆
{
int data[] = {1,343,34,23,56,234,787,25};
//Part 1
int i, j, j2, k;
int tmp;

for(k = (n>>1) - 1; k >= 0; k--)
{
tmp = data[k];

for(j = k; (j<<1) <= n-2; j = i)
{
j2 = j << 1;
if(j2+2 > n-1)
i = j2 + 1;
else
{
if(data[j2+1] < data[j2+2])
i = j2+2;
else
i = j2+1;
}

if(tmp < data[i])
data[j] = data[i];
else
break;
}
data[j] = tmp;
}

//Part 2
int range = n - bigk;
for(k = n-1; k > range -1; k--)
{
tmp = data[k];
data[k] = data[0];
for(j = 0; (j<<1) <= k-2; j = i)
{
j2 = j<<1;
if(j2+2 > k-1)
i = j2+1;
else
{
if(data[j2+1] < data[j2+2])
i = j2+2;
else
i = j2+1;
}
if(tmp < data[i])
data[j] = data[i];
else break;
}
data[j] = tmp;
}
return data[range];
}

//堆的方法虽然看起来复杂，却绝对是高效的算法

Answer 2

一楼的太复杂了

建立循环（一个循环是所以数字个数）：从第一个数字a开始，和下面每一个数比较，并建立一个识别变量i=0,当有一个数字大于a时i=i+1，当次循环结束时如果i=n-1，这时就求出了这个数跳出循环。剩余的数不需要识别了。
dim a(100) &&假设数组a(100)中包含100个数
int n &&要求的位数
int j,k &&外部循环与内部循环的两上递进变量
int i &&识别变量

for j=1 to 100 step 1
i=0
for k=j+1 to 100 step 1
if a(k)>a(j)
i=i+1
endif
endfor
if i=n-1
exit
endif
endfor

? a(j) &&要求的数

vfp语法

Answer 3

一楼的太复杂了
建立循环（一个循环是所以数字个数）：从第一个数字a开始，和下面每一个数比较，并建立一个识别变量i=0,当有一个数字大于a时i=i+1，当次循环结束时如果i=n-1，这时就求出了这个数跳出循环。剩余的数不需要识别了

Answer 4

#include <iostream.h>
#include <stdio.h>

void main()
{
int maxInt=1;
int intArray[6]={1,5,18,2,2,9};
int flags=intArray[0];

for(int i=1; i<=sizeof(intArray)/4;i++)
{
intArray[i-1]=flags;
if(intArray[i-1]<intArray[i])
{
flags=intArray[i];
maxInt=i+1;
}
}
printf("%d",maxInt);
getchar();
return;
}

c算法

Answer 5

int
heapsort(int
*data1,
int
n,
int
bigk)//利用堆排序，存在一种优化方案：建立K大的堆
{
int
data[]
=
{1,343,34,23,56,234,787,25};
//Part
1
int
i,
j,
j2,
k;
int
tmp;
for(k
=
(n>>1)
-
1;
k
>=
0;
k--)
{
tmp
=
data[k];
for(j
=
k;
(j<<1)
<=
n-2;
j
=
i)
{
j2
=
j
<<
1;
if(j2+2
>
n-1)
i
=
j2
+
1;
else
{
if(data[j2+1]
<
data[j2+2])
i
=
j2+2;
else
i
=
j2+1;
}
if(tmp
<
data[i])
data[j]
=
data[i];
else
break;
}
data[j]
=
tmp;
}
//Part
2
int
range
=
n
-
bigk;
for(k
=
n-1;
k
>
range
-1;
k--)
{
tmp
=
data[k];
data[k]
=
data[0];
for(j
=
0;
(j<<1)
<=
k-2;
j
=
i)
{
j2
=
j<<1;
if(j2+2
>
k-1)
i
=
j2+1;
else
{
if(data[j2+1]
<
data[j2+2])
i
=
j2+2;
else
i
=
j2+1;
}
if(tmp
<
data[i])
data[j]
=
data[i];
else
break;
}
data[j]
=
tmp;
}
return
data[range];
}
//堆的方法虽然看起来复杂，却绝对是高效的算法