PTA 6-11 find the median of self-determined type element sequence (25 points)

6-11 Find the median of a sequence of self typed elements (25 branch )

This question requests to realize a function , seek N A collection element A[] The median , That is, the second in the sequence ⌊(N+1)/2⌋ Big elements . The type of collection element is user-defined ElementType.

Function interface definition ：

ElementType Median( ElementType A[], int N );

Where the given collection elements are stored in the array A[] in , Positive integer N Is the number of array elements . The function must return N individual A[] Median of elements , Its value must also be ElementType type .

Sample referee test procedure ：

#include <stdio.h>

#define MAXN 10
typedef float ElementType;

ElementType Median( ElementType A[], int N );

int main ()
{
    ElementType A[MAXN];
    int N, i;

    scanf("%d", &N);
    for ( i=0; i<N; i++ )
        scanf("%f", &A[i]);
    printf("%.2f\n", Median(A, N));

    return 0;
}

/*  Your code will be embedded here  */

sample input ：

3
12.3 34 -5

No blank lines at the end

sample output ：

12.30

No blank lines at the end

      analysis ： This problem is a sort problem . At first, I wanted to use direct insertion sorting , Stop when you're halfway through the row , Because at this time, the first half of the elements are already in order , The first (N+1)/2 Large elements have naturally appeared , The algorithm complexity is . But after running, I found that it was overtime ; The last measuring point is deliberately set large .

      So a different way of thinking , Use fast line , The complexity is , Basically, it belongs to a very good sorting algorithm . The leftmost principal element is selected , It is found that the last measuring point still times out . This is actually because , The time complexity of fast scheduling is statistically average , The worst case is still , This can be improved by changing the random principal component , Don't delve into it here .

      The last algorithm is Hill sort , Time complexity reaches , There is a detailed introduction on the Internet , I won't say much more , Note that the type in the template code is changed to ElementType.

The code involved is as follows ：

// Sort by selection , You can quit when you are halfway through the line （ From big to small ）
ElementType Median(ElementType A[], int N)
{
    for (int i=0;i<N;i++) {
        ElementType temp=A[i];
        int j,p=i;
        for (j=i+1;j<N;j++) {
            if (A[j]>A[p]) p=j;
        }
        if (p!=i) {
            A[i]=A[p];
            A[p]=temp;
        }
        if (i+1==(N+1)/2) return A[i];
    }
}
// The last measuring point timed out 



// Quick sort 
int partition (ElementType a[],int left,int right)
{
    ElementType temp=a[left];
    int i=left,j=right;
    while (i<j) {
        while (i<j&&a[j]>=temp) j--;
        a[i]=a[j];
        while (i<j&&a[i]<=temp) i++;
        a[j]=a[i];
    }
    a[i]=temp;
    return i;
}
void quicksort(ElementType a[],int left,int right)
{
    if (left<right)
    {
        int pos=partition(a,left,right);
        quicksort(a,left,pos-1);
        quicksort(a,pos+1,right);
    }
}
ElementType Median( ElementType A[], int N )
{
    quicksort(A,0,N-1);
    return A[N/2];
}
// Even so, it will timeout 



// Shell Sort 
ElementType Median(ElementType A[], int N)
{
	int j, gap;
	for (gap = N / 2; gap > 0; gap /= 2) {
		for (j = gap; j < N; j++) { // From array No gap Elements start 
			if (A[j] < A[j - gap]) // Each element is directly inserted and sorted with the data in its own group 
			{
				ElementType temp = A[j];
				int k = j - gap;
				while (k >= 0 && A[k] > temp)
				{
					A[k + gap] = A[k];
					k = k- gap;
				}
				A[k + gap] = temp;
			}
        }
    }
    return A[N/2];
}
//ojbk！