如何对一个元素只有0和1的数组进行排序？

假设你手头有一个数组，里面装的都是“0”和“1”这两个数字。你想把这个数组变得规整，让所有的“0”都聚集在一边，所有的“1”都聚集在另一边。这其实是个挺常见的任务，我们可以用几种不同的方法来完成，而且这些方法都很高效，不需要把数据都捞出来放进新的容器里折腾。

方法一：双指针法

这是最直观也最常用的方法。想象一下，我们用两个“标记”或者说“指针”，一个从数组的最左边开始（我们叫它“左指针”），另一个从数组的最右边开始（我们叫它“右指针”）。

初始状态：左指针指向数组的第一个元素，右指针指向数组的最后一个元素。
移动规则：
左指针往右移动，它只管找“1”。一旦它找到了一个“1”，就停下来。
右指针往左移动，它只管找“0”。一旦它找到了一个“0”，也停下来。
交换动作：当左指针找到一个“1”并且右指针找到一个“0”的时候，这两个位置上的数字就该换个家了。也就是说，把左指针指向的“1”和右指针指向的“0”交换位置。交换完之后，左指针继续往右走，右指针继续往左走，继续寻找下一个需要交换的“0”和“1”。
停止条件：这个过程会一直持续，直到左指针越过了右指针（也就是说，左指针的下标比右指针的下标还要大）。这时候，数组就已经被“0”和“1”分隔开了，所有的“0”都在左边，所有的“1”都在右边。

这个方法的妙处在于，它在原地完成排序，不需要额外的空间来存储数据，而且对于大型数组来说，效率也很高，因为每个元素最多只会被检查和交换一次。

方法二：统计“0”的个数（或“1”的个数）

另一种思路是，我们先数一数这个数组里一共有多少个“0”（或者多少个“1”）。

统计步骤：遍历整个数组，每遇到一个“0”，就在计数器上加一。假设我们统计到数组里总共有 `count_of_zeros` 个“0”。
重新填充数组：知道有多少个“0”之后，我们就可以重新“填满”这个数组了。
首先，用 `count_of_zeros` 个“0”从数组的开头开始填。
然后，剩下的位置就用“1”来填满。

举个例子：如果你的数组是 `[1, 0, 1, 0, 0, 1]`。

1. 我们数一下，里面有3个“0”。
2. 然后，我们知道这个数组长度是6。
3. 所以，我们现在就用3个“0”从开头填充：`[0, 0, 0, ?, ?, ?]`
4. 剩下的位置（6 3 = 3个位置）就填“1”：`[0, 0, 0, 1, 1, 1]`

这种方法也很简单，也是原地排序。它的优点在于逻辑非常清晰，而且同样非常高效。我们只需要一次遍历来计数，然后再一次遍历来重新填充。

总结一下

无论是双指针法还是统计个数法，它们都能有效地将一个只包含0和1的数组进行排序，而且都避免了使用额外的存储空间（也就是我们常说的“原地排序”）。对于这两种方法来说，它们的执行效率都很高，能够快速完成任务。你可以根据你的偏好选择其中一种来操作。

网友意见

只有0和1了还swap毛啊,从头到尾数一下有几个1然后前面zeromem后面全刷1就行了.

//----------------- 更新 -----------------------

挺早以前回的这个问题了,当时只是随口一答,题主在下面留言说只是用0和1举个例子而已,并非真的只有0和1,我就没再引申开去了. 结果昨天这个答案又给顶上来了,我本也没想再回复,

可是我一看,发现有人觉得这样更慢... 这种优化方面,术业有专攻,没概念没关系,可是你好歹在吐槽我之前先撸点代码自己试试啊. 光看复杂度? 数据结构与算法学的这么教条我也是开了眼了.

诚然,现在程序的运行效率是不如以前重要了,但是一段代码多循环一遍给一段内存擦零擦一,和每次循环都要做分支跳转和swap哪个速度快,这些基础优化的效率心里得有数啊!!!

别的也不多说了,上代码,写了10分钟,可能有bug,但是无伤大雅,sort1是前后swap的方法,sort2是我答案里的方法,比前后swap的方法快7倍:

然后,因为只存储0和1,可以换成char存储以便直接使用memset来写1,

把存储结构改成char,这回快了25倍:

