律师建网站,北京 高端网站设计,东莞市城建局,什么网站可以做卷子之前学习了堆#xff0c;堆的一棵以顺序结构存储的完全二叉树#xff0c;堆本身又氛围大根堆和小根堆#xff0c;假设以大根堆为例#xff0c;由于堆顶部元素是一棵二叉树里面最大的元素#xff0c;所以如果每次都取堆顶的元素#xff0c;那么取出的元素就是一个降序排列… 之前学习了堆堆的一棵以顺序结构存储的完全二叉树堆本身又氛围大根堆和小根堆假设以大根堆为例由于堆顶部元素是一棵二叉树里面最大的元素所以如果每次都取堆顶的元素那么取出的元素就是一个降序排列的序列。至此我们发现了一个堆的特别重要的一个应用就是堆排序。 目录
1 问题解析
2 算法分析
3 代码
4 时空复杂度分析
1 时间复杂度
2 空间复杂度 1 问题解析 堆排序顾名思义就是用堆结构来实现对一个数组的排序但是在排序过程中是不能使用堆这个数据结构的。如有一个数组 a[] {2, 4, 10, 9, 2, 3}通过堆排序这个排序算法之后数组 a 里面的数据变为了 a[] {2, 2, 3, 4, 9, 10} 升序排列或者是 a[] {10, 9, 4, 3, 2, 2} 降序排列。 2 算法分析 该算法共分为两步 1 首先对于给定的一个数组数组里面的数据都是乱序的既然是堆排序我们就需要先让该数组里面的数据变成一个堆将数组中的数据变成一个堆的算法为(这里是建大堆建小队逻辑类似) 这里利用的是向下调整算法因为向下调整算法的时间效率是比向上调整算法的时间效率高的上一篇文章有所讲解而向下调整算法又需要其左右子树各自都是一个堆所以首先选择最后一个节点作为孩子节点让其父亲向下调整这样最后一棵子树就变成了一个堆然后再以当前孩子节点的上一个节点作为下一个孩子节点让其父亲向下调整直至所有的子树都被调整为了一个堆。该过程如图所示 其本质就是从最小的一个子树建堆然后使子树规模依次扩大最后扩大为整棵树。 2数组建完堆之后由于堆顶数据总是最大的所以我们选择让堆顶数据和最后一个节点的数据进行交换这样最后一个数据就是有序的然后让交换后的堆顶数据再向下建堆但是注意这次建堆的范围应是 n - 1 个数据n 为数组中数据的个数那么当前我们执行完 n - 1 次该操作之后最大的 n - 1 个数据就会被升序的放到后 n - 1 个位置所以就实现了升序排列。该算法如图所示 通过理解该算法如果要排升序的话那么应该建大堆排降序的话应该建小堆。 3 代码
//升序的话建大堆降序的话建小堆
//这里升序排列
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void AdjustDown(int* arr, int parent, int n)
{int child 2 * parent 1;while (child n){if (arr[child 1] arr[child] child 1 n){child;}if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child 2 * parent 1;}else{break;}}
}//Heap是堆的意思Sort是排序的意思
void HeapSort(int* arr, int n)
{//先用所给的数组向下调整建一个堆for (int i (n-1-1)/2;i 0;i--){AdjustDown(arr, i, n);}//然后每次交换堆顶元素和最后一个元素让剩余元素建大堆int end n;while (end 0){//先交换Swap(arr[0], arr[--end]);//然后剩下元素建大堆AdjustDown(arr, 0, end);}
}
测试用例
void Test()
{int arr[] { 10, 9, 2, 4, 6, 11, 56, 20, 15, 19};int n sizeof(arr) / sizeof(arr[0]);HeapSort(arr, n);for (int i 0; i n; i){printf(%d , arr[i]);}
}int main()
{Test();return 0;
} 4 时空复杂度分析
1 时间复杂度 在上一篇文章中我们分析了向下调整算法的时间复杂度为 O(logn) 的而在堆排序里面共有两次循环第一次循环会执行 n/2 - 1 次第二次循环会执行 n 次而这两次循环里面都嵌套了向下调整算法所以时间复杂度为 O( (n/2 - 1)*logn nlogn)去除常数项和低阶项堆排序时间复杂度就是 O(nlogn)的。
2 空间复杂度 由于堆排序算法仅用了几个变量并为额外开辟空间所以空间复杂度为 O(1)。
