Chinaunix首页 | 论坛 | 博客

分类: C/C++

2011-10-18 21:59:15

时间分析:这个函数的由于是乘2操作,堆的高度为O log(n)的数目。
比较次数为O(n)所以,
所以时间度为:
 O (n lgn)

[code]
1 /*This is the heapsort.c*/
  2 #include"heapsort.h"
  3 #include"heapify.h"
  4 #include"heap.h"
  5 extern int heapsize;
  6 void Heapsort(int A[])
  7 {
  8          int i;
  9          Build_max_heap(A);
 10          for(i = heapsize ; i >= 2; i--)
 11           {
 12                 Exchange(A[1] , A[i]);/*这里和最后一个元素交换的含义在于,得改变几乎所有元素在数组的位置。因为堆中少了一个元素,所以要进行从新排列*/
 13                 heapsize--;
 14                 Max_heapify(A, 1);
 15           }
 16 }
[/code]

  [code] 
/*This is the build_max_heap.c file */
  1 #include"heapify.h"               
  2 #include"build_max_heap.h"
  3 #include"heap.h"
  4 extern int heapsize;
  5 void Build_max_heap(int C[])
  6 {
  7         int i;
  8         for(i = heapsize>>1; i >= 1; i-- )
  9                 Max_heapify(C, i);
10 }
[/code]
[code]
  1 /*      This file describes Build-Max-Heap() fuction.
  2 */
  3 #ifndef BUILD_MAX_HEAP_H
  4 #define BUILD_MAX_HEAP_H
  5 #endif
  6 void Build_max_heap(int C[]);
[/code]
[code]  /*This file is the heap.h "*/
  1
  2 #ifndef HEAP_H
  3 #define HEAP_H
  4 #endif
  5
  6 //#define Heap_size(B) (sizeof(B) /sizeof(B[1]) - 1)
  7
  8 #define Length(N)  (sizeof(N) /sizeof(N[1]) - 1)
  9
 10 #define Left(i) i<<1
 11 #define Right(i) ((i<<1)+1)
 12
 13 #define Exchange(x, y)do{\
 14        typeof(int) m = x;   \
 15           x = y;         \
 16           y = m;        \
 17 }while(0)
[/code]
[code]
  1 #include"heap.h"
  2 #include"heapify.h"
  3 extern int heapsize;
  4 int Max_heapify(int A[],int i)
  5 {
  6
  7         int l, r;
  8         l = Left(i);
  9         r = Right(i);
 10
 11         int largest;
 12         if(l <= heapsize && A[l] > A[i])
 13                 largest = l;
 14         else
 15                 largest = i;
 16         if ( r <= heapsize && A[r] > A[largest])
 17                 largest = r;
 18
 19         if (largest != i)
 20                 Exchange(A[i], A[largest]);
 21         else
 22                 return ;
 23         Max_heapify(A, largest);
 24         return 0;
 25 }
[/code]
[code]
1 /* 
  2      This file describes max-heapify() function
  3 */
  4 #ifndef HEAPIFY_H
  5 #define HEAPIFY_H
  6 #endif
  7
  8 int Max_heapify(int A[], int i);
[/code]
[code]
1 /*      This file is the main.c
  2 */
  3
  4 #include "heap.h"
  5 #include
  6 #include"heapsort.h"
  7
  8 int heapsize;
  9
 10 int main()
 11 {
 12
 13         int B[11];
 14         int n;
 15         printf("The B's size %d", sizeof (B));
 16
 17         printf("Input the nums that you want to sort \n");
 18         for(n = 1; n < 11; n++)
 19                 scanf("%d\n", &B[n]);
 20         printf("end in scan\n");
 21         heapsize = Length(B);
 22         printf("The heapsize is %d", heapsize);
 23         Heapsort(B);
 24         printf("The sorted nums are : \n");
 25         for (n = 10; n >=1; n--)
 26         printf("%d\n", B[n]);
 27         Heap_extract_max(B);
 28
 29         return 0;
 30 }
[/code]
[code]
1
  2 object= main.o heapsort.o heapify.o build_max_heap.o
  3 edit : $(object)
  4         cc  -o edit $(object)
  5 main.o :  heapsort.h main.c
  6         cc -g -Wall -c main.c
  7 heapsort.o : build_max_heap.h heapsort.c heap.h heapsort.h
  8         cc -g -c heapsort.c
  9 heapify.o:  heap.h heapify.c heapify.h
 10         cc -g  -c heapify.c
 11 build_max_heap.o : heapify.h build_max_heap.c build_max_heap.h
 12         cc -g -c build_max_heap.c
 13 .PHONY: clean
 14 clean:
 15         -rm edit $(obj)
[/code]
得到的经验是:
注意在递归的结束条件;我一开始就作错了,结果导致了很多错误;
还有scanf("%d \n", &A[i])的这个问题;
这里scanf(%d \n")会消费掉所有的white_space字符;所以如果你以上面的格式输入时,会多输入一个变量;而这个变量却留在了流文件。因为最后的一个ENTER算作一个white_space,所以要等到一个非white_space自发才会结束输入。


阅读(1370) | 评论(0) | 转发(0) |
0

上一篇:有感

下一篇:分享成果。

给主人留下些什么吧!~~