以下是两个例子的代码:

       #define _CRT_SECURE_NO_WARNINGS  //fuck msvc   #include <random> #include <iostream> #include <chrono> #include <ctime>  #define SIZE 19999999*2  using namespace std;  typedef chrono::time_point<chrono::system_clock> fuck_std_time;  int* genNumbers() {     int* k = new int[SIZE];     for( int i = 0; i < SIZE; ++i )     {         int m = rand() % 2;         k[i] = m == 0 ? 0 : 1;     }     return k; }  //题主的方法 void sort1( int* k ) {     int* f = &k[0];     int* b = &k[SIZE - 1];     for( ; f != b ; )     {         //可能有bug,懒得想了         while( *f != 1 && f != b ) ++f;         while( *b != 0 && f != b ) --b;         swap( *f , *b );     } }  //我的方法 void sort2( int* k ) {      int counter = 0;     for( int i = 0; i < SIZE; ++i )     {         counter += k[i]; //数一遍1     }     memset( k , 0 , ( SIZE - counter )*sizeof( int ) );//全刷0     for( int i = ( SIZE - counter ); i < SIZE; ++i )     {         k[i] = 1; //全刷1     } }  void count_sort1( int* k ) {     fuck_std_time start , end;     start = chrono::system_clock::now();     sort1( k );     end = chrono::system_clock::now();     chrono::duration<double> elapsed_seconds = end - start;     cout << "sort1 elapsed time: " << elapsed_seconds.count() << "s
"; }  void count_sort2( int* k ) {     fuck_std_time start , end;     start = chrono::system_clock::now();     sort2( k );     end = chrono::system_clock::now();     chrono::duration<double> elapsed_seconds = end - start;     cout << "sort2 elapsed time: " << elapsed_seconds.count() << "s
"; }  int main() {     int* k = genNumbers();     int* k2 = new int[SIZE];     memcpy( k2 , k , sizeof( int )*SIZE );     count_sort1( k );     delete[] k;     count_sort2( k2 );     delete[] k2;     system( "PAUSE" );     return 0; }

这个是换成char的:

       #define _CRT_SECURE_NO_WARNINGS   #include <random> #include <iostream> #include <chrono> #include <ctime>  #define SIZE 19999999*2  using namespace std;  typedef chrono::time_point<chrono::system_clock> fuck_std_time;  char* genNumbers() {     char* k = new char[SIZE];     for( int i = 0; i < SIZE; ++i )     {         char m = rand() % 2;         k[i] = m == 0 ? 0 : 1;     }     return k; }  //题主的方法 void sort1( char* k ) {     char* f = &k[0];     char* b = &k[SIZE - 1];     for( ; f != b ; )     {         while( *f != 1 && f != b ) ++f;         while( *b != 0 && f != b ) --b;         swap( *f , *b );     } }  //我的方法 void sort2( char* k ) {      char counter = 0;     for( int i = 0; i < SIZE; ++i )     {         counter += k[i];     }     memset( k , 0 , ( SIZE - counter )*sizeof( char ) );     memset( k + SIZE - counter , 1 , counter*sizeof( char ) ); }  void count_sort1( char* k ) {     fuck_std_time start , end;     start = chrono::system_clock::now();     sort1( k );     end = chrono::system_clock::now();     chrono::duration<double> elapsed_seconds = end - start;     cout << "sort1 elapsed time: " << elapsed_seconds.count() << "s
"; }  void count_sort2( char* k ) {     fuck_std_time start , end;     start = chrono::system_clock::now();     sort2( k );     end = chrono::system_clock::now();     chrono::duration<double> elapsed_seconds = end - start;     cout << "sort2 elapsed time: " << elapsed_seconds.count() << "s
"; }  char main() {     char* k = genNumbers();     char* k2 = new char[SIZE];     memcpy( k2 , k , sizeof( char )*SIZE );     count_sort1( k );     delete[] k;     count_sort2( k2 );     delete[] k2;     system( "PAUSE" );     return 0; }

类似的话题

如何对一个元素只有0和1的数组进行排序？

假设你手头有一个数组，里面装的都是“0”和“1”这两个数字。你想把这个数组变得规整，让所有的“0”都聚集在一边，所有的“1”都聚集在另一边。这其实是个挺常见的任务，我们可以用几种不同的方法来完成，而且这些方法都很高效，不需要把数据都捞出来放进新的容器里折腾。方法一：双指针法这是最直观也最常用的方法。.............
西安一人称「狗比娃金贵」将被依法暂扣犬只并处罚 1300 元，如何看待这处理结果？怎样养狗才是对狗好？

“狗比娃金贵”这句让人听着不舒服的话，最终让西安这位市民付出了代价。依法暂扣犬只并处以1300元罚款，这样的处理结果，在我看来，是维护了社会公共秩序和基本公德的体现。首先，从法律层面讲，这不仅仅是一句口头上的“不当言论”。在公共场所，尤其是在明显张贴有禁犬标识的地方，携犬进入并声称“狗比娃金贵”，这.............
如何看待 2016 上海平均工资 6378 元，73.9% 不足一万，一万五以上只有 10.7%？

