C++排序数组为true false

Question

我已经被分配了两个类似的任务,这应该很容易,但我需要澄清我能用c ++做什么和不做什么.

任务1:假设您有一个包含两个不同键的n个元素的数组,true和false.给出一个O(n)算法来重新排列列表,以便所有假元素都在真元素之前.您可以仅使用恒定的额外空间.

对于任务2,我需要做同样的事情,但现在有一个额外的键"可能".所以我需要对数组进行排序,以便在O(n)之前可能先假,并且可能先于真.

我决定在第一个任务上使用插入排序,在第二个任务上快速排序.我的第一个问题是,创建一个数组并使用true false和/或可能的值对它进行排序是否理想.在我看来,我想要改变false,true和0,1,2的所有值,并按数字升序排序数组.我会通过首先遍历数组并更改值然后排序后执行此操作.什么是改变价值观的最佳方式(如果需要的话).这会使算法保持在O(n)时间吗？

谢谢您的帮助!

Answer 1

有一种经典的排序算法,在O(n)时间运行,称为计数排序.更确切地说,它在O(n + k)时间内运行并使用O(k)空间,其中k是可能的键的数量.

在这里,你只有3个可能的密钥,true maybe和false,因此k=3.因为这是一个常量,所以它在big-O表示法中被消除,因此你得到O(n)运行时间和O(1)空间.