java - 不允许对元素进行计数的排序算法

Question

这道题我在某公司面试中看到过crosss，但是我对这道题首先不是很清楚。你们能澄清我的疑问吗？

Question : Write a program to sort an integer array which contains Only 0's,1's and 2's. Counting of elements not allowed, you are expected to do it in O(n) time complexity.

Ex Array : {2, 0, 1, 2, 1, 2, 1, 0, 2, 0}

Answer 1

输出到链表。

• 记住列表的开头。
• 记住 1 开始的位置。
• 记住列表的末尾。

遍历整个数组。

• 如果遇到0，将其添加到链表的第一个位置。
• 如果遇到1，就在1的位置后面加上。
• 如果遇到 2，请将其添加到列表末尾。

HTH

乐