排序算法：

穩(wěn)定性：

穩(wěn)定的排序算法：基數(shù)排序，冒泡排序，直接插入排序，折半插入排序，歸并排序。
不穩(wěn)定的排序算法：快速排序，選擇排序，希爾排序，堆排序。

快排：

一次劃分會將一個元素pivot放置到最終的位置上。
時間復雜度：最好O(nlogn)，最差O(n^2)，一般為O(nlogn)。
空間復雜度：O(logn)。
穩(wěn)定性：不穩(wěn)定。

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;
        }

        //根節(jié)點
        res.push_back(cur->val);
        //左子節(jié)點
        dfs(cur->left);
        //右子節(jié)點
        dfs(cur->right);
    }
    
};

前序遍歷的遞歸寫法2：

class Solution
{
private:
    vector<int> res;
public:
    vector<int> preorderTraversal(TreeNode* root){
        if(root){
            //根節(jié)點
            res.push_back(root->val);
            //左子節(jié)點
            preorderTraversal(root->left);
            //右子節(jié)點
            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){
                    //添加右子節(jié)點
                    stk.push(node->right);
                }
                if(node->left){
                    //添加左子節(jié)點
                    stk.push(node->left);
                }
                //添加中節(jié)點
                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){
            //根節(jié)點
            res.push_back(node->val);
        }
        else{
            continue;
        }
        //右子節(jié)點進棧
        stk.push(node->right);
        //左子節(jié)點進棧
        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;
}