c++ - 具有三个不同整数的排序数组，仅通过一次

Question

有没有可能只对数组进行一次传递就对包含三个整数的数组进行排序的方法？

你得到:

int array[]={1,2,2,2,3,1,1,2,2,1,3}

你被告知只有数字 1,2,3

得到:

int array[]={1,1,1,1,2,2,2,2,2,3,3}

不允许有多余的空间

谢谢!

Answer 1

没有多余空间的一次通过:

first pointer: Denotes start of 2 in the array.

last Pointer: Denotes start of 3 in the array.

If you find a 1, swap it with the first pointer.

If you find a 2, keep it there.

If you find a 3, swap it with the last pointer.

试运行:

{1,2,2,2,3,1,1,2,2,1,3} cur=1, first=1, last=10
{1,2,2,2,3,1,1,2,2,1,3} cur=2, first=2, last=10
{1,2,2,2,3,1,1,2,2,1,3} cur=3, first=2, last=10
{1,2,2,2,3,1,1,2,2,1,3} cur=4, first=2, last=10
{1,2,2,2,3,1,1,2,2,1,3} cur=5, first=2, last=10
{1,2,2,2,1,1,1,2,2,3,3} cur=5, first=2, last=9
{1,1,2,2,2,1,1,2,2,3,3} cur=5, first=3, last=9
{1,1,1,2,2,2,1,2,2,3,3} cur=6, first=4, last=9
{1,1,1,1,2,2,2,2,2,3,3} ...

时间:O(n)(一次通过)

空间:O(1)