题目里面说的很清楚了,时间复杂度为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
