上海建设工程安全质量监督站网站,淘宝推广方式,wordpress 阅读数插件,一个网站一年要多少钱目录 前言
概念
堆排序的实现
1.建堆 #xff08;1#xff09;堆向上调整算法
#xff08;2#xff09;堆的向下调整算法
2. 利用堆删除思想来进行排序
3.堆排序的时间复杂度
4.源码
总结 前言
前边我们学习了堆的实现#xff0c;对堆的每个接口都进行了详细的讲…目录 前言
概念
堆排序的实现
1.建堆 1堆向上调整算法
2堆的向下调整算法
2. 利用堆删除思想来进行排序
3.堆排序的时间复杂度
4.源码
总结 前言
前边我们学习了堆的实现对堆的每个接口都进行了详细的讲解所以这篇文章就来看一看堆到底有哪些应用。 概念 堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法 大顶堆每个节点的值都大于或等于其子节点的值在堆排序算法中用于升序排列小顶堆每个节点的值都小于或等于其子节点的值在堆排序算法中用于降序排列堆排序的平均时间复杂度为 Ο(nlogn)。 我们之前学习的冒泡排序的时间复杂度为o(n^2),此处的堆排序确是Ο(nlogn)这样直接看并不能看出堆排序的优势如果我们使用数字代入就会发现如果我们有1000个数进行排序时冒泡排序是100万次若是堆排序只需1万次对于更大的数差别也会更大所以堆排序是很有优势的。
堆排序的实现 1.建堆
我们根据上节课的学习我们知道了向上调整算法和向下调整算法他们都可以建立一个堆。
我们要切记需要升序排列时要建一个大堆需要降序排列时要建一个小堆。 1堆向上调整算法 现在我们给出一个数组逻辑上看做一颗完全二叉树。我们从第二个位置向上调整直到最后一个位置的数为止。
void hpSort(int* a, int n)
{assert(a);//从第二个数开始向上调整for (int i 1; i n; i){adjustUp(a, i);}
} 2堆的向下调整算法 现在我们给出一个数组逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。 有人可能认为向下调整算法的时间复杂度为o(n*log2n),其实并不是时间复杂度其实为o(n)由于在倒数第二层时每个元素只调整了一次倒数第三层调整了两次也可以通过数学公式来证明通过错位相减法最终得到了向下调整算法的时间复杂度为o(n)。 void hpSort(int* a, int n)
{assert(a);//从非叶子结点开始向下调整for (int i (n-1)-1/2; i 0; i--){adjustDown(a, n, i);}
} 从非叶子结点开始调整可以从最后一个结点的父节点处开始进行向下调整直至调整到根节点。 2. 利用堆删除思想来进行排序 1当我们要对数据进行降序排列时我们先建立一个小堆即父节点的数据小于子节点的数据。 2将最后一个结点与第一个结点互换此时得到的最后一个结点的数据就是最小的数。 3此时对第一个结点向下调整使其恢复成为一个小堆此时堆顶元素就是整个堆中次小的数。 4此时我们把最后一个结点与原来结点分离只是看作分离只是将其余结点从新进行之前的操作直至堆的大小为1。 void hpSort(int* a, int n)
{assert(a);//从第二个数开始向上调整/*for (int i 1; i n; i){adjustUp(a, i);}*///从非叶子结点开始向下调整for (int i (n-1)-1/2; i 0; i--){adjustDown(a, n, i);}for(int endn - 1 ; end 0 ; end--){swap(a[0], a[end]);adjustDown(a, end ,0);}
} 3.堆排序的时间复杂度 我们知道了向下调整算法来建堆的时间复杂度为o(n),所以我们选择向下调整算法来建堆在建完堆之后我们就进行交换并且向下调整排序的时间复杂度为on*log2n所以总和的时间复杂度为o(n*log2n)。 4.源码 hpsort.c void hpSort(int* a, int n)
{assert(a);//从第二个数开始向上调整/*for (int i 1; i n; i){adjustUp(a, i);}*///从非叶子结点开始向下调整for (int i (n-1)-1/2; i 0; i--){adjustDown(a, n, i);}for(int endn - 1 ; end 0 ; end--){swap(a[0], a[end]);adjustDown(a, end ,0);}
} test.c void test1()
{//TestTopk();int a[] { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 };for (int i 0; i sizeof(a) / sizeof(a[0]); i){printf(%d , a[i]);}printf(\n);hpSort(a, sizeof(a) / sizeof(a[0]));for (int i 0; i sizeof(a) / sizeof(a[0]); i){printf(%d , a[i]);}printf(\n);} 总结 今天我们学习了堆排序的概念实现以及时间复杂度过两天我会继续发布关于各种排序的文章希望大家支持。
