算法-调整数组顺组使奇数位于偶数前面

题目: 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,偶数位于数组的后半部分。

解题思路: 比如我们有一个这样的数组:

数组的长度为10,最后能够实现前面4个数字是奇数,后面6个数字是偶数就好了,前面奇数的排序后后面偶数的排序没有要求,比如:

为啥数组里面有两个2呢?这是为了后面介绍是更方便的说明指针如何移动。

为了实现这个任务,一个最简单、粗暴、直接的方法就是从头遍历数组,如果发现是偶数,就拿出这个数并把该数字后面的元素全部向前移动一位,把这个数放到数组的最后一位。

由于我们并不知道数组中有几个奇数,有几个偶数,所以我们不得不遍历整个数组,所以这个算法的时间复杂度为O(n^2)

好在我们有更好的方式解决这个问题,管理两个指针p1和p2,p1初始位置指向数组中第一个数,p2初始位置指向数组中最后一个数,如果恰好p1指向地址内的是偶数,p2指向的地址内是奇数,那么就交换数值,移动指针,做下一次判断。举个例子:

p1指向0,p2指向9,两个数值交换,并且p1向后走1,p2向前走1;此时p1指向2,p2指向8,8就是偶数不需要交换,所以p1不动(等待p2指向奇数和它交换),p2向前走一步;此时p2指向7,两个数值交换并且p1向后走1,p2向前走1,重复上面的步骤:

此时p1指向3,p2指向4,不需要交换并且p1向后走1,p2向前走1:

p1跑到p2的后面了,表明所有的奇数都在偶数的前面了。

我们从上面的例子可以总结出指针移动的一些规律: p1只向后走,p2只向前走,其p1在p2后面时结束; 每次数值交换后p1,p2各走一步; p1指向偶数时如果p2满足条件则交换,不满足则保持不动,p2同理。 根据上面的分析,我们就可以写代码了。

代码实现

void ReorderOddEven(int *pData, unsigned int length)
{
    if(pData == NULL || length == 0)
        return;

    int *pBegin = pData;
    int *pEnd = pData + length - 1;

    while(pBegin < pEnd)
    {
        while(pBegin < pEnd && (*pBegin & 0x1) != 0)
            pBegin ++;

        while(pBegin < pEnd && (*pEnd & 0x1) == 0)
            pEnd --;

        if(pBegin < pEnd)
        {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }
    }
}

1.显然所有的操作都应该有一个大前提,p1(pBegin)在p2(pEnd)的前面:while(pBegin < pEnd),由于数组是连续存储,后面的地址一定比前面的大,代码就是在利用这个特点控制何时终止。 2.代码判断奇偶数:0x1—00000001,按位与操作。 3.循环内if判断的作用:显然两个指针从while退出之后,pBegin指向奇数,pEnd指向偶数,但是到了最后一步,就不能再交换了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

线性表(二)

985
来自专栏calmound

HDU 3555 Bomb(数位DP)

http://acm.hdu.edu.cn/showproblem.php?pid=3555 题意:0-n之间有多少个数包含"13"的 分析:dp[pos][h...

2595
来自专栏HelloCode开发者学习平台

BAT面试算法进阶(3)-无重复字符的最长子串

Given a string, find the length of the longest substring without repeating char...

651
来自专栏我是攻城师

一个优雅的反转数组的算法

` 比较简单粗暴的方法是,遍历原始数组从最后一项向前遍历,然后把输出结果保存在一个新的数组里面,这样就完成了所谓的反转。

551
来自专栏猿人谷

字符串的排列

题目:输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、ca...

1686
来自专栏落花落雨不落叶

线性表学习

32510
来自专栏章鱼的慢慢技术路

Aizu_Insertion Sort

1318
来自专栏来自地球男人的部落格

[LeetCode] 79. Word Search

【原题】 Given a 2D board and a word, find if the word exists in the grid. The wo...

17410
来自专栏编程理解

排序算法(四):归并排序

归并排序是通过分治的方式,将待排序集合拆分为多个子集合,对子集合排序后,合并子集合成为较大的子集合,不断合并最终完成整个集合的排序。

411
来自专栏静默虚空的博客

排序二 快速排序

要点 快速排序是一种交换排序。 快速排序由C. A. R. Hoare在1962年提出。 它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分:分割点左...

1766

扫码关注云+社区