花了兩天時間搞明白答案的快速排序和堆排序。
兩種都寫了一遍，感覺堆排序更簡單很多。
兩種都記錄一下，包括具體方法和易錯點。
快速排序
class Solution {
public:vector<int> nums;int quicksort(int left,int right,int k){if(left==right) return nums[k];int r=right;int mid=left;left--;right++;while(left<right){do left++; while(nums[left]<nums[mid]);do right--; while(nums[right]>nums[mid]);if(left<right) swap(nums[right],nums[left]);}if(right>=k) return quicksort(mid,right,k);else return quicksort(right+1,r,k);}int findKthLargest(vector<int>& nums, int k) {this->nums=nums;return quicksort(0,nums.size()-1,nums.size()-k);}
};具體方案：定下首個元素的值為mid，設置雙指針分別指向首個元素的前一位、最后一個元素的后一位，當左指針在右指針左邊時，移動左指針到第一個大于mid的位置，移動右指針到第一個小于mid的位置，若左指針在右指針左邊，則交換兩者元素，循環以上。
循環最終結果：左指針指向從左往右第一個大于mid的元素，右指針指向從右往左第一個小于mid的元素，且左指針不在右指針左邊。
（選擇排序做法）繼續遞歸右指針往右部分的數組和右指針往左部分的數組。
（這道題做法）若右指針的位置在k右邊，則遞歸右指針往左部分，否則遞歸右指針往右部分。
初寫時犯了不少錯誤，也有很多問題：
錯誤一：最后將mid移至left的位置
一開始的想法是mid既然是中間就要移到中間的位置，然后若mid正好在k的位置就可以直接返回mid，這樣做很麻煩并且不一定正確。
錯誤二：將雙指針分別設在首個元素的后一位、最后一個元素
這樣做會忽略掉一些元素，這樣的話循環就不能先do再while了，可能會陷入死循環，總之比較麻煩。
錯誤三：最終以左節點作為分割線
大概就是把
if(right>=k) return quicksort(mid,right,k);else return quicksort(right+1,r,k);寫成了：
if(left>=k) return quicksort(mid,left-1,k);else return quicksort(left,r,k);其實現在也不是很明白為什么不能以左節點分割，我想可能是因為左指針最開始還要先經過mid，多了一次停留。
總之以后寫快排的時候注意這幾個地方就好了。
堆排序
堆排序做這題會更簡單。
之前不知道堆是什么，現在才知道是一種二叉樹，大根堆就是將大的數作為根節點。
class Solution {
public:void adjustheap(vector<int>& nums,int root){int left=root*2+1;int right=root*2+2;int maxx=root;if(left<nums.size()&&nums[left]>nums[maxx]) maxx=left;if(right<nums.size()&&nums[right]>nums[maxx]) maxx=right;if(maxx!=root){swap(nums[maxx],nums[root]);adjustheap(nums,maxx);}}void initheap(vector<int>& nums){for(int i=nums.size()/2-1;i>=0;i--){adjustheap(nums,i);}}int findKthLargest(vector<int>& nums, int k) {initheap(nums);for(int i=0;i<k-1;i++){nums[0]=-10001;adjustheap(nums,0);}return nums[0];}
};這些函數包括初始化大根堆、調整大根堆的過程。
大根堆就是一個數組，只不過邏輯結構是二叉樹，所以不用建樹那些過程
初始化大根堆：
從最后一個非葉子節點（nums.size()/2-1）開始調整大根堆。
調整大根堆：
輸入root節點，比較root和左右節點，最大的節點若不是root則和root交換，然后遞歸調整最大那個節點。
這道題不需要進行堆排序，只要構建完大根堆不斷刪除最頂節點k-1步即可。
