快速排序

#include <bits/stdc++.h>
using namespace std;
// 快速排序的 partition 函数
int partition(vector<string>& arr, int low, int high) {
	string pivot = arr[high];  // 选择最后一个元素作为基准
	int i = low - 1;	
	// 遍历数组，将小于基准的元素移到左边，大于基准的移到右边
	for (int j = low; j < high; j++) {
		if (arr[j] < pivot) {  // 字典序比较
			i++;
			swap(arr[i], arr[j]);
		}
	}	
	swap(arr[i + 1], arr[high]);  // 将基准元素放到正确的位置
	return i + 1;
}
// 快速排序的递归函数
void quickSort(vector<string>& arr, int low, int high) {
	if (low < high) {
		int pi = partition(arr, low, high);  // 获取基准元素的正确位置
		quickSort(arr, low, pi - 1);  // 排序左边部分
		quickSort(arr, pi + 1, high);  // 排序右边部分
	}
}
int main() {
	string input;
	getline(cin, input);  // 读取整行输入	
	vector<string> words;
	string word;
	bool inWord = false;	
	// 处理输入，按空格分割单词，并去重
	for (char c : input) {
		if (c != ' ') {
			word += c;
			inWord = true;
		} else if (inWord) {
			words.push_back(word);
			word = "";
			inWord = false;
		}
	}
	if (inWord) {  // 最后一组单词
		words.push_back(word);
	}	
	// 使用快速排序进行排序
	quickSort(words, 0, words.size() - 1);	
	// 输出排序后的单词
	for (const string& w : words) {
		cout << w << endl;
	}	
	return 0;
}