快排,堆排与归并排序
2020-12-13 02:59
标签:快排 adjust 个数 时间复杂度 EAP 空间复杂度 pad 时间 序列 快排: Parition函数用于进行一次快排,本次快排将某个元素放在它应该呆在的位置pos。pos左侧全比它小,pos右侧全比它大。 Parition中,设置low指针与high指针,以待排元素为标杆,判断high指向元素是否大于待排元素,若小于则与low指向的元素交换,并切换到low指针。low指针此时指向刚交换过来的元素,其一定小于待排元素,然后low自加直到low指向的元素大于待排元素,此时再与high指向的元素交换,high指向的元素为之前一次low - high交换前low指向的元素; 最后直到low==high,对该待排元素的排列完成。 进行n此Parition即可得到一个完整的排序序列。 堆排: 设计HeapAdjust函数,这个函数用于调整s~m元素使之遵守堆的规则。假设是传进来的数组中只有s位置的元素不满足堆的规则。 HeapAdjust首先找到2*s的位置处,2*s为s的子节点,首先比较s的两个子节点的大小,选一个较大的子节点,若s比它大,则符合堆规则,若比它小,交换他们两个的位置。然后在以s的新位置开始向下调整。 堆排时,首先需要调整为一个大顶堆,从最后一个非子节点的子树开始,一个子树一个子树的向上调整。 调整完后,成为一个大顶堆。然后将顶部元素挪到最后,这样最大的元素已经确定了。在到第一个和第n-1个元素间进行HeapAdjust。。。。 n次后排序完毕。 归并排序: 用递归的思想,对n个数的数组。首先分割成两部分,各一半,然后对每一半做归并排,排完后将这两个数组合并。 即 Msort(0,n/2); Msort(n/2+1,n-1); Merge(); 总结: 快排: 时间复杂度:O(nlogn) 空间复杂度:O(logn) 堆排: 时间复杂度:O(nlogn) 空间复杂度:O(1) 归并排序: 时间复杂度:O(nlogn) 空间复杂度:O(n) 快排,堆排与归并排序 标签:快排 adjust 个数 时间复杂度 EAP 空间复杂度 pad 时间 序列 原文地址:https://www.cnblogs.com/lxy-xf/p/11063812.html