一道简单的ACM题目,快速排序的,老是提交不成功,大家帮我看看DescriptionGive a set of numbers,output them after sort.You may use any algorithm you like to solve it.InputEach input file contains only one case.Each test case begins

一道简单的ACM题目,快速排序的,老是提交不成功,大家帮我看看DescriptionGive a set of numbers,output them after sort.You may use any algorithm you like to solve it.InputEach input file contains only one case.Each test case begins
一道简单的ACM题目,快速排序的,老是提交不成功,大家帮我看看
Description
Give a set of numbers,output them after sort.You may use any algorithm you like to solve it.
Input
Each input file contains only one case.
Each test case begins with an integer N(0

一道简单的ACM题目,快速排序的,老是提交不成功,大家帮我看看DescriptionGive a set of numbers,output them after sort.You may use any algorithm you like to solve it.InputEach input file contains only one case.Each test case begins
题目里面说的很清楚了,时间复杂度为n平方可能会超时,要用O(n*lgn)的算法才行.快速排序的时间复杂度在最坏情况下是 O(n2),
你用堆排序试试.下面是我写的堆排序的代码：
#include
#include
#define LEFT(i) (2*(i + 1) - 1)
#define RIGHT(i) (2* (i + 1))
void max_heapify_itr(int a[], int size, int index);
void build_max_heap(int a[], int size);
void heapsort(int a[], int size);
void exchg(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void max_heapify(int a[], int size, int index)
{
int l, r, largest;
l = LEFT(index);
r = RIGHT(index);
if (l < size && a[l] > a[index]) {
largest = l;
} else {
largest = index;
}
if (r < size && a[r] > a[largest]) {
largest = r;
}
if (largest != index) {
exchg(&a[largest], &a[index]);
max_heapify(a, size, largest);
}
}
void max_heapify_itr(int a[], int size, int index)
{
int l, r, largest;
while (1) {
l = LEFT(index);
r = RIGHT(index);
if (l < size && a[l] > a[index]) {
largest = l;
} else {
largest = index;
}
if (r < size && a[r] > a[largest]) {
largest = r;
}
if (largest != index) {
exchg(&a[largest], &a[index]);
index = largest;
} else {
break;
}
}
}
void build_max_heap(int a[], int size)
{
int i;
for (i = size / 2; i >= 0; i--) {
max_heapify_itr(a, size, i);
}
}
void heapsort(int a[], int size)
{
int i;
build_max_heap(a, size);
for (i = 0; i < size; i++) {
exchg(&a[size - i - 1], &a[0]);
max_heapify_itr(a, size - i - 1, 0);
}
}
int main()
{
int N, i;
int *a;
scanf("%d", &N);
a = malloc(sizeof(int) * N);
for (i = 0; i < N; i++) {
scanf("%d", &a[i]);
}
heapsort(a, N);
for (i = 0; i < N; i++) {
printf("%d ", a[i]);
}
free(a);
return 0;
}
我在这个网上测了一下,这个代码结果如下：
Test # 1. Accepted
Use Time 4ms, Use Memory 36KB
Test # 2. Accepted
Use Time 0ms, Use Memory 36KB
Test # 3. Accepted
Use Time 8ms, Use Memory 36KB
Test # 4. Accepted
Use Time 0ms, Use Memory 40KB
Test # 5. Accepted
Use Time 0ms, Use Memory 36KB
Test # 6. Accepted
Use Time 4ms, Use Memory 44KB
Test # 7. Accepted
Use Time 0ms, Use Memory 40KB
Test # 8. Accepted
Use Time 0ms, Use Memory 40KB
Test # 9. Accepted
Use Time 8ms, Use Memory 56KB
Test #10. Accepted
Use Time 12ms, Use Memory 80KB
Test #11. Accepted
Use Time 88ms, Use Memory 432KB
Test #12. Accepted
Use Time 960ms, Use Memory 3948KB
Test #13. Accepted
Use Time 784ms, Use Memory 3944KB
Test #14. Accepted
Use Time 732ms, Use Memory 3944KB
Congratulation! Your solution has passed all of test cases.
Use Time 2600ms, Use Memory 3948KB