题解 | #c++ 小半天的劳动成果，炒鸡易懂，不懂提刀来见我#

class Solution {
public:
    /***********字典序法解决全排列 给研究排序的人员致敬 致以我的respect********/
    /*算法链接： https://blog.csdn.net/qq_34672688/article/details/79557380?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.no_search_link&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.no_search_link*/
    /*算法1：
     *   （1）从右向左找出第一个正序(即当前元素小于后一个元素)，假设找到的元素为
     *list[start] == a.
     *    (2) 重新从右向左找出第一个大于a的元素，并假设当前元素为 list[end] == b
     *    (3) 交换list[start]和list[end]
     *   （4） 将start后面的序列从小到大排列
     *   （5）此时的序列为一次新排列，将它储存，并进行下一次排列
     *方法2:
     *     直接使用库函数：
     *      bool  next_permutation(last,end) 实现方法可能与上述相同
     *        功能：计算下一个字典序列
     *      bool prev_permutarion(last,end) 
     *        功能：计算上一个字典序列
     */   
    vector<string> Permutation(string str) {
        return myPermutation(str);
    }
    vector<string> myPermutation(string str){
         /*先将当前序例推进去，算作一次排列*/
        int start = 0;int end = 0;
        vector<string> result; 
        result.push_back(str);
        sort(str.begin(), str.end());
        while(1){
            /*（1）找出list[start],返回start*/
            start = findStart(str);
            if(start == -1){
                break;
            }
            /* (2)找出list[end],返回end*/
            end = findEnd(str,str[start]);
            if(end == -1){
                break;
            }
            /* (3)交换list[start],list[end]*/
            swap(str[start],str[end]);
            /* (4)对start+1-末尾进行排序*/
            /*    4.1 快排     */
            qucikSort(str,start+1, str.size()-1);
            /*    4.2 sort排序  */
            /*string::iterator it = str.begin()+start+1;
            if(it != str.end()){
                sort(it,str.end());
            }*/
            /* (5)储存结果,进行下一次排序*/
            result.push_back(str);
        }
        return result;
    }
    int findStart(string s){
        for(int i = s.size()-1;i>=1;i--){
            if(s[i-1] < s[i]){
                return i-1;
            }
        }return -1;
    }int findEnd(string s,char ch){
        for(int i = s.size()-1;i>=1;i--){
            if(s[i] > ch){
                return i;
            }
        }return -1;
    }void qucikSort(string& s,int start,int end){
        if(end > s.size()-1 || start > end){
            return;
        }else{
            char cmp = s[end];
            int pos = start-1;
            for(int i =start;i<=end;i++){
                if(s[i] < cmp){
                    swap(s[i],s[++pos]);
                }
            }swap(s[++pos],s[end]);
            qucikSort(s,start,pos-1);
            qucikSort(s,pos+1, end);
        }
    }
    
};