当前位置：首页 > news >正文

排序算法--堆排序

news 2025/8/14 7:21:14

基本思想

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

算法步骤

构建最大堆：将待排序的数组从最后一个非叶子节点开始不断向前使用向下调整，使之成为一个最大堆。
交换堆顶元素与堆尾元素：将堆顶元素（最大值）与堆中最后一个元素交换，此时最后一个元素即为最大值，放置在数组的正确位置。
调整堆：交换后的堆可能不满足最大堆的性质，因此需要从堆顶开始重新调整堆。
重复步骤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); // 向下调整堆，让堆顶变为最大数}
}