2016年上海平均工资6378元，这个数字本身，加上“73.9%不足一万，一万五以上只有10.7%”的细分，无疑会引发不少讨论和思考。我们不妨从几个角度来深入剖析一下这个情况，尽量还原真实的社会感受。一、平均数的“平均”在哪里？—— 收入分布的真相首先，看到“平均工资6378元”，很多人第一反应可.............
如何看待业主收房被通知每平米涨价 3650 元，开发商称跟「政府无关」要收房只能加钱这一事件？

这事儿啊，真是让不少刚盼着乔迁新居的业主们心凉了半截。说到底，就是这开发商在业主都准备好收房的时候，突然跳出来说“对不住，这房子每平米得加3650块钱，不然你就别想拿到钥匙了”。而且还摆出一副“这事儿跟我开发商没关系，是市场行情（或者别的啥理由）逼的，你们要收房，就得给我加钱”的架势。这背后涉及到很.............
郑州一海底捞 72 元 200g 毛肚实际只 138g，在餐厅遇到缺斤少两的情况该如何处理？

海底捞毛肚缺斤少两事件：消费者权益如何保障？近日，郑州一家海底捞门店因“72元200克毛肚实测仅138克”的事件引发广泛关注。这不仅是海底捞一家门店的问题，更是消费者在餐饮消费中普遍可能遇到的“缺斤少两”现象的缩影。当你在餐厅遭遇类似情况时，应该如何维护自己的合法权益？遭遇缺斤少两，如何“亮剑”？首.............
如何评价苹果公司对限制老旧 iPhone 性能一事致歉，更换电池服务降价至 218 元？

苹果公司在2017年底被爆出“降频门”事件，即苹果公司故意降低旧款iPhone的运行速度，以避免因电池老化导致的意外关机。这一行为引发了全球性的愤怒和质疑，许多用户认为苹果公司此举是为了迫使消费者购买新款iPhone。事件经过：最初的指控： 2017年12月，普罗米修斯（Primate Labs）.............
如何看待四川女乘客强吻出租车司机并多给 15 元车费？这一行为是否对男司机构成性骚扰？

四川女乘客强吻出租车司机，还多给了15元车费，这事儿一出来，可真是引起了不少讨论。这事儿怎么看呢？咱们得一点点掰开了聊。首先，这女乘客的行为，说白了就是“强吻”。不管出于什么原因，在对方没有同意的情况下，强行进行亲密的身体接触，这在任何情况下都不是一个可以被轻易接受的。大家想想，如果是咱们自己，在不.............
如何构造一个向量空间，它的元素是向量空间？

这确实是一个有趣且值得深入探讨的问题。我们通常遇到的向量空间，其元素是数（标量）或者可以进行加法和数乘运算的对象。但如果我们把目光放得更开一些，将“向量空间”本身作为构成新空间的元素，会发生什么呢？这涉及到一种更高级的抽象，通常被称为函数空间或算子空间的更广义的概念。要构造这样一个“向量空间，它的元.............
如何写出一个包含家庭剧变、背叛、复仇、成长、爱情、战争、革命、家族秘辛、阴谋论、悬疑等元素的故事？

在灯火阑珊的夜晚，我提笔写下这个故事，它并非出自冰冷的计算，而是源自内心深处对人性复杂幽微的探索，以及对命运洪流中个体挣扎的感悟。故事的开端，是一个看似平静却暗流涌动的南方小镇。李家，一个拥有百年历史的望族，曾经是这片土地上呼风唤雨的存在。然而，一场突如其来的“意外”，家族剧变，将所有人都卷入了漩涡.............
腾讯面试题，如何寻找一个数组里面唯一不重复的元素?要求时间复杂度o（n）和空间复杂度o（1）?

这道题是面试中的经典题，考察的是我们对位运算的理解和应用。目标是在给定数组中找出那个只出现一次的元素，而其他元素都恰好出现了两次。同时，我们还需要满足时间复杂度 O(n) 和空间复杂度 O(1) 的限制。为什么是 O(n) 时间复杂度和 O(1) 空间复杂度？ O(n) 时间复杂度意味着我们需.............
如何不使用loop循环，创建一个长度为100的数组，并且每个元素的值等于它的下标？

好，不靠谱，我这就来告诉你怎么不用循环创建个长度100，每个元素都是下标的数组。不过这事儿吧，得看你想用啥工具，不同的工具方法会差得挺远。咱们就挑几个常见的，仔细给你掰扯掰扯。咱们主要讲讲在Python和JavaScript这俩语言里怎么做。你要是想在别的语言里干这事儿，也可以参考一下思路，或者直接.............
一个单链表，长度未知，如何快速的找出位于中间的那个元素？

