手写堆排序

发布于:2021-07-20 04:37:14

若从小到大排序,把原有数组维护成一个大顶堆即可,注意从非叶子结点中的最后一个结点倒序遍历。


若二叉树结点下标从0开始,某个节点下标为k,则它的左右子节点的下标分别为2k+1,2k+2。 获得某个节点的父节点下标的方法为(idx+1)/2-1


若二叉树结点下标从1开始,某个节点下标为k,则它的左右子节点的下标分别为2k,2k+1,获得某个节点的父节点下标的方法为idx/2。


代码如下:


#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;


void adjust(vector &a, int idx,int size) {
int left = 2 * idx + 1;
int right = 2 * idx + 2;
while (left < size) {
int maxc = left; //记录左右子节点更大的那个下标
if (right< size&&a[right]>a[maxc])
maxc = right;
if (a[idx] < a[maxc]) {
swap(a[idx], a[maxc]);
idx = maxc;
left = 2 * idx + 1;
right = 2 * idx + 2;
}
else
break;
}
}

void heapSort(vector &a,int size) {
int idx = size / 2 - 1; //得到最后一个非叶子结点的下标
for (int i = idx; i >= 0; i--) { //从最后一个非叶子结点倒序遍历数组
adjust(a,i,size); //向下调整
}

int swapidx = size-1; //当前应该交换到的位置
for (int i = 0; i < size - 1; i++) {
swap(a[0], a[swapidx--]);
adjust(a, 0, swapidx + 1); //swapidx + 1表示大顶堆里的元素个数
}

}


int main() {

vectora = { 3,5,4,2,6,6,1,100,0,100 };
heapSort(a,a.size());

for (auto num : a) {
cout << num << " ";
}

return 0;
}

相关推荐

最新更新

猜你喜欢