有不同的方法来对只包含两种元素（即只有1和0）的数组进行排序。我们将讨论三种不同的方法来实现这个目标。第一种方法简单地使用预定义的sort()函数对给定的数组进行排序。第二种方法是计数排序方法，我们将计算0和1的数量，然后通过首先写入0的次数来更新数组，然后写入1的次数。在最后一种方法中，我们使用了双指针方法。
问题陈述
我们被给定一个只包含1和0的数组。我们的任务是将所有的0和1排列，使得1在数组的最右边，0在数组的左边
Example
的中文翻译为：
示例
Given array: a[] = [ 1, 1, 0, 1, 0, 1, 0, 1 ]Resultant array: a[] = [ 0, 0, 0, 1, 1, 1, 1, 1 ]
登录后复制
方法一：暴力破解法。
在此方法中，我们将直接使用 sort() 函数对数组进行排序。由于1>0，排序后，所有1都会排列在数组的右侧，所有0都会排列在左侧。
Sort() 函数：Sort() 函数需要 O(NlogN) 时间并按升序返回数组。
Example
的中文翻译为：
示例
下面是一个C++实现，用于对包含两种类型元素的数组进行排序。
#include using namespace std;int main(){ int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 }; int len = sizeof(a) / sizeof( a[0] ); // sort function to // sort the array sort( a, a + len); cout输出
在编译时，上述程序将产生以下输出 -
After sorting the array, the array obtained is 0 0 0 1 1 1 1 1
登录后复制
方法2：计数排序方法
在这种方法中，我们将简单地计算数组中 0 和 1 的数量，然后更新数组，其中 0 位于开头，1 位于最后。
通过这样做，我们将在数组的最左边部分拥有所有的0，并在数组的最右边部分拥有所有的1，这将自动表示所需的排序数组。
这是一种简单的方法，但它会向数组中插入新的值，而不仅仅是交换它们的位置，因此这种方法不高效。
Example
的中文翻译为：
示例
下面是使用 C++ 实现上述方法。
#include using namespace std;int main() { int count = 0 ; int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 }; int len = sizeof(a) / sizeof(a[0]); for(int iterator=0; iterator输出
编译时，它将产生以下输出 -
After sorting the array, the array obtained is 0 0 0 1 1 1 1 1
登录后复制
时间复杂度 - 由于我们只使用了一个循环，所以这种方法的时间复杂度为O(N)
空间复杂度 - O(1)。虽然我们使用了额外的变量，但由于它们是线性的，所以空间复杂度是常数。
方法 3：解决此问题的最佳方法
在这种方法中，我们将保留两个指针，即start和end。我们将同时使用start指针从数组的开头（索引为0）开始遍历，并使用end指针从末尾（索引为len-1）开始遍历。
我们的任务是将所有的1排列到数组的最右边，这将自动使所有的0排列到数组的左边。
我们从初始索引开始，如果找到的元素为 1，我们将与索引“end”处的元素交换它，并将结束指针递减 1。
如果找到的元素是0，那么就不需要执行任何交换操作，因为它已经在最左边的位置，我们只需将起始指针增加1即可。
Example
的中文翻译为：
示例
以下是实现此方法的代码 -
#include using namespace std;int main(){ int start =0 ; int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 } ; int len = sizeof(a) / sizeof( a[0] ) ; int end = len-1; while(start 输出
After sorting the array, the array obtained is 0 0 0 1 1 1 1 1
登录后复制
时间复杂度 - 由于我们只遍历数组一次，因此这种方法的时间复杂度是线性的，即 O(N)
空间复杂度 − 由于我们没有使用任何额外的空间，所以空间复杂度为 O(1)。
结论
在本文中，我们讨论了三种不同的方法来对仅包含两种类型元素（即仅 1 和 0）的数组进行排序。
以上就是对一个包含两种类型元素的数组进行排序的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2584205.html
