蓝桥杯算法基础（15）：十大排序算法（堆排序）c语言版
堆排序
外堆：
需要一段和原来数组长度大小的内存空间，这段内存空间是用来存储堆结构的
内堆：
不需要重新申请内存，直接原来的数组上进行排序
堆结构
本质上就是一个完全二叉树（不了解二叉树可以取学习一下二叉树的基本概念），每一个节点的存储都是连续的
知道当前下标为current
从0开始计数
左子树下标-->2*current+1
右子树下标-->2*current+2
从1开始计数
左子树下标-->2*current
右子树下标-->2*current+1
大顶堆
父亲的权值比左右子树的权值大
小顶堆
父亲的权值比左右子树的权值小
(小顶堆)
2
/ \
3 4
/\ /
8 7 6
（大顶堆）
8
/\
7 3
/\ /\
3 5 2 0
/
2
完全二叉树中间是不能有空的
(以下二叉树就不是完全二叉树)
8
/\
7 3
/\ /\
3 5 2 0
/ \
2 4
堆结构
//外堆
typedef struct Heap{
int* root;
int length;
}Heap;
(伪代码)
//入堆
void pushHeap(Heap* heap,int data);
//出堆
int popHeap(Heap* heap);
arr[MAXSIZE];
for(arr){
pushHeap(heap,arr[i])
}
for(heap){
arr[i]=popHeap(heap);
}
创建一个堆
Heap* creatHeap(int length){
Heap* heap=(Heap*)malloc(sizeof(Heap)*length);//开辟一个较大的内存空间
assert(heap);//断言一下
heap->length=0;//让length从0开始
heap->root=(int*)malloc(sizeof(int)*length);//开辟length长度的int数组，表示各个节点节点
assert(heap->root);
return heap;
}
//5 74 94 12 60 33 14
小顶堆
每拿一个数，放到底部，每次都要与父亲比较，小于父亲则与父亲替换
5(0)
/ \
12(1) 14(2)
/ \ / \
74(3)60(4)94(5)33(6)
//入堆
// 0 1 2 3 4 5 6 7 8
void pushHeap(Heap* heap,int data){
int current=heap->length++;
int parent=(current-1)/2;
heap->root[current]=data;
while(parent!=current){
if(heap->root[current]<heap->root[parent]){
swap(heap->root,current,parent);
current=parent;
parent=current/2;
}else
break;
}
}
拿走一个最小值，最后一个到第一个位置，再与左右子结点中比它小且二者中比较小的交换，直到回到再次满足小顶堆
33
/ \
12 14
/ \ /
74 60 94
12
/ \
33 14
/ \ /
74 60 94
//出堆
int popHeap(Heap* heap){
int val=heap->root[0];// 拿走一个最小值
int current=0;//从第一个位置开始
int rchild=2*current+2;//右子树（rchild-1为左子树）
int small;
int n=--heap->length;//最后一个位置
heap->root[0]=heap->roo[--heap->length];//将最后的数放到第一个位置上
while(rchild <= heap->length){
small=arr[rchild-1]<arr[rchild]?richild-1:rchild;
if(heap->root[small]<heap->root[current]){
swap(heap->root,small,current);//heap->root是一个指针开辟空间形成的数组
current=small;
rchild=2*(current)+2;
}
}else
break;
return val;
}
viod heapSort(int arr[],int length){
Heap *heap=creatHeap(MAXSIZE);
for(int i=0;i<MAXSIZE;i++){
pushHeap(heap,arr[i]);
}
for(inti=0;i<MAXSIZE;i++){
arr[i]=popHeap(heap);}
free(heap->root);
}
内堆实现
//不需要重新申请空间
heapify实现大顶堆
再将大顶堆的最大值逐渐放到最后一位上
最终实现从小到大有序的小顶堆
//heapify 堆化
void heapify(int arr[],int length,int current){
int rchild=2*current+2;
int large;
while(rchild<=length){
//若右子节点为length位置上的，然而length位置上没有元素，则意味着只有左子节点，在length-1上
//选子节点较大的元素
large=rchild==length?rchild-1:(arr[rchild-1]>arr[rchild]?rchild-1:rchild);
if(arr[large]>arr[current]){
swap(arr,large,current);//与比自己大的子节点交换，并更新位置，继续与子节点比较，直至找到合适的位置
current=large;
rchild=2*current+2;
}else
break;//如果找到合适的位置，则推出循环
//堆化就是将某一个位置的数按照大顶堆的方式，找到合适的位置
}
}
void heapSort2(int arr[],int length){
int current=length/2;//将除完全二叉树最后一层的叶子节点的数进行堆化
while(current>=0)//直到所有的数都完成堆化，则结束
{
heapify(arr,length,current);
current--;
}
showArr(arr,length);//输出arr所有元素
while(length>=0){
swap(arr,0,--length);//逐渐将大顶堆的最大值放到数组的后面，将最后一个数放到第一个位置
heapify(arr,length,0);
//然后对第一个位置上的数进行堆化，每次循环，length都减1，就把之前放到最后的最大值，给踢出对结构了，如此最大值便保留了下来，如此循环直到所有数都排好序
//形成从小到大的序列。
}
}
*/