做推广能提高网站权重么,网站开发工具的功能包括哪些,淮北集团网站建设,wordpress返回堆排序的排序思想#xff1f; 堆排序是一种高效的排序算法#xff0c;其基本思想是利用堆这种数据结构来实现排序。堆是一种特殊的完全二叉树#xff0c;通常用数组来表示。堆排序的基本步骤如下#xff1a;
1. 构建初始堆#xff1a;
将待排序的数组转换成一个最大堆 堆排序是一种高效的排序算法其基本思想是利用堆这种数据结构来实现排序。堆是一种特殊的完全二叉树通常用数组来表示。堆排序的基本步骤如下
1. 构建初始堆
将待排序的数组转换成一个最大堆或最小堆。在最大堆中父节点的值总是大于或等于其子节点的值。转换过程从最后一个非叶子节点开始向上调整堆确保堆的性质。
2. 堆排序过程
将堆顶元素最大值或最小值与最后一个元素交换然后将剩余的元素重新调整为堆。重复上述过程每次将堆顶元素与当前未排序部分的最后一个元素交换并重新调整堆直到整个数组被排序。
3. 调整堆
每次交换后需要调整堆以保持堆的性质。调整过程从交换后的堆顶元素开始向下调整确保每个节点都满足堆的性质。
4. 循环结束
当所有元素都通过堆调整并交换到数组的前部时排序完成。
具体步骤
假设数组长度为n初始时数组为A[1…n]。将数组从后向前转换为最大堆 从最后一个非叶子节点开始即A[n/2]向下调整堆。每个节点向下调整时比较其值与其子节点的值如果当前节点的值小于其子节点的值则与较大的子节点交换。重复上述过程直到堆顶元素满足最大堆的性质。 将堆顶元素最大值与数组的最后一个元素交换然后重新调整堆。重复上述过程直到堆的大小减少到1。
时间复杂度
堆排序的时间复杂度为O(n log n)其中n是数组的长度。
空间复杂度
堆排序是原地排序算法不需要额外的存储空间因此空间复杂度为O(1)。
稳定性
堆排序不是稳定的排序算法因为相同的元素在排序过程中可能会交换位置。
代码
// 向下调整算法使以 parent 为根节点的堆满足大根堆性质
void AdjustDown(int* a, int parent, int n)
{assert(a);int child parent * 2 1;// 确保子节点不超过堆的大小while (child n){// 找到左右子节点中较大的一个if (child 1 n a[child] a[child 1]){child;}// 父节点小于较大子节点交换父子节点位置if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break; // 父节点已经大于等于子节点退出循环}}
}// 堆排序算法
void HeapSort(int* a, int n)
{// 升序排序建大根堆降序排序建小根堆for (int i (n - 1) / 2; i 0; i--) // 从最后一个非叶子节点开始向下调整{AdjustDown(a, i, n); // 向下调整以 i 为根节点的大根堆}int end n - 1;while (end 0){Swap(a[0], a[end]); // 将堆顶元素即最大值与堆末尾元素交换AdjustDown(a, 0, end); // 对新的堆顶进行向下调整使其满足大根堆性质--end; // 堆大小减 1排除已排序好的最大值}
}使用 priority_queue 实现
逆序
void heapSort(vectorint nums) {priority_queueint maxHeap;// 将数组元素插入最大堆中for (int num : nums) {maxHeap.push(num);}// 依次取出堆顶元素放入结果数组中逆序for (int i nums.size() - 1; i 0; --i) {nums[i] maxHeap.top();maxHeap.pop();}
}顺序
void heapSort(vectorint nums) {priority_queueint, vectorint, greaterint minHeap;// 将数组元素插入最小堆中for (int num : nums) {minHeap.push(num);}// 依次取出堆顶元素放入结果数组中顺序for (int i 0; i nums.size(); i) {nums[i] minHeap.top();minHeap.pop();}
}
