月度归档： 2021 年 5 月

堆排序将数组看成一个二叉堆，对于序号为i的节点，第2*i+1和第2*i+2为它的子节点

最大堆，堆顶节点的元素比所有其他节点的元素都大的堆称为最大堆

void heapSort(int* array,int size)
{
    if(size<=1)
        return;
    int maxidx=size-1;
    int i=maxidx%2;
    if(i==0)
        i=(maxidx-2)/2;
    else
        i=(maxidx-1)/2;
    for(;i>=0;i--)
    {
        if((2*i+1)<=maxidx&&array[i]<array[2*i+1])
        {
            swap(array+i,array+(2*i+1));
        }
        if((2*i+2)<=maxidx&&array[i]<array[2*i+2])
        {
            swap(array+i,array+(2*i+2));
        }
    }
    swap(array,array+maxidx);
    heapSort(array,size-1);
}

排序原理

将数组看成一个二叉堆

1.构造最大堆.

2.堆顶元素排除

3 循环1，2直到剩余元素无法构造堆，排序完成

构造最大堆的方法

从最后一个非叶子节点向前遍历开始，如果子节点比当前节点大，将当前节点与子节点交换。遍历完成后最大的元素会被移动到堆的根节点，成为最大堆。

void qsort(int* array,int size)
{
    if(size<=1)
        return;
    int* pEnd=array+size-1;
    int* pBegin=array;
    while(pEnd!=pBegin)
    {
        while(*pEnd>=*pBegin&&pEnd>pBegin)
            --pEnd;
        if(pEnd==pBegin)
            break;
        swap(pEnd,pBegin);
        pBegin++;
        while(*pEnd>=*pBegin&&pEnd>pBegin)
            ++pBegin;
        if(pEnd==pBegin)
            break;
        swap(pEnd,pBegin);
        pEnd--;
    }
    int front_part=pEnd-array;
    qsort(array,front_part);
    qsort(pEnd+1,size-front_part-1);

}

快速排序，简单来说就是找数组中的一个元素为基准，通过只遍历数组一边的方法，将数组调整成，基准值左边所有元素都不大于基准值，基准值右边所有元素都不小于基准值的状况。然后递归的将基准值左右的两个子数组调整成这种状况。以实现数组的排序

调整的方法:

1.将数组首元素作为基准值

2.从数组未被遍历的部分的尾部向前遍历，找到一个比基准值小的元素，将他与基准值交换位置

3.从数组未被遍历部分的头部向后遍历，找一个比基准值大的元素，将他与基准值交换

4 经过一轮2，3后，左侧被遍历过的位置都保存着不比基准值大的元素，而右侧被遍历过的位置都保存着不比基准值小的元素。循环2，3直到所有的位置都被遍历过，此时基准值左边的值都不大于基准值，而基准值右侧的元素都不小于基准值

后天有个面试，要带笔记本电脑，可是我没笔记本电脑，😓，应该是要现场编码，有点紧张，刷个简单的leetcode

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        if(numRows==0)
            return res;
        res.emplace_back(vector<int>{1});
        for(int i=2;i<numRows+1;i++)
        {
            res.emplace_back(vector<int>{1});
            auto& lastvec=res[res.size()-2];
            auto& thisvec=res.back();
            for(int j=0;j<i-2;j++)
            {
                  thisvec.push_back(lastvec[j]+lastvec[j+1]);  
            }
            thisvec.push_back(lastvec.back());
        }
        return res;
    }
};

中间有个取vector中的上一个行的 auto& lastvec=res[res.size()-2];，这个原本写再了vector::emplace_back之前，引发了异常，才注意到，由于vector在插入元素后内存的位置可能会变化，导致之前的引用不在有效。因此将取上一行引用的代码移动到了emplace_back之后