警告該文章涉嫌嚴重的標題黨，博主膽小怕事歡迎狂噴
個人喜歡將堆排序設計為三個層次分三個函式層層遞進實作
1.將一個區域的堆（二叉堆）實作大根堆
解釋一些概念
(1)二叉堆：將元素（這里不嚴謹的指代所有實數）按照二叉樹的結構以陣列下標映射的方式存盤，
對于每個元素，我們關心其與子節點間的大小關系(如果存在)
對于陣列下標為i的元素(從0開始)
其左子節點的下標(若存在)
lt = 2 * i + 1;
其右子節點的下標為(若存在)
rt = 2 * i + 2;
(2)大根堆
對于每個結點，其相對于左右子節點的值，為最大(隱含著根節點為區域大根堆最大值)
習慣上我們會建成一個完全二叉樹形式的大根堆
補充完廢話，直接上代碼決議一哈
void maxHeapify(vector<int> & nums, int i, int heapSize)
{ //heapSize = nums.size();
int lt = 2 * i + 1, rt = 2 * i + 2, largest = i;
//lt,rt說過了不談，largest我們用來動態存盤三個結點之間的最大值(當前結點i與其左右子節點)
if (lt < heapSize && nums[lt] > nums[largest]) {largest = lt;}
if (rt < heapSize && nums[rt] > nums[largest]) {largest = rt;}
if (largest != i) //如果最大值不為當前結點
{
swap(nums[i], nums[largest]); //交換兩個結點的位置
maxHeapify(nums, largest, heapSize);//小值下濾
}
}
2.實作建立全域的大根堆
從第一個非葉結點開始，向上遍歷將最大值放到根的位置
void buildMaxHeap(vector<int> & nums, int heapSize)
{
for (int i = heapSize / 2; i >= 0; --i)
{
maxHeapify(nums, i, heapSize);
}
//對于每次遍歷，我們利用1中實作的子程序，實作了以當前結點為根的區域大根堆的構建，在下一次遍歷中，其會作為子節點與新的上面的根作比較
}
3.初始化大根堆及每次遍歷將元素"插入"對應位置
這里所說的插入實際上是對于第i次遍歷，我們把當前全域大根堆根值與第i大元素應該存在的位置上的元素做交換
void HeapSort(vector<int> & nums)
{
int heapSize = nums.size();
buildMaxHeap(nums, heapSize);
for (int i = nums.size() - 1; i >= 0; --i) //從大到小排序
{
//第i次遍歷構建區域大根堆然后將區域大根堆最大值與末端位置元素做交換并放到第i大的元素的位置
swap(nums[0], nums[i]);
heapSize -= 1;
maxHeapify(nums, 0, heapSize);
}
}
總體代碼
void maxHeapify(vector<int> & nums, int i, int heapSize)
{
int lt = 2 * i + 1, rt = 2 * i + 2, largest = i;
if (lt < heapSize && nums[lt] > nums[largest]) {largest = lt;}
if (rt < heapSize && nums[rt] > nums[largest]) {largest = rt;}
if (largest != i)
{
swap(nums[i], nums[largest]);
maxHeapify(nums, largest, heapSize);
}
}
void buildMaxHeap(vector<int> & nums, int heapSize)
{
for (int i = heapSize / 2; i >= 0; --i)
{
maxHeapify(nums, i, heapSize);
}
}
void HeapSort(vector<int> & nums)
{
int heapSize = nums.size();
buildMaxHeap(nums, heapSize);
for (int i = nums.size() - 1; i >= 0; --i) //從大到小排序
{
//第i次遍歷構建區域大根堆然后將區域大根堆最大值與末端位置元素做交換并放到第i大的元素的位置
swap(nums[0], nums[i]);
heapSize -= 1;
maxHeapify(nums, 0, heapSize);
}
}
int main(void)
{
HeapSort(nums);
//略
}
讀者閱讀實作后，可以嘗試完成leetcode板子題ac進行練習
977.有序陣列的平方
睡了睡了
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/257477.html
標籤：其他
下一篇：1208.盡可能使字串相等