堆排序

堆排序方法对于记录数较少的文件并不值得提倡，但对n较大的文件还是有效
运行时间主要耗费在：

1. 建立初始堆
2. 调整建立新堆 反复筛选

筛选算法进行的关键字比较次数至多为：$2(k-1)$
最坏情况O(nlogn),仅需一个记录大小供交换用的辅助存储空间

堆采用线性表表示
typedef SqList HeapType;
void HeadAdjust(HeapType &H,int s,int m){//已知H.r[s..m]中记录关键字除H.r[s].key之外均满足堆的定义//本函数调整H.r[s]的关键字，使H.r[s..m]成为一个大顶堆//s最大的非叶子节点 rc = H.r[s]; //辅助元素记录最大非叶子节点for(j=2*s;j<=m;j*=2){//2*s末尾元素//沿key较大的孩子结点向下筛选if(j<m && LT(H.r[j].key,H.r[j+1].key))++j;//j为key较大的记录的下标if(!LT(rc.key,H.r[j].key))break;//叶子节点大于等于非叶子节点，不需要调整（大根堆）//需要调整，将叶子节点和非叶子节点【已经记录】交换H.r[s]=H.r[j];s=j;}H.r[s]=rc;//插入元素}//HeadAdjustvoid HeadAdjust(int A[],int i,int m){//易懂版本A[0]=A[j];for(j=2*i;j<=m;j*=2){//2*s末尾元素//沿key较大的孩子结点向下筛选if(j<m && A[j]<A[j+1])++j;//j为key较大的记录的下标if(A[0]>=A[j])break;//叶子节点大于等于非叶子节点，不需要调整（大根堆）//需要调整，将叶子节点和非叶子节点【已经记录】交换A[i]=A[j];i=j;}A[i]=A[0];
}

void HeapSort(HeapType &H){//对顺序表H进行排序for(i=H.length/2;i>0;--i){HeapAdjust(H,i,H.length);//把H.r[1...H.length]建成大顶堆}for(i=H.length;i>1;--i){swap(H.r[1],H.r[i]);//将堆顶记录和当前未经排序子序列Hr[1...i]中//最后一个记录相互交换HeapAdjust(H,1,i-1);//将H.r[1..i-1]重新调整为大顶堆}
}//HeapSort

  最大堆：priority_queue<int, vector<int>, less<int>> maxHeap;最小堆：priority_queue<int, vector<int>, greater<int>> minHeap;如果使用 priority_queue<int> 创建堆，默认创建的是最大堆；最小堆会在一些图算法中应用，比如prim，dijkstra算法等，

链接

class Solution {
public:int mySqrt(int x) {if(x<=1)return x;int left=1,right=x/2;while(true){int mid = (left+right)/2;if(mid>0&&mid>x/mid)right=mid-1;else if((mid+1)>x/(mid+1))return mid;else left=mid+1;  }}
};

215 数组中第k个最大元素

方法一：利用快速排序进行划分

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {return divide(nums,0,nums.size()-1,nums.size()-k);}int divide(vector<int>& nums,int left,int right,int k){if(left==right)return nums[k];int partition = nums[left],i=left-1,j=right+1;while(i<j){while(nums[++i]<partition);while(nums[--j]>partition);if(i<j)swap(nums[i],nums[j]);}if(k<=j)return divide(nums,left,j,k);else return divide(nums,j+1,right,k);}
};