问题描述：假设某个数组中只有数字 1 和 2，进行排序，使得数字 1 位于数组前部分，数字 2 位于后部分。
这道算法题其实不是很难，使用各种排序算法应该都能解出，但是若要考虑性能问题，那就得选择一种算法复杂度最低的解法。这里我使用双指针的方法来解答该题，时间复杂度为 O(n)。
- 解法步骤
（1）设置一个头指针、一个尾指针，头指针首先指向数组的第一个元素（索引为 0），而尾指针则指向数组的最后一个元素（索引为 len - 1，假定数组的长度为 len）；
（2）然后比较这两个一前一后元素的大小；
- 若两值不相等，则较小的 1 放在前面，较大的 2 放在后面，头指针往后移动一步，尾指针向前移动一步；
- 若两值相等且都等于 1，则头指针往后移动一步，尾指针不移动；
- 若两值相等且都等于 2，则尾指针往前移动一步，头指针不移动；
（3）接着再次比较头、尾指针指向元素的大小，决定是否交换值以及移动指针；
（4）依照以上步骤进行指针移动、元素大小比较，便可使得数字 1 位于数组前部分，数字 2 位于数组后部分。
-
注意点：上面循环进行操作的条件是头指针索引值小于尾指针索引值。
-
书写的代码如下：
function sortOneTwoInArr (arr) { var len = arr.length; var head = 0; var tail = len - 1; /* 遍历数组，对 1 和 2 进行排序 */ while (head < tail) { // 若头、尾指针指向的元素大小相等则只移 // 动一个指针，否则同时移动两个指针 if (arr[head] === arr[tail]) { if (arr[head] === 1) { head++; } else if (arr[head] === 2) { tail--; } } else { if (arr[head] > arr[tail]) { [arr[head], arr[tail]] = [arr[tail], arr[head]]; } head++; tail--; } } return arr;}/* 测试用例 */var arr1 = [];var arr2 = [1];var arr3 = [2];var arr4 = [1, 2, 1, 2];var arr5 = [1, 1, 2, 2];var arr6 = [1, 2, 2, 1, 1];var arr7 = [2, 2, 1, 1, 2];console.log(sortOneTwoInArr(arr6)); // [1, 1, 1, 2, 2]复制代码