重要排序算法(更新ing)

堆排序核心思路构建堆的时候是从下到上的从一个个分支节点开始调整的。调整一个分支节点的时候需要与其最大max孩子结点做比较如果当前分支节点比max孩子小的话就交换由于交换可能会破坏max孩子子堆的最大堆性质所以需要继续朝着最大max孩子方向做调整直到遇到叶子节点。出堆的时候堆顶top之间出去然后用最后一个元素代替堆顶top然后从上至下的调整堆。非递归实现692. 前K个高频单词 - 力扣LeetCodeclass Solution { public: bool stringOrder(string a, string b){ //a和b肯定是不一样的 //a的字典序是否比b小呢 // 如果所有字符都相同则较短的字符串被认为更小。 int minLen min(a.size(), b.size()); for (int i 0; i minLen; i) { if (a[i] ! b[i]) { return a[i] b[i]; } } return a.size()b.size(); } void buildHeap(int node, vectorpairstring, int nums){ int n nums.size(); //把从node开始往下的所有分支结点都做调整 for(int i node; in/2-1;){ int max (i1)*2 - 1; //默认孩子节点里面最大的是左孩子 if(max1n){ //如果右孩子存在的话 //如果右孩子的次数比左孩子多的话那么就让max为右孩子 //或者如果右孩子与左孩子次数一样但是字典序比左孩子小的话 if(nums[max].secondnums[max1].second || (nums[max].secondnums[max1].second stringOrder(nums[max1].first, nums[max].first))) max max 1; } bool change false; //如果结点的次数比孩子max的次数要小的话 //如果次数一样但是max的字典序比node的小 if(nums[i].secondnums[max].second || (nums[i].secondnums[max].second stringOrder(nums[max].first, nums[i].first))){ change true; } if(change){ pairstring, int tmp nums[i]; nums[i] nums[max]; nums[max] tmp; i max; //就向max的方向继续调整 //如果max不是分支节点的话 那么它就会退出for循环 }else break; //当不需要change的时候 就说明这个堆没问题了就退出for } } string getTop(vectorpairstring, int nums){ pairstring, int top nums[0]; int n nums.size(); nums[0] nums[n-1]; //用最后一个元素代替第一个元素 nums.pop_back(); //删掉最后一个元素 if(nums.size()0) buildHeap(0, nums); //调整堆 return top.first; } vectorstring topKFrequent(vectorstring words, int k) { //构建字符串次数数组nums --- begin --- mapstring, int cnt; for(string tmp: words){ if(cnt.find(tmp)!cnt.end()){ cnt[tmp]; }else cnt[tmp]1; } vectorpairstring, int nums; for(auto [word, time]: cnt){ nums.emplace_back(pairstring, int(word, time)); } //--- end --- //从分支节点从下往上调整建立大根堆 --- begin --- int n nums.size(); for(int i n/2-1; i0; i--){ buildHeap(i, nums); } //--- end --- vectorstring res; while(k--){ res.emplace_back(getTop(nums)); } return res; } };递归实现347. 前 K 个高频元素 - 力扣LeetCodeclass Solution { public: void heap(int node, vectorpairint, int nums){ //王道书里面采用的for循环实现最大堆的调整 //我这里采用递归我感觉更好理解而且代码更少 if(nodenums.size()/2-1) return; //只允许分支节点操作 //因为索引是从0开始的 那么左孩子的索引应该是 (node1)*2-1 int max (node1)*2-1; //if(maxnums.size()) printf(%d , max); //max代表node的左右孩子里面最大的那个结点的索引 //默认是left if(max1nums.size()nums[max].secondnums[max1].second) max max 1; //如果有右孩子并且右孩子的值比左孩子大 //那么max right if(nums[node].secondnums[max].second){ //如果是孩子结点比node大 那么就交换值 int tmp nums[max].second; nums[max].second nums[node].second; nums[node].second tmp; int index nums[max].first; nums[max].first nums[node].first; nums[node].first index; heap(max, nums); //向调整的方向继续调整 } } int getHeapTop(vectorpairint, int nums){ int n nums.size(); int res nums[0].first; nums[0].first nums[n-1].first; nums[0].second nums[n-1].second; //用最后一个元素来替代第一个元素的位置 nums.pop_back(); //舍弃最后一个元素 if(nums.size()0) heap(0, nums);// 如果还有元素的话就调整堆 return res; } vectorint topKFrequent(vectorint nums, int k) { //首先要统计每个元素的出现次数 mapint, int cnt; for(int i: nums){ if(cnt.find(i)!cnt.end()){ cnt[i]; }else cnt[i] 1; } vectorpairint, int values; for (const auto [key, value] : cnt) { values.emplace_back(pairint, int(key, value)); } //基于堆排序实现 int n values.size(); //对所有的分支节点进行操作 for(int i n/2-1; i0; i--){ heap(i, values); } vectorint res; while(k--){ res.emplace_back(getHeapTop(values)); } return res; } };二路归并排序912. 排序数组 - 力扣LeetCodeclass Solution { public: void merge(vectorint nums, int low, int mid, int high) { // 合并两个有序的数组 vectorint res(nums); // 复制数组 int l, m; l low; m mid 1; int index l; while (l mid m high) { if (res[l] res[m]) { nums[index] res[l]; } else nums[index] res[m]; } while (l mid) nums[index] res[l]; while (m high) nums[index] res[m]; } // 下面是优化版本 // void merge(vectorint nums, int low, int mid, int high) { // vectorint tmp(high - low 1); // 1. 只申请这段区间 // int l low, r mid 1, idx 0; // while (l mid r high) // tmp[idx] (nums[l] nums[r]) ? nums[l] : nums[r]; // while (l mid) // tmp[idx] nums[l]; // while (r high) // tmp[idx] nums[r]; // for (int i 0; i idx; i) // 2. 拷回原数组对应位置 // nums[low i] tmp[i]; // } void twoRoad(vectorint nums, int low, int high) { if (low high) { int mid (low high) / 2; twoRoad(nums, low, mid); twoRoad(nums, mid 1, high); merge(nums, low, mid, high); } } vectorint sortArray(vectorint nums) { twoRoad(nums, 0, nums.size() - 1); return nums; } };快速排序int sort(vectorint nums, int left, int right){ int base nums[left]; while(leftright){ while(leftrightnums[right]base) --right; nums[left] nums[right]; while(leftrightnums[left]base) left; nums[right] nums[left]; } nums[left] base; return left; } void fastSort(vectorint nums, int left, int right){ if(leftright){ int p sort(nums, left, right); fastSort(nums, left, p-1); fastSort(nums, p1, right); } }