东莞莞城建筑工程有限公司,seo站长工具查询系统,上海在线做网站,网站建设q-9堆排序即利用堆的思想来进行排序#xff0c;总共分为两个步骤#xff1a; 1. 建堆 升序#xff1a;建大堆 降序#xff1a;建小堆
原因分析#xff1a;
若升序建小堆时间复杂度是O(N^2) 升序建大堆#xff0c;时间复杂度O#xff08;N*logN#xff09; 所以升序建大堆…堆排序即利用堆的思想来进行排序总共分为两个步骤 1. 建堆 升序建大堆 降序建小堆
原因分析
若升序建小堆时间复杂度是O(N^2) 升序建大堆时间复杂度ON*logN 所以升序建大堆降序建小堆 2. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。
代码实现
#includestdio.h//交换函数
void Swap(int* px, int* py)
{int tmp *px;*px *py;*py tmp;
}
//向下调整算法
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child child * 2 1;}else{break;}}
}
void HeapSort(int* a, int n)
{//建堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}
int main()
{int a[] { 0,4,3,6,7,8,1 };HeapSort(a, sizeof(a) / sizeof(int));return 0;
}
运行结果 若是建小堆则只需要把向下调整中的改成,修改后如下
if (child 1 n a[child 1] a[child])
{child;
}
if (a[child] a[parent])
{Swap(a[child], a[parent]);parent child;child child * 2 1;
}
运行结果 当然我们也可以先写一个堆的数据结构再进行堆排序但是这显然不如上面的快速且节省空间
自主实现数据结构堆再进行堆排序
代码实现
#pragma once
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.h
#includestring.htypedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
//初始化
void HPArrayInit(HP* hp, HPDataType* a, int n);
//销毁
void HPDestroy(HP* hp);
// 堆的插入
void HPPush(HP* hp, HPDataType x);
// 堆的删除
void HPPop(HP* hp);
// 取堆顶的数据
HPDataType HPTop(HP* hp);
// 堆的数据个数
int HPSize(HP* hp);
// 堆的判空
int HPEmpty(HP* hp);
//向上调整算法
void Adjustup(HPDataType* a, int child);
//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);void HPArrayInit(HP* hp, HPDataType* a, int n)
{assert(hp);hp-a (HPDataType*)malloc(sizeof(HPDataType) * n);if (hp-a NULL){perror(malloc fail);return;}memcpy(hp-a, a, n * sizeof(HPDataType));hp-size hp-capacity n;//向上调整,建堆时间复杂度O(N*logN)for (int i 1; i hp-size; i){Adjustup(hp-a, i);}//向下调整建堆时间复杂度O(N)for (int i (hp-size - 1 - 1) / 2; i 0; i--){AdjustDown(hp-a, hp-size, i);}
}
//销毁
void HPDestroy(HP* hp)
{assert(hp);hp-size hp-capacity 0;free(hp-a);hp-a NULL;
}
//交换函数
void Swap(HPDataType* px, HPDataType* py)
{HPDataType tmp;tmp *px;*px *py;*py tmp;
}
//向上调整算法
void Adjustup(HPDataType* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (parent - 1) / 2;//找原本父亲的父亲下标}else{break;}}
}
// 堆的插入
void HPPush(HP* hp, HPDataType x)
{assert(hp);//扩容if (hp-size hp-capacity){int newcapacity hp-capacity 0 ? 4 : 2 * hp-capacity;HPDataType* tmp (HPDataType*)realloc(hp-a, sizeof(HPDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}hp-a tmp;hp-capacity newcapacity;}hp-a[hp-size] x;Adjustup(hp-a, hp-size - 1);
}
//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child child * 2 1;}else{break;}}
}
// 堆的删除
void HPPop(HP* hp)
{assert(hp);assert(hp-size 0);Swap(hp-a[0], hp-a[hp-size - 1]);hp-size--;AdjustDown(hp-a, hp-size, 0);
}
// 取堆顶的数据
HPDataType HPTop(HP* hp)
{assert(hp);return hp-a[0];
}
// 堆的数据个数
int HPSize(HP* hp)
{assert(hp);return hp-size;
}
// 堆的判空
int HPEmpty(HP* hp)
{assert(hp);return hp-size 0;
}
void HeapSort(int* a, int n)
{HP hp;HPArrayInit(hp, a, n);int i 0;while (!HPEmpty(hp)){a[i] HPTop(hp);//将堆顶数据放入数组中HPPop(hp);//再已放入数组中的堆顶数据删除}HPDestroy(hp);
}
int main()
{int a[] { 60,70,65,50,32,100 };HeapSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i){printf(%d , a[i]);}return 0;
}
运行结果 欢迎各位大佬一起学习交流~
