cur 和 end 是左右一起遍历的指针, 时间O(n);
先举出大量复杂测试用例一边想方案一边验证。
不要举 00 11 22 、 22 11 00 、 11 00 22 这类特点明显不够随机的用例。
用键盘随机按出:
231223321321
232123123
2312312321
23312123
2313123
思路:
设置三个标记指针,pos0,pos2,cur 令pos0从前往后遍历,指向第一个非0的位置,pos2从后往前遍历,指向第一个非2的位置 然后cur从pos0开始往后遍历: 遇到0就和pos0交换, while a[pos0] ==0 : pos0 = pos0 + 1 遇到1什么也不做; 遇到2就和pos2交换,pos2向前滑动到下一个非2的位置,交换后还要重新检查cur的值,如果cur是0, cur和pos0交换; 直到cur与pos2相遇。 一次遍历,复杂度是O(n),因为每次操作都使得数组更为有序,不像快排需要重复比较,所以比应用快排的方法效率高一些。
一个数组中只有0,1,2三个元素,进行排序,要求时间复杂度为O(n). https://blog.csdn.net/fjqcyq2/article/details/48929825?locationNum=8