选择问题（selection problem）

本文是选择问题：

选择一组N个数当中的第k小的数（第k大的数类似）
集中方法的实现代码

#include "sorting.h"

#include "fatal.h"

#define SORTING_BUBBLE 1

#define SORTING_INSERTION 2

#define SORTING_SELECTION 3

#define SORTING_SHELL 4

#define SORTING_QUICK 5

#define SORTING_HEAP 6

#define SORTING_MERGE 7

解法1：我们可以对这个乱序数组按照从小到大先行排序，然后

取出前k大，总的时间复杂度为O(n*logn + k)。

int select_by_sorting(int A[], int N, int k, int SortingMethod)

{

|| k > N )

{

fprintf (stderr, "error, k ??????\n");

exit (EXIT_FAILURE);

}

switch(SortingMethod)

{

case SORTING_BUBBLE :

bubble_sort (A, N,IntComp);

];

case SORTING_INSERTION :

insertion_sort (A, N,IntComp);

];

case SORTING_SELECTION :

selection_sort (A, N,IntComp);

];

case SORTING_SHELL :

shell_sort (A, N,IntComp);

];

case SORTING_QUICK :

quick_sort (A, N,IntComp);

];

case SORTING_HEAP :

heap_sort (A, N,IntComp);

];

case SORTING_MERGE :

merge_sort (A, N,IntComp);

];

default:

Error ("not a known sorting method!");

}

;

}

解法2：先把前k个元素读进数组并排序（递增顺序），接着，将剩下

的元素逐个读入。当新元素大于数组中的第k个元素是则忽略，否则将
其放入正确的位置，旧的第k个元素将被挤掉！

int select2(int A[], int N, int k)

{

// 可改进为前面k个数原地排序。

int *Ak = malloc(sizeof(int )*k);

Ak ];

int i,j ;

; i < k; i++)

{

; j--)

{

if(A [i]< Ak[j])

Ak ] = Ak[ j];

else

break;

}

Ak ] = A[ i];

}

for(i = k ; i < N; ++i )

{

]<= A [i]) continue;

; --j)

{

if(A [i] < Ak[j ])

Ak ] = Ak[ j];

else

break;

}

Ak ] = A[ i];

}

];

free(Ak );

return ret ;

}

解法3：利用选择排序或交互排序，K次选择后

即可得到第k大的数。总的时间复杂度为O(n*k)

int select3(int A[], int N, int k)

{

int minIndex ;

int tmp;

int i,j ;

; i <k; ++i)

{

minIndex = i;

; j <N; ++j)

if(A [minIndex] > A [j])

minIndex = j;

tmp = A[ minIndex];

A [minIndex] = A [i];

A [i] = tmp;

}

];

}

解法4：利用快速排序的思想，从数组S中随机找出一个元素X，

把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素
     小于X。这时有两种情况：
          1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
          2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)

int partition(int A[], int p, int q)

{

// select a pivot

// for simplicity select p as pivot

int i,j ;

i = p ;

int tmp;

; j <= q ; j++)

{

if(A [j] < A[p ])

{

++i;

if(i == j)

continue;

tmp = A[ i];

A [i] = A[j ];

A [j] = tmp;

}

tmp = A [i];

A[i ] = A[p];

A[p ] = tmp;

return i ;

}

int findk( int A[], int p, int q, int k)

{

int r = partition (A, p,q);

== r)

return A[ r];

)

{

, k);

}else

,q, k);

}

int select4(int A[], int N, int k)

{

, k);

}

#define ITEMNUM 5000

#define METHODNUM 10

int main()

{

int A[METHODNUM ][ITEMNUM];

;

int temp;

; i < ITEMNUM; ++i)

{

temp = rand();

; j < METHODNUM; j++)

A [j][ i] = temp ;

}

int r1,r2 ,r3, r4,r5,r6 ,r7, r8;

r1 ],ITEMNUM ,k, SORTING_BUBBLE);

r2 ],ITEMNUM ,k, SORTING_INSERTION);

r3 ],ITEMNUM ,k, SORTING_SELECTION);

r4 );

r5 );

r6 );

r7);

r8 ],ITEMNUM ,k);

],ITEMNUM ,k);

printf("%d\n%d\n%d\n%d\n%d\n%d\n%d\n%d\n" ,r1, r2,r3,r4 ,r5, r6,r7,r8 );

printf("%d\n" ,r9);

],ITEMNUM ,k);

printf("%d\n" ,r10);

;

}

巴特西

选择问题（selection problem）

最新文章

热门文章