linear.cpp

算法设计与分析中的现行选择算法的实现。在visual c++中实现的

#include<stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 100
void swap(int &a,int &b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}
void merge(int array[],int p,int q,int r)
{
    int n1,n2;
    int L[MAX],R[MAX];
    int i,k,j;

    n1 = q-p+1;
    n2 = r-q;

    for(i=1 ; i<=n1 ; i++)
        L[i]=array[p+i-1];
    for(j=1 ; j<=n2 ; j++)
        R[j]=array[q+j];
    L[n1+1] = MAX;
    R[n2+1] = MAX;

    i=1;
    j=1;
    for(k=p;k<=r;k++)
    {
        if(L[i]<=R[j])
        {
            array[k]=L[i];
            i=i+1;
        }
        else
        {
            array[k]=R[j];
            j=j+1;
        }
    }
}
void merge_sort(int array[],int p,int r)
{
    int q;
    if(p<r)
    {
        q = (p+r)/2;
        merge_sort(array,p,q);
        merge_sort(array,q+1,r);
        merge(array,p,q,r);
    }
}

void mid(int A[],int i,int p[])
{
     int k = 5 * i;
     if (A[k]>A[k+2])
         swap(A[k],A[k+2]);
     if (A[k+1]>A[k+3])
         swap(A[k+1],A[k+3]);
     if (A[k]>A[k+1])
         swap(A[k],A[k+1]);
     if (A[k+2]>A[k+3])
        swap(A[k+2],A[k+3]);
     if (A[k+1]>A[k+2])
         swap(A[k+1],A[k+2]);
     if (A[k+4]>A[k+2])
         p[i] = A[k+2];
     else if (A[k+4]>A[k+1])
         p[i] = A[k+4];
     else
         p[i] = A[k+1];
 }
select(int a[],int n,int k)
{
     int i,j,s,t;
     int m,*p,*q,*r;
     if (n<=75) 
	 {				
         merge_sort(a,1,n);
         return a[k-1];			
     }
     p = new int[3*n/4];
     q = new int[3*n/4];
     r = new int[3*n/4];
     for (i=0;i<n/5;i++) 	
     mid(a,i,p);
     m = select(p,i,i/2+1);	
     i = j = s = 0;
     for (t=0;t<n;t++)
	 {
         if (a[t]<m)
             p[i++] =a[t];
         else if (a[t]==m)
             q[j++] =a[t];
         else
             r[s++] =a[t];
	 }
     if (i>k)					
         return select(p,i,k);
     else if (i+j>=k)			
         return m;				
     else						
         return select(r,s,k-i-j);
}

void main()
{
	int k,n,m;
	printf("please input two number n k(k<=n):\n");
	scanf("%d %d",&n,&k);
	int *a= new int [1];
    srand( (unsigned)time( NULL ) );
    int bound = n * 10; 
    for(int i = 0; i < n; ++i)
	{
    a[i] = rand() % bound + 1;
	}
	for(i = 0; i < n; ++i)
	printf("%d ",a[i]);
	m=k+1;
	select(a,n,m);
    printf("\n");
	printf("所找的第%d小的数是%d \n",k,a[m]);
}