排序

快速排序

在数组中选定一个分界数pivot, 然后将所有其他的数和它进行比较，大于的小于的分成两部分，pivot放中间，这样这一轮就确定了一个数的位置，然后递归左右两边继续快排即可：

首先确定一个分界数：可以直接固定取最开始或者最后的那个数，也可以用随机算法。随机取数会使效率更加稳定。然后把这个数交换到 end，以便前面进行分块。
如何将大于和小于的两部分分开：我们目标是让小于的部分在前，大于的部分在后————两种分割方法：

一种是利用两个标志位，lo=start和hi=end-1，然后两个标志位互相把不该在自己这里的数丢给对方。 if (nums[lo]>pivot)，显然 nums[lo] 的值不应该在 lo 所处的小于区，因此我们把它丢到大于区swap(nums[lo],nums[hi]);hi--;。而 lo 获得了 hi 交换过去的数，大于小于性未知，lo 不能动。
另一种利用一个标志位和一个遍历位，即lo=start-1和cur=start。cur 从 start 遍历到 end-1 ，lo 指示着小于区的边界。我们只要把小于区分好，那么大于区自然就分好了。

if (nums[cur]<pivot) 即当前数应该添加到小于区，因此交换swap(nums[cur],nums[++lo]);。注意从 ++lo 换给 cur 的数必然是 cur 走过的，因此换完cur++即可。

分好区之后，把 pivot 放回到两区中间。
递归在两个分区里分别排序。

这里代码展示第一种分割方法，比较常见和经典。实现上需要注意 while 循环出口时，lo 和 hi 的停留位置

vector<int> sortArray(vector<int>& nums) 
{   
    //快速排序
    sortArrayHelp(nums,0,nums.size()-1);
    return nums;
}

void sortArrayHelp(vector<int>& nums,int start,int end)
{
    if(start>=end)
        return ;
    int pivot=nums[end];//end 为尾，不是尾后
    int lo=start,hi=end-1;
    while(lo<=hi)//出口时 lo 和 hi 重叠在 hi 区的第一个
    {
        if(nums[lo]>pivot)
        {
            swap(nums[lo],nums[hi]);//交换两数
            hi--;
        }
        else
            lo++;

    }

    swap(nums[lo],nums[end]);//注意 lo 的停留位置
    sortArrayHelp(nums,start,lo-1);
    sortArrayHelp(nums,lo+1,end);

}

不稳定。
时间复杂度最优 O(nlogn)，最差 O(n^2)。因为快排主要部分就是分区，分区好坏决定了递归树的深度O(log n) ~ O(n)，而递归树每一层的操作代价 O(n)。
空间复杂度即堆栈空间的大小，最优 O(log_2 n), 最坏 O(n), 平均 O(lg n)

堆排序

通过构建一个最大堆，这样从最大堆每次弹出 root，即可获得最大数，然后重新整理剩下的堆，循环类推：

构建最大堆，最大堆本身是二叉树结构，只不过维护了父结点比子节点大的特征。而二叉树本身也可以通过数组的形式实现，因此我们这里可以直接用数组实现最大堆。当然，另建数据结构也行，理解上会更简单点。
首先明确，在数组结构的二叉树中，i 结点的父结点是 (i-1)/2，子结点是 2i+1, 2i+2。对于每个结点，检查其是否比父结点大，是的话就换上去，同时递归往上检查，即往上冒泡。
取数时直接弹出根节点，同时临时拿末尾的数上来当根节点，并再逐层冒泡一个上来把它换下去。

实现时注意重建堆的细节，需要考虑到子节点是否越界，还有递归重建的终止条件是否正确。

vector<int> sortArray(vector<int>& nums) //堆排序
{   

    int length=nums.size();
    buildHeap(nums);
    // for(int i=0;i<length;i++)
    //     cout<<nums[i]<<' ';
    for(int end=length-1;end>0;end--)
    {
        //取出根，并临时拿end当根
        swap(nums[0],nums[end]);
        //维护新的根节点
        reBuildHeap(nums,0,end-1);
    }
    return nums;
}

void buildHeap(vector<int>& nums)
{
    int length=nums.size();

    for(int i=1;i<length;i++)
    {
        int child=i;
        int parent=(child-1)/2;
        while(parent>=0 && nums[parent]<nums[child])//注意 parent>=0 不是>0
        {
            swap(nums[parent],nums[child]);
            //递归往上更新
            child=parent;
            parent=(parent-1)/2; 
        }
    }
}

