我必须重复排序一个包含300个随机元素的数组。但是我必须做一种特殊的排序：我需要数组子集中5%的最小值，然后计算一些值并增加子集。现在再次计算该值，子集也会增加以此类推，直到子集包含整个数组。
子集从前10个元素开始，每一步后增加10个元素。
即：
子集大小（5%*子集）
10 1（所以是最小的元素）
20 1（因此也是最小的）
30 2（最小和第二小）
…
计算值基本上是小于k的所有元素和特别加权的k最小元素的总和。
代码中：
k = ceil(0.05 * subset) -1; // -1 because array index starts with 0...
temp = 0.0;
for( int i=0 i<k; i++)
temp += smallestElements[i];
temp += b * smallestElements[i];
我已经实现了一个基于选择排序的算法（代码在本文末尾）我使用MAX（k）指针来跟踪k个最小元素因此，我不必对所有小于k的元素排序：/
此外，我知道选择排序不利于性能，这在我的情况下很不幸是至关重要的。
我试着找出一种方法，我可以使用一些快速或基于堆的算法我知道，如果k和子集是固定的，那么quickselect或heapselect非常适合查找k个最小元素。
但因为我的子集更像是数据的输入流，所以我认为基于快速排序的算法会退出。
我知道，如果k是固定的，heapselect将非常适合数据流。但是，在没有大的性能下降的情况下，我没有管理它来调整动态k的heap select，因此它比我的基于选择排序的版本效率低：（有人能帮我修改动态k的heap select吗？
如果没有更好的算法，您可能会为我的选择排序实现找到一种不同的/更快的方法。这里是我实现的一个最小的例子，这个例子中不使用计算变量，所以不用担心（在我的实际程序中，为了获得更好的性能，我只是手动展开了一些循环）
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ARRAY_SIZE 300
#define STEP_SIZE 10
float sortStream( float* array, float** pointerToSmallest, int k_max){
int i,j,k,last = k_max-1;
float temp=0.0;
// init first two pointers
if( array[0] < array[1] ){
pointerToSmallest[0] = &array[0];
pointerToSmallest[1] = &array[1];
}else{
pointerToSmallest[0] = &array[1];
pointerToSmallest[1] = &array[0];
}
// Init remaining pointers until i= k_max
for(i=2; i< k_max;++i){
if( *pointerToSmallest[i-1] < array[i] ){
pointerToSmallest[i] = &array[i];
}else{
pointerToSmallest[i] = pointerToSmallest[i-1];
for(j=0; j<i-1 && *pointerToSmallest[i-2-j] > array[i];++j)
pointerToSmallest[i-1-j] = pointerToSmallest[i-2-j];
pointerToSmallest[i-1-j]=&array[i];
}
if((i+1)%STEP_SIZE==0){
k = ceil(0.05 * i)-1;
for(j=0; j<k; j++)
temp += *pointerToSmallest[j];
temp += 2 * (*pointerToSmallest[k]);
}
}
// Selection sort remaining elements
for( ; i< ARRAY_SIZE; ++i){
if( *pointerToSmallest[ last ] > array[i] ) {
for(j=0; j != last && *pointerToSmallest[ last-1-j] > array[i];++j)
pointerToSmallest[last-j] = pointerToSmallest[last-1-j];
pointerToSmallest[last-j] = &array[i];
}
if( (i+1)%STEP_SIZE==0){
k = ceil(0.05 * i)-1;
for(j=0; j<k; j++)
temp += *pointerToSmallest[j];
temp += 2 * (*pointerToSmallest[k]);
}
}
return temp;
}
int main(void){
int i,k_max = ceil( 0.05 * ARRAY_SIZE );
float* array = (float*)malloc ( ARRAY_SIZE * sizeof(float));
float** pointerToSmallest = (float**)malloc( k_max * sizeof(float*));
for( i=0; i<ARRAY_SIZE; i++)
array[i]= rand() / (float)RAND_MAX*100-50;
// just return a, so that the compiler doens't drop the function call
float a = sortStream(array,pointerToSmallest, k_max);
return (int)a;
}
非常感谢你
最佳答案
通过使用两个堆存储流中的所有项，您可以：
在O（1）中查找前p%元素
在o（log n）中更新数据结构（两个堆）
假设，现在我们有n个元素，k=p%*n，
存储前k项的最小堆（LargerPartHeap）
用于存储其他（N-k）项的最大堆（SmallerPartHeap）。
smallerpartheap中的所有项都小于或等于largerpartheap的最小项（top item@largerpartheap）。
对于查询“什么是顶级p%元素？”，只需返回largerpartheap
更新“new element x from stream”，
2.检查new k'=（N+1）*p%，如果k'=k+1，将SmallerPartHeap的顶部移动到LargerPartHeap-O（对数）
2.b如果x大于LargerPartHeap的顶部元素（最小元素），则将x插入LargerPartHeap，并将LargerPartHeap的顶部移动到SmallerPartHeap；否则，将x插入SmallerPartHeap-O（logN）
关于c - 从数据流中选择前k个(百分比)项的有效算法:，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20038163/