证明做二维码打款网站链接,qq网页版输入账号登录,百度seo哪家公司好,网站建设满意度调查问卷1.前言
在学习这篇文章之前#xff0c;请大家先学习堆这一数据结构中堆的概念#xff0c;向下调整算法#xff0c;向下调整建堆。
有关堆的实现方式请参考#xff1a;堆的实现
堆排序就是利用堆里面学习过的知识点进行排序#xff0c;如何进行排序呢#xff1f;
2.堆…1.前言
在学习这篇文章之前请大家先学习堆这一数据结构中堆的概念向下调整算法向下调整建堆。
有关堆的实现方式请参考堆的实现
堆排序就是利用堆里面学习过的知识点进行排序如何进行排序呢
2.堆排序原理剖析
现在我们要对一个无序的数组升序排列那么我们应该利用大堆还是小堆进行排序呢
这时我们大家就会想既然是升序排列那么我们建一个小堆不就可以了吗刚好小堆的第一个元素是最小的元素。
建小堆可行性分析
好那么我们现在来思考一下这种方法的可行性。
现在我们给出如下一个小堆。 现在我们可以确保根节点是最小的了下面我就就要从第二层选最小的数了这里我们选到了右子树2但是根结点的左右两棵子树之间是没有联系的我们应该如何判决左子树8和右子树2的子树们的关系呢这时就需要我们遍历才能确定大小关系了而后续的每一次比较都需要这么一个过程。时间复杂度就变的相当高了。若如此建堆堆排序就是一个理解起来困难而时间复杂度又高的离谱的排序方法了。
建大堆可行性分析
既然建小堆不可以那么建大堆应该如何排序呢又有没有优势呢
首先我们可以确定的一点是大堆的堆顶一定是一整个堆中最大的元素。
但是我们排的是升序最大的一个应该在堆的最后面才对那么我们直接交换堆顶元素和堆尾元素的位置不就可以让堆的最后一个元素是最大的了嘛。 这时新的问题是我们的交换破坏了堆原来的结构那么这时我们需要做的工作则是恢复堆原来的结构。这不就是我们的向下调整算法所能做的事嘛因此我们每次交换了之后用一个向下调整算法即可。 3.堆排序代码详细阐述
我们首先完成第一次交换和向下调整
int endn-1;//n是数组长度
swap(arr[0], arr[end]);
AdjustDown(a, end, 0);
下面我们要做的事情即将数组内所有的元素都按照这种方式进行排序这就需要我们将上述代码嵌套进一个循环内而由于此时最后一个元素已经是最大的了因此我们需要剔除掉这个元素在这里我们直接让end-1即可。
while (end0)
{swap(arr[0], arr[end]);AdjustDown(a, end, 0);end--;
}
上述代码即可完成一次堆排序。
而由于我们传进来的数组的元素是无序的因此我们首先需要将其调整为堆之后再进行上述操作即可完成堆排序。
void AdjustDown(HPDataType * a, int n, int parent)
{// 先假设左孩子大int child parent * 2 1;while (child n)// 当childn时就说明child已经到达叶子节点了{// 先找出左右孩子节点中大的那个if (child 1 n 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)
{// 降序建小堆// 升序建大堆for (int parent (n - 1 - 1) / 2; parent 0; parent--){AdjustDown(a, n, parent);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}
4.堆排序时间复杂度分析
初始化堆的时间复杂度为O(n) n-1次删除操作的时间复杂度为O(nlogn) 所以总操作时间复杂度为O(nlogn)
由于每删除一个元素总元素减一。 共有n-1次删除操作操作时间应该为log(n)log(n-1)…log(3)log(2) log(n!)。 又由于(n/2)^(n/2) ≤ n≤ n ^ n,即 1/4*nlog(n) ≤ n! ≤ nlogn。常数可舍去时间复杂度为O(nlogn)