void reBuildHeap(vector<int>& nums,int root,int end)//弹出根后 重新整理 heap,end 为尾后
{
    //根的子节点索引
    int left=2*root+1;
    int right=left+1;

    int max=left;
    if(right<=end && nums[right]>nums[left])
        max=right;
    if(left<=end && nums[max]>nums[root])
    {
        swap(nums[max],nums[root]);
        reBuildHeap(nums,max,end);
    }

}

不稳定
时间复杂度 O(nlog n), 构建堆和重建堆时，每个元素都需要经历等于 O(log n) 层数 的比较，因此所有元素的代价是 O(nlog n)。
空间复杂度使用原数组构建堆时，O(1)。

冒泡排序

第 n 轮遍历，找出一个第 n 大，放在最后或最前，这样 n-1 轮下来即全部排好：

外层循环控制冒泡轮数
内层循环为每次遍历，假如当前的比后一个大，则交换，最终一轮走下来会冒泡出最大的一个。

vector<int> sortArray(vector<int>& nums) 
    {
        int length=nums.size();
        for(int i=length-1;i>0;i--)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[j]>nums[j+1])
                    swap(nums[j],nums[j+1]);
            }
        }

        return nums;
    }

稳定，不需要交换等值数
时间复杂度 O(n^2), 冒泡轮数固定，冒泡时比较次数也固定，因此 T(n)=n+n-1+...1=(1+n)*n/2=O(n)
空间复杂度 O(1), 不需要额外空间

归并排序

分治代表。先分别对左半边和右半边进行排序，然后再合并它俩的排序结果。

private void MergeSort(vector<int>& nums,int left,int right)
{
    if(left>=right)
        return;

    int mid=(left+right)/2;
    MergeSort(left,mid);
    MergeSort(mid+1,right);
    //合并
    vector<int> temp=new vector<int>(right-left);
    int i=left,j=mid+1;
    int temp_i=0;
    while(i<=mid && j<=right)
    {
        if(nums[i]<=nums[j])
            temp[temp_i]=nums[i++];
        else
            temp[temp_i]=nums[j++];
        temp_i++;
    }

    while(i<=mid)
        temp[temp_i++]=nums[i++];
    while(j<=right)
        temp[temp_i++]=nums[j++];
    //放回原数组
    for(int k=0;k<temp.length;k++)
        nums[left+k]=temp[k];
}

时间复杂度稳定\(O(n\log{n})\)，每轮合并操作需要\(O(n)\)，共有\(\log{n)\)轮。
空间复杂度\(O(n)\)
稳定

箱子排序/桶排序

将待排序数按规则划分成 N 类 (例如可按数值区间划分)，并分别用 N 个链表存储。然后对每个链表内部进行排序，最后把所有链表依次连接起来即完成排序：

private void bucketSort(vector<int>& nums)
{
    int bucket_size=100; //桶大小
    int min_num=max_num=nums[0];

    //找到数值范围
    for(auto num:nums)
    {
        min_num=min(min_num,num);
        max_num=max(max_num,num);
    }

    //初始化桶
    int count=(max_num-min_num+1);
    int bucket_count;//桶数量
    if(count%bucket_size==0)//整除
        bucket_count=count/bucket_size;
    else//非整除
        bucket_count=count/bucket_size+1;

    List<int>[] buckets=new List[bucket_count];

    //元素放入 List
    for(auto num: nums)
    {
        int index=(num-min)/bucket_size;//放入到 index 里
        if(buckets[index]==NULL)
            buckets[index]=new List<int>();
        
        buckets[index].add(num);
    }

    int length=nums.size();
    int i=0;
    
    //将元素放回原数组
    while(i<length)
    {
        for(auto bucket:buckets)
        {
            if(bucket==NULL)
                continue;
            else
            {
                //桶内部任意方法排序
                sort(bucket);
                for(auto num : bucket)
                {
                    nums[i]=num;
                    i++;
                }
            }
        }
    }

}

一般稳定 (与桶内排序方法有关)
空间复杂度 O(n),需要额外一份存储。
时间复杂度 O(k)+O(k * NlogN)。连接k个桶O(k)，桶内排序N个数O(N logN)。

