排序算法--堆排序

基本思想

堆排序的基本思想是，将待排序的元素构建成一个最大堆或最小堆。对于最大堆来说，堆顶是整个堆中的最大元素；对于最小堆来说，堆顶是整个堆中的最小元素。然后，将堆顶元素与堆中最后一个元素交换，并从堆中移除这个最大或最小元素，再调整剩余的堆，使其满足堆的性质。这个过程重复进行，直到堆中只剩下一个元素，此时数组就被排序了。

算法步骤

1. 构建最大堆：将待排序的数组从最后一个非叶子节点开始不断向前使用向下调整，使之成为一个最大堆。
2. 交换堆顶元素与堆尾元素：将堆顶元素（最大值）与堆中最后一个元素交换，此时最后一个元素即为最大值，放置在数组的正确位置。
3. 调整堆：交换后的堆可能不满足最大堆的性质，因此需要从堆顶开始重新调整堆。
4. 重复步骤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)，因此性能稳定。
• 空间效率高：由于是原地排序算法，不需要额外的内存空间。

缺点

• 实现复杂：相对于冒泡排序、插入排序等简单排序算法，堆排序的实现相对复杂。
• 不稳定性：堆排序不是一个稳定的排序算法，相等的元素可能在排序过程中改变它们的相对顺序。

总结来说，堆排序是一种高效、稳定的排序算法，适用于大规模数据的排序，尽管它的实现较为复杂。在实际应用中，堆排序常用于需要性能稳定且空间复杂度低的场景。