Question

对数组中的数字 1 和 2 进行排序，使得数字 1、2 分别位于前、后部分

Answer 1

问题描述：假设某个数组中只有数字 1 和 2，进行排序，使得数字 1 位于数组前部分，数字 2 位于后部分。

这道算法题其实不是很难，使用各种排序算法应该都能解出，但是若要考虑性能问题，那就得选择一种算法复杂度最低的解法。这里我使用双指针的方法来解答该题，时间复杂度为 O(n) 。

（1）设置一个头指针、一个尾指针，头指针首先指向数组的第一个元素（索引为 0），而尾指针则指向数组的最后一个元素（索引为 len - 1，假定数组的长度为 len）；
（2）然后比较这两个一前一后元素的大小：

（3）接着再次比较头、尾指针指向元素的大小，决定是否交换值以及移动指针；
（4）依照以上步骤进行指针移动、元素大小比较，便可使得数字 1 位于数组前部分，数字 2 位于数组后部分。