题解 | #字符串内排序#

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

void swap(char &a, char &b){
    char temp = a;
    a = b;
    b = temp;
}

int partition(string &str, int low, int high);

void quickSort(string &str, int low, int high);

int main() {
    string str = "bacd";
    cin >> str;
    quickSort(str, 0, str.size() - 1);
    cout << str;
}
int partition(string &str, int low, int high){
    int i = low, j = high, pivot = str[low];
    while(i < j){
        //先使用j从右往左遍历，再使用i从左往右遍历。顺序不可以颠倒。
        while(i < j && str[j] >= pivot) j--;
        while(i < j && str[i] <= pivot) i++;
        swap(str[i], str[j]);
    }
    //while结束时，i指向的元素一定小于等于str[low]，交换str[i]和str[low]。
    swap(str[i], str[low]);
    return i;
}

void quickSort(string &str, int low, int high){
    if(low >= high) return;
    int mid = partition(str, low, high);
    quickSort(str, low, mid - 1);
    quickSort(str, mid + 1, high);
}
// 64 位输出请用 printf("%lld")