希尔排序

类似于跨间隔的归并排序。先把数组跨步长分成多个子数组，分别插入排序。然后逐渐收缩步长，排序更大的子数组。

private void ShellSort(vector<int>& nums)
{
    int gap=nums.size()>>2;
    while(gap >0)
    {
        for(int i=0;i<gap;i++)//遍历每个子数组
        {
            for(int j=i+gap;j<nums.size();j+=gap)//
            {
                int temp_index=j;
                //子数组内部插入排序
                while(temp_index >i  && nums[temp_index]< nums[temp_index-gap])
                {
                    swap(nums[temp_index],nums[temp_index-gap]);
                    temp_index-=gap;
                }
            }
        }
        gap-=1;
    }
}

不稳定
时间复杂度\(O(n^{\frac{4}{3}})\) ~ \(O(n^2)\)
空间复杂度O(1)

其他简易排序

选择排序：每轮选出最大的一个，与数组末端的数交换位置。类似冒泡，只不过只交换一次。时间复杂度稳定\(O(n^2)\)。不稳定
插入排序：把排好的部分放在前端。每轮拿一个未排好的数去前端寻找插入点，时间复杂度\(O(n)\) ~ \(O(n^2)\)。稳定。
计数排序：特化的桶排序，以每个数字作为一个桶，统计所有数字的出现次数，然后批量写回，仅在数值差较小时有用。统计消耗\(O(n)\)，遍历统计数组写回原数组消耗\(O(delta)\)。空间复杂度\(O(delta)\)。
基数排序：特化的多轮桶排序，仅适用于数字排序。每轮桶分类规则分别为数字个位、十位、百位上的数字。时间复杂度\(O(n*k)\),排序k轮，每轮遍历所有n个数。其中k为数字位数。

参考资料

十二种排序算法包你满意（带 GIF 图解）

树相关

