[PTA]6-11 求自定類型元素序列的中位數

本題要求實作一個函數，求N個集合元素A[]的中位數，即序列中第⌊(N+1)/2⌋大的元素。其中集合元素的類型為自定義的ElementType。

函數接口定義：

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

其中給定集合元素存放在數組A[]中，正整數N是數組元素個數。該函數須傳回N個A[]元素的中位數，其值也必須是ElementType類型。

裁判測試程式樣例：

#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;
}

/* 你的代碼将被嵌在這裡 */
           

輸入樣例：

3
12.3 34 -5
           

輸出樣例：

12.30
           

• 送出結果：

• 源碼：

#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;
}

/* 你的代碼将被嵌在這裡 */
ElementType Median(ElementType A[], int N)
{
    // gap是每次排序分組的間隔，每次間隔縮小兩倍
    for (int gap = N / 2; gap >= 1; gap /= 2)
    {
        // 每個元素在同一組内采用一次直接插入排序
        for (int i = gap; i < N; i++)
        {
            // 如果同一組内前一個元素大于相 gap個位置的元素，則交換兩者位置
            for (int j = i - gap; j >= 0 && A[j] > A[j + gap]; j -= gap)
            {
                ElementType temp;
                temp = A[j];
                A[j] = A[j + gap];
                A[j + gap] = temp;
            }
        }
    }

    return A[N / 2];
}
           

注： 總之這題就是非常的離譜，常見的選擇排序、冒泡排序都要逾時，采用希爾排序時就算不把判斷條件寫進for循環也要逾時。