衡阳退休职工做面膜网站,专门做设计的一个网站,服务商平台登录,致远oa协同管理系统基本思想
堆排序的基本思想是#xff0c;将待排序的元素构建成一个最大堆或最小堆。对于最大堆来说#xff0c;堆顶是整个堆中的最大元素#xff1b;对于最小堆来说#xff0c;堆顶是整个堆中的最小元素。然后#xff0c;将堆顶元素与堆中最后一个元素交换#xff0c;并…基本思想
堆排序的基本思想是将待排序的元素构建成一个最大堆或最小堆。对于最大堆来说堆顶是整个堆中的最大元素对于最小堆来说堆顶是整个堆中的最小元素。然后将堆顶元素与堆中最后一个元素交换并从堆中移除这个最大或最小元素再调整剩余的堆使其满足堆的性质。这个过程重复进行直到堆中只剩下一个元素此时数组就被排序了。
算法步骤
构建最大堆将待排序的数组从最后一个非叶子节点开始不断向前使用向下调整使之成为一个最大堆。交换堆顶元素与堆尾元素将堆顶元素最大值与堆中最后一个元素交换此时最后一个元素即为最大值放置在数组的正确位置。调整堆交换后的堆可能不满足最大堆的性质因此需要从堆顶开始重新调整堆。重复步骤2和3重复上述过程每次都会将最大的元素放置在数组的正确位置直至数组完全有序。
示例代码从小到大
建堆有向上调整建堆和向下调整建堆两种使用向上调整建堆的时间复杂度为O(nlogn)而向下调整建堆的时间复杂度为O(n)所以我们选择向下调整建堆向下调整详细请看我发布的堆博客
向下调整
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
void AdjustDown(HPDataType* a, int n, int parent)//n为a数组元素个数
{int child (parent * 2) 1; // 左子节点位置假设法找大孩子while (child n) // 如果有左子节点进行循环{if (a[child] a[child 1] child 1 n) // 如果右子节点比左子节点大且右子节点存在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)//n为a数组元素个数
{// 建大堆for (int i (n - 2) / 2; i 0; i--){AdjustDown(a, n, i); // 向下调整堆}// 排序for (int i n - 1; i 0; i--){Swap(a[i], a[0]); // 交换堆顶元素和最后一个元素则最后一个元素为最大的元素AdjustDown(a, i, 0); // 向下调整堆让堆顶变为最大数}
}时间复杂度
堆排序的时间复杂度是O(nlogn)。构建最大堆的时间复杂度是O(n)每次调整堆的时间复杂度是O(logn)由于需要调整n-1次所以总的时间复杂度为O(nlogn)。
空间复杂度
堆排序的空间复杂度是O(1)。它是在原地进行排序的不需要额外的存储空间。
优点
性能稳定堆排序的时间复杂度在最好、最坏和平均情况下都是O(nlogn)因此性能稳定。空间效率高由于是原地排序算法不需要额外的内存空间。
缺点
实现复杂相对于冒泡排序、插入排序等简单排序算法堆排序的实现相对复杂。不稳定性堆排序不是一个稳定的排序算法相等的元素可能在排序过程中改变它们的相对顺序。
总结来说堆排序是一种高效、稳定的排序算法适用于大规模数据的排序尽管它的实现较为复杂。在实际应用中堆排序常用于需要性能稳定且空间复杂度低的场景。
