排序算法：

稳定性：

稳定的排序算法：基数排序，冒泡排序，直接插入排序，折半插入排序，归并排序。
不稳定的排序算法：快速排序，选择排序，希尔排序，堆排序。

快排：

一次划分会将一个元素pivot放置到最终的位置上。
时间复杂度：最好O(nlogn)，最差O(n^2)，一般为O(nlogn)。
空间复杂度：O(logn)。
稳定性：不稳定。

void quick_sort(vector<int>& nums, int L, int R){
        if (L < R){
            int i = L;
            int j = R;
            int pivot = nums[L];
            while (i < j)
            {
                while (i < j && nums[j] >= pivot){
                    j--;
                }
                if (i < j){
                    nums[i] = nums[j];
                    i++;
                }
                while (i < j && nums[i] < pivot){
                    i++;
                }
                if (i < j){
                    nums[j] = nums[i];
                    j--;
                }
            }
            nums[i] = pivot;
            quick_sort(nums, L, i - 1);
            quick_sort(nums, i + 1, R);
        }
    }   

遍历二叉树：

前序遍历二叉树

前序遍历的递归写法1：

class Solution
{
private:
    vector<int> res;
public:
    vector<int> preorderTraversal(TreeNode* root){
        dfs(root);
        return res;
    }

    void dfs(TreeNode* cur){
        if(cur == NULL){
            return;
        }

        //根节点
        res.push_back(cur->val);
        //左子节点
        dfs(cur->left);
        //右子节点
        dfs(cur->right);
    }
    
};

前序遍历的递归写法2：

class Solution
{
private:
    vector<int> res;
public:
    vector<int> preorderTraversal(TreeNode* root){
        if(root){
            //根节点
            res.push_back(root->val);
            //左子节点
            preorderTraversal(root->left);
            //右子节点
            preorderTraversal(root->right);
        }
        return res;
    }    
};

前序遍历的迭代写法1：

vector<int> preorderTraversal(TreeNode* root){
        std::vector<int> res;
        stack<TreeNode*> stk;
        if(root != NULL){
            stk.push(root);
        }
        while(!stk.empty()){
            TreeNode* node = stk.top();
            if(node != NULL){
                stk.pop();
                if(node->right){
                    //添加右子节点
                    stk.push(node->right);
                }
                if(node->left){
                    //添加左子节点
                    stk.push(node->left);
                }
                //添加中节点
                stk.push(node);
                stk.push(NULL);
            }
            else{
                stk.pop();
                node = stk.top();
                stk.pop();
                res.push_back(node->val);
            }
        }
        return res;
    }

前序遍历的迭代写法2：

vector<int> preoederTraversal(TreeNode* root){
    vector<int> res;
    stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty())
    {
        TreeNode* node = stk.top();
        stk.pop();

        if (node != NULL){
            //根节点
            res.push_back(node->val);
        }
        else{
            continue;
        }
        //右子节点进栈
        stk.push(node->right);
        //左子节点进栈
        stk.push(node->left);
    }
    return res;
}

中序遍历二叉树

中序遍历的递归写法1：

vector<int> res;
vector<int> midorderTraversal(TreeNode* root){
    dfs(root);
    return res;
}
void dfs(TreeNode* root){
    if (root == NULL){
        return;
    }
    dfs(root->left);
    res.push_back(root->val);
    dfs(root->right);
}

中序遍历的递归写法2：

vector<int> midorderTraversal(TreeNode* root){
    vector<int> res;
    if (root){
        midorderTraversal(root->left);
        res.push_back(root->val);
        midorderTraversal(root->right);
    }
    return res;
}

中序遍历的迭代写法1：

vector<int> midorderTraversal(TreeNode* root){
    vector<int> res;
    stack<TreeNode*> stk;
    if (root != NULL){
        stk.push(root);
    }
    while (!stk.empty()){
        TreeNode* node = stk.top();
        if (node){
            stk.pop();
            if (node->right){
                stk.push(node->right);
            }

            stk.push(node);
            stk.push(NULL);

            if (node->left){
                stk.push(node->left);
            }
        }
        else{
            stk.pop();
            node = stk.top();
            stk.pop();
            res.push_back(node->val);
        }
    }
    return res;
}

中序遍历的迭代写法2：

vector<int> midorderTraversal(TreeNode* root){
    vector<int> res;
    stack<TreeNode*> stk;
    TreeNode* cur = root;
    
    while (cur || !stk.empty()){
        if (cur){
            stk.push(cur);
            cur = cur->left;
        }
        else{
            cur = stk.top();
            stk.pop();
            res.push_back(cur->val);
            cur = cur->right;
        }
    }
    return res;
}

后序遍历二叉树

后序遍历的递归写法1：

vector<int> res;
vector<int> postorderTraversal(TreeNode* root){
    dfs(root);
    return res;
}

void dfs(TreeNode* root){
    if (root == NULL){
        return;
    }

    dfs(root->left);
    dfs(root->right);
    res.push_back(root->val);
}

后序遍历的递归写法2：

vector<int> postorderTraversal(TreeNode* root){
    vector<int> res;
    if (root){
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        res.push_back(root->val);
    }
    return res;
}

后序遍历的迭代写法1：

vector<int> postorderTraversal(TreeNode* root){
    vector<int> res;
    stack<TreeNode*> stk;
    if (root != NULL){
        stk.push(root);
    }

    while (!stk.empty()){
        TreeNode* node = stk.top();
        if (node != NULL){
            stk.pop();

            stk.push(node);
            stk.push(NULL);

            if (node->right){
                stk.push(node->right);
            }

            if (node->left){
                stk.push(node->left);
            }
        }
        else{
            stk.pop();
            node = stk.top();
            stk.pop();
            res.push_back(node->val);
        }
    }
    return res;
}

后序遍历的迭代写法2：

vector<int> postorderTraversal(TreeNode* root){
    vector<int> res;
    stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty()){
        TreeNode* node = stk.top();
        stk.pop();
        if (node){
            res.push_back(node->val);
        }
        else{
            continue;
        }       
        stk.push(node->left);
        stk.push(node->right);
    }
    reverse(res.begin(), res.end());
    return res;
}