堆排序

堆排序是对简单选择排序算法的一种改进。可以构建大顶堆（每个结点的值都大于等于其左右孩子的值）也可以构建小顶堆（每个结点的值都小于等于其左右孩子的值）。堆排自我感觉代码理解起来还是有点难，主要是如何构建一个新堆以及输出堆顶元素后，怎样调整剩余元素成为一个新堆。

1、堆排代码

 1 void heapsort(SqList *s)
 2 {
 3     int increment = s->length/2;   //父结点记录，父结点为从increment到s->length的记录
 4     //构建大顶堆
 5     for (int i = increment;i>0;i--)
 6     {
 7         heapadjust(s,i,s->length);
 8     }
 9     //交换大顶堆父结点到末端，将最大元素沉到叶结点处；再调整剩余元素为一个新的大顶堆
10     for(int j = s->length;j>1;j--)
11     {
12         swap(s,1,j);
13         heapadjust(s,1,j-1);
14     }
15 }

2、堆调整代码

 1 void heapadjust(SqList *s,int i,int j)
 2 {
 3     //保存当前结点
 4     int temp = s->data[i];
 5     int k;
 6     //对该节点的左右孩子进行比较，再将左右孩子中较大的与根结点比较，将最大者作为根结点（与选择排序类似，选择最大的值作为根结点）
 7     for (k = 2*i;k < j;k*=2)
 8     {
 9         if ((s->data[k]) < (s->data[k+1]))
10         {
11             k++;
12         }
13         if (temp > s->data[k])
14         {
15             break;
16         }
17         s->data[i] = s->data[k];
18         i = k;
19     }
20     s->data[i] = temp;
21 }

堆排测试完整代码：

 1 #include <iostream>
 2 using namespace std;
 3 #define MAXSIZE 100
 4 
 5 struct SqList
 6 {
 7     int data[MAXSIZE];
 8     int length;
 9 };
10 
11 void heapadjust(SqList *s,int i,int j)
12 {
13     //保存当前结点
14     int temp = s->data[i];
15     int k;
16     //对该节点的左右孩子进行比较，再将左右孩子中较大的与根结点比较，将最大者作为根结点（与选择排序类似，选择最大的值作为根结点）
17     for (k = 2*i;k < j;k*=2)
18     {
19         if ((s->data[k]) < (s->data[k+1]))
20         {
21             k++;
22         }
23         if (temp > s->data[k])
24         {
25             break;
26         }
27         s->data[i] = s->data[k];
28         i = k;
29     }
30     s->data[i] = temp;
31 }
32 
33 void swap(SqList *s,int i,int j)
34 {
35     int temp;
36     if (s->data[i] > s->data[j])
37     {
38         temp = s->data[i];
39         s->data[i] = s->data[j];
40         s->data[j] = temp;
41     }
42 }
43 
44 void heapsort(SqList *s)
45 {
46     int increment = s->length/2;   //父结点记录，父结点为从increment到s->length的记录
47     //构建大顶堆
48     for (int i = increment;i>0;i--)
49     {
50         heapadjust(s,i,s->length);
51     }
52     //交换大顶堆父结点到末端，将最大元素沉到叶结点处；再调整剩余元素为一个新的大顶堆
53     for(int j = s->length;j>1;j--)
54     {
55         swap(s,1,j);
56         heapadjust(s,1,j-1);
57     }
58 }
59 
60 void main()
61 {
62     SqList s;
63     s.length = 5;
64     int m;
65     for (int i = 1; i <= s.length;i++)
66     {
67         cin >> m;
68         s.data[i] = m;
69     }
70     heapsort(&s);
71     for (int i = 1; i <= s.length;i++)
72     {
73         cout << s.data[i] << " ";        
74     }
75     system("pause");
76 }

结果：

复杂度分析：

堆排序的运行时间主要消耗在初始构建堆和重建堆时的反复筛选上。在构建堆的过程中，根结点与其左右孩子结点最多进行两次的比较与交换操作，因此整个构建堆的时间复杂度为O(n)。在正式排序的过程中，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的性质），并需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。

空间复杂度上，它只有一个用来交换的暂存单元，空间复杂度为O(1)。

由于记录的比较与交换是跳跃式进行的，因此堆排是一种不稳定的排序算法。