假定树结构如下：


 struct TreeNode 
 {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

递归思路很简单，只记录迭代思路。

前序遍历

先根，再左结点，再右结点。

vector<int> preorderTraversal(TreeNode* root) 
{
    vector<int> result;
    if(root==NULL)
        return result;
    
    stack<TreeNode*> s;
    s.push(root);
    while(!s.empty())
    {
        TreeNode * current=s.top();s.pop();
        result.push_back(current->val);
        if(current->right) s.push(current->right);
        if(current->left) s.push(current->left);
    }

    return result;
}

中序遍历

先左，再根，再右。

vector<int> inorderTraversal(TreeNode* root) 
{
    vector<int> result;
    if(root==NULL)
        return result;
    stack<TreeNode*> mem;
    TreeNode *current=root;
    //注意根节点也在里面压，而不是提前压好
    while(!mem.empty()||current)
    {
        //左节点压栈
        while(current)
        {
            mem.push(current);
            current=current->left;
        }


        current=mem.top();
        mem.pop();
        result.push_back(current->val);//输出子树根结点
        current=current->right;//进入当前子树右树
    }

}

后序遍历

先左，再右，最后根。

和中序遍历一样，首先要走到左树最深处。但是迭代很难控制从下一层返回上来的时候，不再压栈子结点，因此需要在第一次压栈时，断开根结点和子节点的链接。

取当前结点，先找左子树，左子树里面同样还要找左子树啊，因此是while找下去。
直至左子树为NULL，再找右子树，注意右子树里面优先找的是左子树，因此不能while持续找右子树，而是进入右子树后当作全新的树，再同样的查找。
迭代到某个结点后，左子树为NULL，右子树也为NULL，递归迭代停止，终于可以作为根结点进行输出了。

vector<int> postorderTraversal(TreeNode* root) 
{
    vector<int> result;
    if(root==NULL)
        return result;


    stack<TreeNode*> s;//递归栈
    TreeNode* current;//当前处理结点
    s.push(root);//初始化栈


    while(!s.empty())
    {
        
        current=s.top();//取结点
        root=current;//保留父结点，后续断开连接要用
        
        //先遍历这结点的左结点，左左结点，左左左...结点
        while(current->left)
        {
            s.push(current->left);
            current=current->left;
            root->left=NULL;//断开连接，避免返回到这个结点时又递归左树死循环
            root=current;
        }

        //走到最左端后，进入右子树。注意进入右子树后还是返回上面的步骤，优先找左子子树。
        if(current->right)
        {
            s.push(current->right);
            current=current->right;
            root->right=NULL;
            root=current;
        }
        else//左右子树都走完了，则可以输出自己了。
        {
            result.push_back(current->val);
            s.pop();
        }

    }

    return result;
}

层序遍历

即逐层的从左到右访问所有结点。值得考虑的是，怎么把每层结果分开？使用一个length在每层开始，检查队列长度获得该层长度，这样后面加入的子节点就不在长度范围内。

vector<vector<int>> levelOrder(TreeNode* root) 
{

    vector<vecotr<int>> result;
    if(root==NULL)
        return result;

    queue<TreeNode*> q;
    q.push(root);


    while(!q.empty())//队列不空
    {
        vector<int> temp;
        int length=q.size();//获取当前层结点
        TreeNode* current=q.front();q.pop();


        for(int i=0;i<length;i++)//分层计数
        {       
            if(current!=NULL)//当前为有效结点，加入result，检查子节点
            {
                temp.push_back(current->val);
                if(current->left) q.push(current->left);
                if(current->right) q.push(current->right);
            }

        }

        result.push_back(temp);

    }

    return temp
}

链表相关

判断链表是否有环

双指针————假如有环，快指针将迟早能和慢指针相遇

 bool hasCycle(ListNode *head) 
{
    if(head==NULL || head->next==NULL)//空链表或单结点
        return false;

    ListNode* fast=head;
    while(fast!=NULL)
    {
        //快慢指针移动
        fast=fast->next;
        if(fast!=NULL)
            fast=fast->next;
        head=head->next;

        //检查移动后是否相遇
        if(fast==head)
            return true;
    }

    return false;
}

寻找链表环的入口

参考题解

双指针————同上方法等待快慢指针相遇。

第一次相遇时：

环外距离 out ，也就是我们要找的
环内距离 in
环长 circle
慢指针走过的距离：len_s=out+in
快指针走过的距离：len_f= out+in+n*circle

因为len_f=2*len_s 推导出=>out + in = len_s = n*circle

此时把快指针置零，我们准备再让他俩走一遍直到相遇。

第二次相遇时：

设快指针走了 x 距离相遇，此时大家走过的总距离如下：

快指针走过的距离：len_f=x
慢指针走过的距离：len_s=x+n*circle

可以发现，当快指针刚到环入口，即x=out的时候，慢指针也恰好在环入口，只不过多走了n圈而已，此时他俩停留的地方即是环入口：

快指针走过的距离：len_f=out
慢指针走过的距离：len_s=out+n*circle

ListNode *detectCycle(ListNode *head) 
   {
       ListNode* fast=head,*slow=head;
       if(fast==NULL || fast->next==NULL)
           return NULL;
       while(fast && fast->next)//第一次相遇
       {
           fast=fast->next->next;
           slow=slow->next;

           if(fast==slow)
               break;
       }

       if(fast!=slow)//无环
           return NULL;

       //有环
       fast=head;
       while(fast!=slow)//第二次相遇
       {
           fast=fast->next;
           slow=slow->next;
       }

       return slow;
   }

翻转链表

不断将 head 后一个移到头部去。

利用一个 root 维护头部

ListNode* reverseList(ListNode* head) 
{
    ListNode* root=new ListNode(0);
    root->next=head;
    while(head && head->next)
    {
        ListNode* temp=head->next;//[1,2,3] 
        head->next=temp->next;//1 接上 2 的后续

        temp->next=root->next;//2 连上 头结点
        root->next=temp;//2 作为新的头结点

    }
    return root->next;
}

相交链表

找出两个链表的交点并返回。

假设：

链表 A 长度为 a，独有部分长度为 c。
链表 B 长度为 b，独有部分长度为 d。

可以知道a-c=b-d，变换一下则是a+d=b+c。即一个指针走完 A，再去走 B 的独有部分，和另一个指针走完 B，再去走 A 的独有部分，所需步数是相同的。换句话说，两个指针同时在两条链表上走，走到尾部就切换到隔壁链表上走，它们最终会在a+d和b+c的距离处相遇，也就是交点处相遇。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
{
    ListNode* rootA=headA,*rootB=headB;
    //注意移动和跳转的顺序 是先跳到 root 再移动？还是用跳跃取代移动？
    while(headA!=headB)
    {
        
        if(headA==NULL) 
            headA=rootB;
        else
            headA=headA->next;

        if(headB==NULL) 
            headB=rootA;
        else
            headB=headB->next;
    }
    if(headA==headB)
        return headA;
    else
        return NULL;

}

栈相关

最小栈的实现

需要实现一个能随时获取当前最小元素的栈。

题解思路

一开始想的是维护一个 int min，但是次小值之类的是无法维护的。首先我们来看看当前最小值是怎么更新的，假设当前最小值是 min_cur：

入栈一个比它大的值，那么此时栈当前最小不变。
在它上面的比它大的元素出栈，反正没 min_cur 小，因此出了也不影响栈当前最小=min_cur。
入栈一个比它小的值，那么栈当前最小更新到新值 min_new。而且在 min_new 上面的情景和 min_cur 一样，不用考虑了。
出栈 min_new，则最小值由 min_new 往下的接管，而我们直到 min_new 往下之前一直是 min_cur 管着最小值，因此又回到了 min_cur。

即核心操作是，判断当前入出栈的元素是不是比之前的最小值小。且最小值的更新有着后进先出的特性，后面更新的最小值，必然也会先被出栈，然后返回上一个最小值，因此考虑使用一个辅助栈。

辅助栈，存放有史以来的最小值记录，栈顶即当前状态最小值。假设当前最小值是 min_cur：

主栈入栈的元素比最小值大时，辅助栈保存的最小值保持不变，重复入栈一个 min_cur。
较小时，更新当前最小值，入栈一个 min_new。
出栈时，辅助栈跟随主栈相应出栈。

每日温度——单调栈

请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

题解思路

有点类似接雨水的题目，要在一系列顺序高度中，找到一个凹区间。且易知较矮的凹区间，必然包含在较高的凹区间内（最外层区间除外）。

换句话说，假如有 temperatures[i],temperatures[i+1] 两个气温：

temperatures[i+1] > temperatures[i]，则 i+1 就是 i 的新高温
temperatures[i+1] < temperatures[i]，则 i+1 的新高温肯定比 i 的新高温更先出现，即有点后进先出的特性，考虑用栈。

遍历 temperatures，并且维护一个栈：

如果当前元素比栈顶元素小，那么它的新高温肯定比栈顶元素先出现，因此压入栈顶。
如果当前元素比栈顶元素大，那么它可以作为栈顶元素的新高温，并且也可能是栈顶往下的元素的新高温，保持出栈，直到比当前栈顶元素小。

题解代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) 
    {
        stack<int> lower;//保存的是下标而不是值，便于下标相减
        vector<int> result(T.size(),0);//结果数组
        lower.push(0);
        for(int i=1;i<T.size();i++)
        {
            while(!lower.empty() && T[i]>T[lower.top()])//把所有比它小的出栈，并且计算差值
            {
                result[lower.top()]=i-lower.top();
                lower.pop();
            }

            lower.push(i);
        }

        return result;
    }
};

