问题描述：假设某个数组中只有数字 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]
复制代码