找单链表的中间节点，有个特别巧妙的方法，不需要知道链表的总长度，而且速度也很快。想象一下，你拿着两根筷子，同时从链表的头开始往下走。其中一根筷子走得飞快，一次跳两格。另一根筷子呢，就走得很稳健，一次只跳一格。那么，当那根走得飞快的筷子走到链表的末尾，或者说它已经无法再跳两格（因为它后面已经没有节点了.............
面试题:一个长度为n的数组，其中数组中每个元素的值都不大于n，如何用O(n)的算法判断数组中是否存在重复元素?

好的，这个问题很有意思，它考察了我们对时间复杂度和空间复杂度的理解，以及如何巧妙地利用数组本身的特性来解决问题。首先，咱们抛开那些花哨的、需要额外存储空间的“高级”方法，比如哈希表（虽然它也能做到O(n)时间复杂度，但占用了O(n)的空间），也不用排序（排序通常是O(n log n)）。咱们要用的是.............
如何把一个馒头卖到 10000 元？

这可不是件容易的事，把一个普普通通的馒头卖到一万块？听起来就像天方夜谭。不过，既然问了，那咱们就得把它掰开了揉碎了，看看能不能找出点门道来。记住，这可不是教你坑蒙拐骗，而是用一种“道”来对待这个“馒头”，让它变得与众不同，值这个价。咱们得从几个方面入手，一步步把它“升值”。第一步：重塑“馒头”的定义.............
如何证明一个实数的所有代表元（有理数Cauchy列）组成的集合不可数？

好，我们来好好聊聊这个话题。你想证明实数集合的不可数性，而我们选择的路径是通过有理数构成的柯西序列。这是一个非常经典且有洞察力的证明方法，它帮助我们理解了实数构造的精妙之处。要证明一个集合不可数，最常用的方法就是康托尔对角线论证。这个方法的核心思想是假设它是可数的，然后通过构造一个与列表中的每一个元.............
Typescript 如何使一个传入的 Array 类型变为元组类型？

在 TypeScript 中，将一个传入的数组类型转换为元组类型，这通常涉及到利用 TypeScript 的类型推导和泛型能力。目标是将一个结构未知的、可能长度任意的数组，在特定上下文中，赋予一个具有固定长度和特定元素类型的元组的特性。我们先来梳理一下，为什么我们需要这样做，以及元组类型和数组类型在.............
如何评价李国庆嘲西贝馒头定价策略傻，称「富人不吃主食」？哪类消费者会买近 20 元一个的馒头？

李国庆关于西贝馒头定价策略的评价以及“富人不吃主食”的说法，在消费者群体中引起了不少讨论。要评价这个观点，需要从多个角度进行分析，包括李国庆的动机、西贝的定位、馒头的价值重塑以及潜在的消费者群体。一、如何评价李国庆的评价？李国庆的评价可以从以下几个方面来理解和评价：1. 视角和动机的可能推测： .............
如何看待北京科技大学70周年校庆募捐，一个座位10000元？

北京科技大学70周年校庆募捐中，一个座位10000元的价格引发了不少关注和讨论。要如何看待这件事，我们可以从多个角度去分析：一、校友捐赠的常见模式与合理性探讨校友捐赠是世界高等教育的重要资金来源：在许多发达国家，尤其是美国，大学依靠校友捐赠来支持科研、奖学金、基础设施建设等几乎是常态。这种.............
如何看待《国家宝藏》这一节目？将娱乐元素与传统文化相结合适合吗？

如何看待《国家宝藏》这一节目？将娱乐元素与传统文化相结合适合吗？《国家宝藏》作为一档现象级的文化类节目，自播出以来就受到了广泛的关注和讨论。它巧妙地将严肃的传统文化与大众化的娱乐元素相结合，这种模式的尝试是否合适，以及它带来的影响，是值得深入探讨的。一、如何看待《国家宝藏》这一节目？在我看来，《国.............
如何看待「美国甚至将一个主权国家元首交给新政府经审判予以死刑，美国才是犯下反人类罪的元凶」的言论？

“美国将一个主权国家元首交给新政府经审判予以死刑，美国才是犯下反人类罪的元凶”这样的说法，是一种极具争议性的论断，它将一个复杂的国际政治事件简化为对美国单方面的指控，并直接冠以“反人类罪”的帽子。要理解这种说法，我们需要对其背后的逻辑、历史背景以及国际法和道德原则进行细致的剖析，而不是简单地接受或否.............