本文主要是介绍算法题：对只含有0，1，2三个元素的数组排序，时间复杂度O（n），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
将元素均为0、1、2的数组排序，时间复杂度O（n）。
思路：
方法1：通过三个下标遍历一遍实现的方法。
p1从左侧开始，指向第一个非1的数字；p3从右侧开始，指向第一个非3的数字。
p2从p1开始遍历，如果是2，p2继续遍历，直到p2遇到1或者3
如果遇到1，则和p1进行交换，然后p1向右，指向第一个非1的数字
如果遇到3，则和p3进行交换，然后p3向左，指向第一个非3的数字
方法2：基于快排划分的思路
上面的思路，是针对三个数的，如果有更多的数，怎么处理呢？比如，4个，5个等等。下面根据快速的排序的启发，介绍一种算法，尽管在处理三个数的时候，比较次数会多些，但具有很好的通用性。
思路来自快排的划分部分，快排的划分部分：给定pivot，然后将数据划分为<=pivot和>pivot两部分。这样，三个数字时，需要两次划分：
1.第一次，用1作为pivot,划分1到最左边；
2.第二次，用2作为pivot，划分2到左边，则得到整体的排序。
方法1的代码：
void sort012(vector<int> array)
{int p0=0;int p2=array.size()-1;int p1;//p0指向第一个不是0的值while(array[p0]==0 && p0<array.size()){p0++;}//p2指向第一个不是2的值while(array[p2]==2 && p2>=0){p2--;}p1=p0;//p1从p0的位置开始遍历while(p1<=p2){if(array[p1]==1)p1++;else if(array[p1]==0){swap(array[p0],array[p1]); while(array[p0]==0 && p0<array.size()){p0++;}}else{swap(array[p2],array[p1]);while(array[p2]==2 && p2>=0){p2--;}}}
}
这篇关于算法题：对只含有0，1，2三个元素的数组排序，时间复杂度O（n）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
