C++ 实现堆排序 | 您所在的位置:网站首页 › 堆排序从小到大排序 › C++ 实现堆排序 |
时空复杂度
时间复杂度
排序复杂度
O ( n l o g n ) O(nlogn) O(nlogn) 建堆复杂度O ( n ) O(n) O(n) 空间复杂度由于堆排序是一种就地设计的排序算法,空间需求是恒定的,所以是O(1) 稳定性不稳定。 C++代码(大根堆) class Solution { public: void adjust(vector&nums,int len,int index){ int left=2*index+1; int right=2*index+2; int maxid=index; if(leftnums[maxid]) maxid=left; if(rightnums[maxid]) maxid=right; if(maxid!=index){ swap(nums[maxid],nums[index]); adjust(nums,len,maxid); } } void HeapSort(vector&nums,int size){ for(int i=size/2-1;i>=0;i--){ adjust(nums,size,i); } for(int i=size-1;i>=1;i--){ swap(nums[0],nums[i]); adjust(nums,i,0); } } vector sortArray(vector& nums) { HeapSort(nums,nums.size()); return nums; } }; 运行结果 |
CopyRight 2018-2019 实验室设备网 版权所有 |