题目地址：

https://www.lintcode.com/problem/string-sorting/description

给定一个以逗号分隔开的单词组成的字符串，单词只由小写字母构成。要求返回同样以逗号分隔开的单词组成的字符串，单词按字典序排序。

用快速排序。代码如下：

public class Solution { /** * @param s: string * @return: sort string in lexicographical order */ public String sorting(String s) { // write your code here // 按逗号分隔开 String[] ss = s.split(","); quickSort(ss, 0, ss.length - 1); // join回去并返回 return String.join(",", ss); } private void quickSort(String[] ss, int l, int r) { if (l >= r) { return; } swap(ss, l, l + (r - l >> 1)); String piv = ss[l]; int i = l, j = r; while (i < j) { while (i < j && ss[j].compareTo(piv) >= 0) { j--; } ss[i] = ss[j]; while (i < j && ss[i].compareTo(piv) <= 0) { i++; } ss[j] = ss[i]; } ss[i] = piv; // 递归排序左右半边 quickSort(ss, l, i - 1); quickSort(ss, i + 1, r); } private void swap(String[] ss, int i, int j) { String tmp = ss[i]; ss[i] = ss[j]; ss[j] = tmp; } }

时间复杂度$O(ln\log n)$，空间$O(\log n)$，$n$为单词数量，$l$为单词最长长度。