我们得到了一个字符串和一个整数。如果要将字符按排序顺序排列，我们必须判断字符串中整数位置的字符是什么。
例如
String = LALIT
Index = 3
Sorted string AILLT and the character at position 3 is L
不用排序就可以解决这个问题吗
如果是，那么是否有人可以提供伪代码。
是的，可以这样做。您正在寻找一种名为选择算法的东西，该算法给定元素列表和数字k，返回如果元素按排序顺序排列，哪个元素将位于k位置。令人惊讶的是，不需要对整个列表进行排序就可以做到这一点！
最简单的非排序选择算法被称为quickselect，它在预期时间O(n)内运行，并且如果允许修改原始数组，则只使用O(1)辅助存储空间。quickselect背后的想法是做一步快速排序——选择一个pivot元素，将元素划分为小于pivot的元素、等于pivot和大于pivot，然后看看会发生什么。如果在这一步之后，pivot元素最终位于k的位置，那么您就完成了——这是最终序列中位于k的位置，则递归地看向枢轴的左侧(k+最小的元素在其中的某个位置)，如果枢轴位于低于k，则递归性地看向轴心的右侧(k+th最小的元素位于其中的某一位置)。
其他方法也存在，例如中位数算法，它总是在最坏的O(n)时间运行，但却是一种经典的"难以理解的算法">