排序算法—堆排序

x33g5p2x  于11个月前 转载在 其他  
字(0.8k)|赞(0)|评价(0)|浏览(130)

算法稳定性:不稳定

复杂度分析:

  • 空间复杂度:O(1)
  • *时间复杂度:O(n/logn)

实现代码:

#include<iostream>
using namespace std;
//堆排序(大根堆,从小到大排序)

//调整堆
void HeapAdjust(int *nums,int x,int n) {

	nums[0] = nums[x]; //nums[0]暂存子树的根节点

	for (int i = 2 * x;i <= n;i *= 2) {

		if (i < n && nums[i] < nums[i + 1])
			i++;
		if (nums[0] >= nums[i]) {
			break; //如果根节点的元素大于左右两颗子树的元素则无需交换
		}else {
			nums[x] = nums[i];
			x = i;
		}
	}
	nums[x] = nums[0]; //将最初子树根节点元素存放在最终x的位置

}

//构建大根堆
void BuildMaxHeap(int* nums, int n) {
	
	for (int i = n / 2;i >= 1;i--) { //从后往前调整所有非叶子节点
		HeapAdjust(nums, i, n);
	}

}

//堆排序
void HeapSort(int* nums, int n) {

	BuildMaxHeap(nums, n); //建大根堆

	for (int i = n;i > 1;i--) {
		swap(nums[1], nums[i]); //堆顶元素和堆底元素交换
		HeapAdjust(nums, 1, i-1); //交换后再调整堆
	}

}

int main() {

	int nums[155];
	int n;
	cin >> n;
	
	for (int i = 1;i <= n;i++)
		cin >> nums[i];

	HeapSort(nums, n); //堆排序

	cout << "排序后序列为:";
	for (int i = 1;i <= n;i++)
		cout << nums[i] << " ";

	return 0;
}

运行结果:

在这里插入图片描述

相关文章