赣州互联网哪家好,想找搜索引擎优化,电商平台网址,福州网站建设制作前言#xff1a;我们已经学习了堆以及实现了堆#xff0c;那么我们就来给堆进行排序。我们怎么来进行排序呢#xff1f;这一次我们就来解决这个问题。 如果我们堆排序要求排序#xff0c;我们是建立大堆还是小堆呢#xff0c;如果我们建的小堆的话#xff0c;那我们在排序… 前言我们已经学习了堆以及实现了堆那么我们就来给堆进行排序。我们怎么来进行排序呢这一次我们就来解决这个问题。 如果我们堆排序要求排序我们是建立大堆还是小堆呢如果我们建的小堆的话那我们在排序的时候就给不断地进行建堆那么我们的时间复杂度就会很大如果我们建立大堆的话最大的数就在堆顶如果我们要给接下来的排序我们要求排升序的话我们的大堆就可以很简单的解决这个问题我们只需要把堆顶的数和最后一个数进行交换在不断地进行向下调整就可以了。时间复杂度就很小所以我们排升序就建立大堆。
建立大堆
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;//while (parent 0)while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;//child (child - 1) / 2;//parent (parent - 1) / 2;}else{break;}}
}void AdjustDown(HPDataType* a, int size, int parent)
{int child parent * 2 1;while (child size){// 假设左孩子小如果解设错了更新一下if (child 1 size a[child 1] a[child]){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)
{//建大堆//O(N*logN)for (int i 1; i n; i){AdjustUp(a, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}我们的end是最后一个元素下标是前面的元素的个数我们就让它与堆顶元素交换在向下调整调整完之后就让end–也就是堆顶与下标为n-2的元素交换在进行调整反复操作知道end0结束。 我们建立大堆的代码还可以改进优化到时间复杂度为O(N)
void HeapSort(int* a, int n)
{//建大堆/*O(N)*/for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}因为我们的父节点下标为子节点下标减去1再除以2所以我们可以直接利用循环传参的是父节点的下标所以我们的这个方法是先从最下面的父节点开始调整最后在调整下标为0的父节点。 接下来我们就来测试我们代码
int main()
{int a[] { 4, 6, 2, 1, 5, 8, 2, 9 };HeapSort(a, sizeof(a)/sizeof(int));for (int i 0; i sizeof(a)/sizeof(int); i){printf(%d , a[i]);}printf(\n);return 0;
}最后就成功的将排序后的堆打印出来就可以了。感谢大家的支持
