首页 > 代码库 > 选择问题（selection problem）

选择问题（selection problem）

2024-07-10 03:27:47   231人阅读

/*
    本文是选择问题：

          选择一组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)
{
    if(k <1 || k > N )
    {
        fprintf (stderr, "error, k ??????\n");
        exit (EXIT_FAILURE);
    }
    switch(SortingMethod)
    {
    case SORTING_BUBBLE :
        bubble_sort (A, N,IntComp);
         return A[ k-1];
    case SORTING_INSERTION :
        insertion_sort (A, N,IntComp);
         return A[ k-1];
    case SORTING_SELECTION :
        selection_sort (A, N,IntComp);
         return A[ k-1];
    case SORTING_SHELL :
        shell_sort (A, N,IntComp);
         return A[ k-1];
    case SORTING_QUICK :
        quick_sort (A, N,IntComp);
         return A[ k-1];
    case SORTING_HEAP :
        heap_sort (A, N,IntComp);
         return A[ k-1];
    case SORTING_MERGE :
        merge_sort (A, N,IntComp);
         return A[ k-1];
    default:
        Error ("not a known sorting method!");
    }
    return 0;
}
/*
    解法2： 先把前k个元素读进数组并排序（递增顺序），接着，将剩下

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

*/
int select2(int A[], int N, int k)
{
    // 可改进为前面k个数原地排序。
    int *Ak = malloc(sizeof(int )*k);
    Ak[0 ] = A[0];
    int i,j ;
    for(i = 1; i < k; i++)
    {
         for(j = i- 1; j >= 0 ; j--)
         {
             if(A [i]< Ak[j])
                Ak [j+ 1] = Ak[ j];
             else
                 break;
         }
        Ak [j+ 1] = A[ i];
    }
    for(i = k ; i < N; ++i )
    {
         if(Ak [k- 1]<= A [i]) continue;
        
         for(j = k- 2; j >=0; --j)
         {
             if(A [i] < Ak[j ])
                Ak [j+ 1] = Ak[ j];
             else
                 break;
         }
        Ak [j+ 1] = A[ i];
    }
    int ret = Ak [k- 1];
    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 ;
    for(i = 0; i <k; ++i)
    {
        minIndex = i;
         for(j = i+ 1; j <N; ++j)
             if(A [minIndex] > A [j])
                minIndex = j;
        tmp = A[ minIndex];
        A [minIndex] = A [i];
        A [i] = tmp;
    }
    return A [k- 1];
}
 
/*
    解法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;
    for(j = p +1; 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);
    if(k-1 == r)
         return A[ r];
    else if(r > k - 1)
    {
         return findk( A,p,r -1, k);
    }else
         return findk( A,r+1 ,q, k);
}
int select4(int A[], int N, int k)
{
    return findk (A, 0,N -1, k);
}
 
 
#define ITEMNUM 5000
#define METHODNUM 10
int main()
{
    int A[METHODNUM ][ITEMNUM];
    int k = 564;
    int temp;
    for(int i = 0 ; i < ITEMNUM; ++i)
    {
        temp = rand();
         for(int j = 0; j < METHODNUM; j++)
            A [j][ i] = temp ;
    }
    
    int r1,r2 ,r3, r4,r5,r6 ,r7, r8;
    r1 = select_by_sorting (A[ 0],ITEMNUM ,k, SORTING_BUBBLE);
    r2 = select_by_sorting (A[ 1],ITEMNUM ,k, SORTING_INSERTION);
    r3 = select_by_sorting (A[ 2],ITEMNUM ,k, SORTING_SELECTION);
    r4 = select_by_sorting (A[ 3],ITEMNUM ,k, 4);
    r5 = select_by_sorting (A[ 4],ITEMNUM ,k, 5);
    r6 = select_by_sorting (A[ 5],ITEMNUM ,k, 6);
    r7= select_by_sorting (A[ 6],ITEMNUM ,k, 7);
    r8 = select2 (A[ 7],ITEMNUM ,k);
    int r9 = select3 (A[ 8],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);
    int r10 = select4 (A[ 9],ITEMNUM ,k);
    printf("%d\n" ,r10);
    return 0;
}


联系
我们