怎么样百度能搜到自己的网站,云建站推荐,长春网络公司招聘,网站建设管理规范参考#xff1a; 面试官#xff1a;请写一个堆排序_哔哩哔哩_bilibiliC实现排序算法_c从小到大排序-CSDN博客 堆的基本概念 堆排实际上是利用堆的性质来进行排序。堆可以看做一颗完全二叉树。 堆分为两类#xff1a; 最大堆#xff08;大顶堆#xff09;#xff1a;除根… 参考 面试官请写一个堆排序_哔哩哔哩_bilibiliC实现排序算法_c从小到大排序-CSDN博客 堆的基本概念 堆排实际上是利用堆的性质来进行排序。堆可以看做一颗完全二叉树。 堆分为两类 最大堆大顶堆除根节点外堆的每个父节点都大于其孩子节点。最小堆小顶堆除根节点外堆的每个父节点都小于其孩子节点。最大堆和最小堆示意图 数据结构包含逻辑结构和存储结构对于堆来说 堆的逻辑结构是完全二叉树堆的存储结构可以是链式存储也可以是顺序存储。在堆排序中我们基于的存储结构是顺序存储。顺序存储示意图以最大堆为例
堆排序
堆排序主要分为三个步骤 建堆交换数据重复步骤1,2 建堆。首先说说建堆因为我们要对数组进行排序这个数组里元素原本的排列是无规则的为了能通过堆对数组进行排序我们需要进行“建堆”操作从而使得数组的排序符合堆的要求。根据上文可知堆可以分为两种一种是最大堆另一种是最小堆。既然有两种堆我们应该基于哪种类别来建堆呢这就要取决于我们的排序形式了如果是升序从小到大则需要建最大堆如果是降序从大到小则需要建最小堆。以下都以升序建最大堆为例。交换数据。交换什么数据呢这里直接给出结论是交换堆数组索引为0的元素和末尾元素堆的最后一个元素。因为我们已经建好堆了且我们堆的存储结构是顺序结构即根节点只最大的节点存储在数组的第一位索引为0这是我们将这个数与数组最后一个数交换位置就完成了数组中最大元素的排序因为最大的元素肯定在数组最后一个位置。交换完数据后对于新的堆新的二叉树来说是不满足最大堆的条件的因为发生了位置交换这时就需要重新建堆重新建堆有别于初次建堆因为我们已经固定了最大元素的位置所以之后建堆不应该让这个最大的元素参与进来。参考代码如下 最大堆建堆
/*** 堆化* 大根堆大顶堆/最大堆小的数往下沉*/
void maxHeapify(vectorint nums, int pos, int len)
{// (pos 1) 1就是2*pos1对应该节点的左子节点// (pos 1) 2就是2*pos2对应该节点的右子节点int child (pos 1) 1;while (child len){if (child 1 len nums[child 1] nums[child]){child child 1;}if (nums[pos] nums[child]){return;}else{swap(nums[pos], nums[child]);pos child;child (pos 1) 1;}}
}最小堆建堆
/*** 堆化* 小根堆小顶堆/最小堆大的数往下沉*/
void minHeapify(vectorint nums, int pos, int len)
{// (pos 1) 1就是2*pos1对应该节点的左子节点// (pos 1) 2就是2*pos2对应该节点的右子节点int child (pos 1) 1;while (child len){if (child 1 len nums[child 1] nums[child]){child child 1;}if (nums[pos] nums[child]){return;}else{swap(nums[pos], nums[child]);pos child;child (pos 1) 1;}}
}堆排序
/*** 堆排序*/
void heapSort(vectorint nums)
{// 每次交换完数据后要len--让排序好的元素不参与建堆for (int len nums.size(); len 0; len--){// (len - 2) 1就是len-2)/2这样能找到最后一个非叶子结点for (int i (len - 2) 1; i 0; i--){minHeapify(nums, i, len);// 最小堆建堆对应降序// maxHeapify(nums, i, len);// 最大堆建堆对应升序}// 每进行一次交换就要重新堆化且重新堆化时堆的大小要对应减1因为堆末尾的元素已经排好序了swap(nums[0], nums[len - 1]);}
}堆排序测试用例
#include iostream
#include vectorusing namespace std;/*** 堆化* 大根堆大顶堆/最大堆小的数往下沉*/
void maxHeapify(vectorint nums, int pos, int len)
{int child (pos 1) 1;while (child len){if (child 1 len nums[child 1] nums[child]){child child 1;}if (nums[pos] nums[child]){return;}else{swap(nums[pos], nums[child]);pos child;child (pos 1) 1;}}
}/*** 堆化* 小根堆小顶堆/最小堆大的数往下沉*/
void minHeapify(vectorint nums, int pos, int len)
{int child (pos 1) 1;while (child len){if (child 1 len nums[child 1] nums[child]){child child 1;}if (nums[pos] nums[child]){return;}else{swap(nums[pos], nums[child]);pos child;child (pos 1) 1;}}
}/*** 堆排序*/
void heapSort(vectorint nums)
{for (int len nums.size(); len 0; len--){for (int i (len - 2) 1; i 0; i--){minHeapify(nums, i, len);// 最小堆建堆对应降序// maxHeapify(nums, i, len);// 最大堆建堆对应升序}// 每进行一次交换就要重新堆化且重新堆化时堆的大小要对应减1因为堆末尾的元素已经排好序了swap(nums[0], nums[len - 1]);}
}int main(int argc, char const *argv[])
{vectorint nums {5, 3, 2, 63, 56, 8, -1, 3, 0, -222};heapSort(nums);for (auto num : nums){cout num ;}cout endl;return 0;
}
