c-你会如何随机选择快速排序来获得多个元素

Question

我目前是算法的新手，我发现了一种方法，可以使用快速排序中的随机选择来获得数组中第K个最小的元素。然而，有人提议进行一个练习，这样它就返回了第K个最小的元素S，例如：
现在，如果我用随机选择来运行这个数组，寻找第三小的元素(K=3( ：
int a[6]={1,3,4,2,5,6}
random_select(a，0,5,3(
将输出"；3〃
但我正在寻找1 2 3，或直到第K个最小元素。

这是当前的代码：

int random_select(int a[], int p, int r, int i) {
if (p == r) {
return a[p];
}
int q = partition_random(a, p, r);
int k = q - p + 1;
if (i == k) { //this is our element
return a[q];
}
else if (i < k) { //on the left side
return random_select(a, p, q - 1, i);
}
else { // right side
return random_select(a, q + 1, r, i - k);
}
}

Answer 1

为什么要用推土机把面包屑从桌子上刮下来？

如果您想要数组中最低的'n'值，只需遍历数组即可查找这些值。

以下是两个版本，一个按数组顺序，另一个按限定值的排序顺序。

亲吻！

int cmp( const void *a, const void *b ) { return *(int*)a - *(int*)b; }
int main() {
size_t i = 0, n = 0;
int a[] = { 1,3,4,2,5,6 };
const int sz = sizeof a/sizeof a[0];
printf( "Simple selection <= 3n" );
for( i = 0; i < sz; i++ )
if( a[i] <= 3 )
printf( "%d ", a[ i ] );
puts( "" );
int srt[ sz ];
for( i = 0; i < sz; i++ )
if( a[i] <= 3 )
srt[ n++ ] = a[ i ];
qsort( srt, n, sizeof srt[0], cmp );
printf( "Sorted selection <= 3n" );
for( i = 0; i < n; i++ )
printf( "%d ", srt[ i ] );
puts( "" );

return 0;
}

输出

Simple selection <= 3
1 3 2
Sorted selection <= 3
1 2 3

编辑：KISS到此为止。成为"；"一般"；，也许更像这个

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// "helper" function
void show( int a[], size_t ssz ) {
for( size_t si = 0; si < ssz; si++ )
printf( "%d ", a[ si ] );
puts( "" );
}
// for "qsort()"
int cmp( const void *a, const void *b ) { return *(int*)a - *(int*)b; }
// general purpose "sniffer" for 'K' lowest values
// no check of "lowest 10 values of 5 element array"
void func( int a[], size_t sz, size_t K ) {
int select[ 100 ]; // should be [K], but no VLA's for my old compiler
size_t ai = 0, si = 0, sii = 0, Mx = 0;
// Start with first 'K' elements as default
for( si = 0; si < K; si++ )
select[ si ] = a[ si ];
// compare further elements against what's been selected
for( ai = K; ai < sz; ai++ )
for( si = 0; si < K; si++ )
if( a[ ai ] < select[ si ] ) {
// higher than one...find highest to replace
for( Mx = si, sii = Mx + 1; sii < K; sii++ ) {
if( select[ Mx ] < select[ sii ] )
Mx = sii;
}
select[ Mx ] = a[ ai ];
break;
}
// now some output
printf( "%20s: K(%d) :: ", "In sequence", K );
show( select, K );
printf( "%20s: K(%d) :: ", "Sorted", K );
qsort( select, K, sizeof select[0], cmp );
show( select, K );
}
int main() { // a handful of tests
{
int a[] = { -15839, 113, 69849, 40, 0, 938 };
func( a, sizeof a/sizeof a[0], 3 );
func( a, sizeof a/sizeof a[0], 4 );
}
puts("");
{
int a[] = { 9, 8, 7, 6, 5, 4 };
func( a, sizeof a/sizeof a[0], 3 );
func( a, sizeof a/sizeof a[0], 4 );
}
return 0;
}

输出

In sequence: K(3) :: -15839 0 40
Sorted: K(3) :: -15839 0 40
In sequence: K(4) :: -15839 113 0 40
Sorted: K(4) :: -15839 0 40 113
In sequence: K(3) :: 6 5 4
Sorted: K(3) :: 4 5 6
In sequence: K(4) :: 5 4 7 6
Sorted: K(4) :: 4 5 6 7

使用索引而不是像只处理int数组那样锚定func()可能会更通用和复杂一点。。。这个练习留给读者。。。