在做PAT的是时候,用普通的快速排序,在评分后会出现运行超时。
而在网上找到的这种代码不会出现,但是看不懂代码是什么意思,还求前辈解释。
#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;
}
/*您的代码将被嵌在这里*/
void Swap(ElementType *a, ElementType *b)
{
ElementType temp = *a;
*a = *b;
*b = temp;
}
ElementType Median3(ElementType A[], int left, int right)
{
int Center = (left + right) / 2;
if (A[left] > A[Center])
Swap(&A[left], &A[Center]);
if (A[left] > A[right])
Swap(&A[left], &A[right]);
if (A[Center] > A[right])
Swap(&A[Center], &A[right]);
Swap(&A[Center], &A[right - 1]);
return A[right - 1];
}
void QSort(ElementType A[], int left, int right)
{
if (left >= right) return;
ElementType Pivot = Median3(A, left, right);
int i = left, j = right - 1;
while (1) {
while (A[++i] < Pivot) {}
while (A[--j] > Pivot) {}
if (i < j){
Swap(&A[i], &A[j]);
}
else break;
}
Swap(&A[i], &A[right - 1]);
QSort(A, left, i - 1);
QSort(A, i + 1, right);
}
ElementType Median(ElementType A[], int N)
{
QSort(A, 0, N - 1);
return A[N / 2];
}