|
|
5.堆排序
|
|
|
|
|
|
5.1 描述
|
|
|
（1）将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
|
|
|
（2）将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),
|
|
|
且满足R[1,2…n-1]<=R[n]；
|
|
|
（3）由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，
|
|
|
然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。
|
|
|
不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成
|
|
|
|
|
|
5.2 复杂程度
|
|
|
时间复杂度O(nlog2n)
|
|
|
空间复杂度O(1)
|
|
|
|
|
|
5.3 代码
|
|
|
#include <stdio.h>
|
|
|
void swap(int arr[], int a, int b)
|
|
|
{
|
|
|
int tmp;
|
|
|
tmp = arr[a];
|
|
|
arr[a] = arr[b];
|
|
|
arr[b] = tmp;
|
|
|
}
|
|
|
|
|
|
void heapify(int tree[], int n, int i)
|
|
|
{
|
|
|
if (i >= n)
|
|
|
{
|
|
|
return;
|
|
|
}
|
|
|
int max = i;//假设父节点为最大值
|
|
|
int c1 = 2 * i + 1;
|
|
|
int c2 = 2 * i + 2; //左孩子结点的下标为2i + 1, 右孩子结点的下标为2i + 2
|
|
|
if (c1 < n && tree[c1] > tree[max])
|
|
|
{//左孩子的下标要小于总结点数
|
|
|
max = c1;//将较大值的结点下标记录下来
|
|
|
}
|
|
|
if (c2 < n && tree[c2] > tree[max])
|
|
|
{
|
|
|
max = c2;//将较大值的结点下标记录下来
|
|
|
}
|
|
|
if (max != i)
|
|
|
{//如果最大值不是根节点
|
|
|
swap(tree, max, i);//交换tree[max]和tree[i]的值
|
|
|
heapify(tree, n, max);//max就是孩子结点下标
|
|
|
}
|
|
|
}
|
|
|
|
|
|
void build_heapify(int tree[], int n)
|
|
|
{
|
|
|
int last_node = n - 1;
|
|
|
int parent = (last_node - 1) / 2;
|
|
|
int i;
|
|
|
for (i = parent; i >= 0; i--)
|
|
|
{
|
|
|
heapify(tree, n, i);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
void heapify_sort(int tree[], int n)
|
|
|
{
|
|
|
build_heapify(tree, n);
|
|
|
int tmp = tree[0];
|
|
|
for (int i = n - 1; i >= 0; i--)
|
|
|
{//从最后一个结点开始
|
|
|
swap(tree, i, 0);
|
|
|
heapify(tree, i, 0);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main(){
|
|
|
int tree[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
|
|
|
int n = 14;
|
|
|
printf("原数组为:");
|
|
|
for (int i = 0; i < n; i++)
|
|
|
{
|
|
|
printf("%d ", tree[i]);
|
|
|
}
|
|
|
printf("\n");
|
|
|
heapify_sort(tree, n);
|
|
|
printf("经过堆排序后的数组为：");
|
|
|
for (int i = 0; i < n; i++)
|
|
|
{
|
|
|
printf("%d ", tree[i]);
|
|
|
}
|
|
|
printf("\n");
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
5.4 运行时间
|
|
|
0.02498s |
