PAT基础编程题目-6-11 求自定类型元素序列的中位数

题目详情

题目地址：https://pintia.cn/problem-sets/14/problems/743

解答

C语言版

注：这里如果简单的使用冒泡等一般的排序方法是通过不了的，大N会卡时。使用希尔排序可以通过。

#include <stdio.h>

#define MAXN 1000
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) {
   
	int increment = N / 2;
	ElementType tmp;
	int i, j;
	// 采用希尔排序+直接插入排序
	while (increment) {
   
		for (i = 0; i < N-increment; i++)
		{
   
			for (j = i+increment; (j-increment)>=0 && A[j-increment] > A[j]; j = j - increment )
			{
   
				tmp = A[j - increment];
				A[j - increment] = A[j];
				A[j] = tmp;
			}
		}
		increment = increment / 2;
	}
	for (int i = 0; i < N; i++)
	{
   
		printf("%.2f ", A[i]);
	}
	printf("\n");
	return A[N / 2];  // 返回第N/2个位置的即可，不需要分奇偶讨论
}

C++版

C++中有排序函数，可以直接使用这个排序函数（官方写的比我们自己写的要快太多了，是一种优化后的快速排序）

#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;

#define MAXN 1000
typedef float ElementType;

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

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

	cin >> N;
	for (i = 0; i < N; i++)
		cin >> A[i];
	cout << fixed << setprecision(2) << Median(A, N)<<endl;

	return 0;
}
ElementType Median(ElementType A[], int N) {
   
	// 用C++自带（#include<algorithm>中）的排序函数
	sort(A, A+N, greater<ElementType>());  //不写第三个参数，默认升序。greater<ElementType>()表示降序
	for (int i = 0; i < N; i++)
	{
   
		printf("%.2f ", A[i]);
	}
	printf("\n");
	return A[N / 2];
}

Java版

Java中有排序函数，可以直接使用这个排序函数（官方写的比我们自己写的要快太多了，是一种优化后的快速排序）

import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Scanner;
public class Main{
   

	private static final int MAXN = 1000;
	
	private static float Median(float []A, int N) {
   
		Arrays.sort(A, 0, N);  //0包括，N不包括
		for (int i = 0; i < N; i++) {
   
			System.out.print(A[i]+" ");
		}
		System.out.println();
		return A[N/2];
	}
	
	public static void main(String[] args) {
   
		int N = 0;
		float [] A = new float[MAXN];
		Scanner scanner = new Scanner(System.in);
		if(scanner.hasNext()) {
   
			N = scanner.nextInt();
			for (int i = 0; i < N; i++) {
   
				A[i] = scanner.nextFloat();
			}
		}
		scanner.close();
		DecimalFormat decimalFormat = new DecimalFormat("#.00");
		System.out.println(decimalFormat.format(Median(A, N)));
	}
}