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

创作不易，喜欢的话加个关注点个赞，谢谢谢谢谢谢！