栈模拟队列

栈后进先出，队列先进先出，容易想到通过两个栈的负负得正实现。假设有 S1，S2 两个栈。S1 用来入队，S2 用来出队。

出队时，先把原 S1 栈里所有元素倒进另一个栈 S2，这样队首是在 S2 的顶部，即可出栈队首元素。入队时，先在S1压栈，等到S2没有元素了再倒过去用于出队。

中缀运算表达式转后缀表达式

准备两个栈，一个运算数栈，一个运算符栈。

从左到右依次扫描中缀表达式每个元素：

如果是'('，则入栈。
如果是')', 则持续出栈运算，直到出了一个'('。
是其他运算符，如果比栈顶运算符优先级高，压栈。如果比栈顶优先级低，则先出栈运算，再比较新的栈顶。

出栈运算：出栈一个运算符和两个运算数进行运算，把运算结果压回运算数栈。

Sitch's Blog

基础算法总结

排序

快速排序

堆排序

冒泡排序

归并排序

箱子排序/桶排序

希尔排序

其他简易排序

参考资料

树相关

前序遍历

中序遍历

后序遍历

层序遍历

链表相关

判断链表是否有环

寻找链表环的入口

翻转链表

相交链表

栈相关

最小栈的实现

题解思路

每日温度——单调栈

题解思路

题解代码

栈模拟队列

中缀运算表达式转后缀表达式