数组中的排序分析及奇偶排序 - 算法数据结构面试分享（四）

数组中的排序分析及奇偶排序

我们之前在课本上学习过一般的排序方法，如冒泡，快排，插入，归并。其中时间复杂度有O(N), 和O(Nlogn), 以及O(N2）的。今天我们在这里看一些特定情况下的排序，并否所有的排序都是基于大小的，有时待排序的数大小范围是已知的，我们分别看两个典型的例子：

• 给你一个整型的数组，我想把奇数排在前面，偶数排在后面，也就是没有任何一个偶数出现在奇数的前面。
• 给你一个整型数组，里面出现的数在[0-100] 之间，能用最优化的方法帮我排序吗

我们今天先看第一个问题。还是按照之前的六部曲。

1. 确保我们理解了问题，并且尝试一个例子，确认理解无误。

题目当中已经把需求给细化了，没有任何一个偶数排在奇数的前面。举个例子 {1，2，3，4，5}会排成 {1，3，5，4，2}。 当然这里还有一个问题需要确认清楚，我们关心它的大小吗？即奇数和偶数部分都需要时升序的吗？ 这里可以告诉大家，我们可以忽略这个，这道题目中中只关心奇偶。

2. 想想你可以用什么方法解决问题，你会选择哪一种，为什么？

拿到这道题，我们首先想到的是如何判断奇偶数。但这其实不是本题的重点。一个很简单的方法出来了，我申明两个数组，一个保存奇数，另一个保存偶数，再把两个数组做一个合并并返回就好了。这个方法是可行的，再挑奇偶时，其实我们只需要扫描数组一遍，不过我们浪费了存储空间，至少我们需要另外申明两个临时的数组。而且，我们还无法事先知道奇数和偶数的数组应该是多长。是不是有更好的办法呢？

我们再看下之前的例子，看能不能找到什么蹊跷的地方？ {1，2，3，4，5} 从前往后，其实1是不用动的，2确定要往后挪​动，放到哪里呢？具体位置无所谓，但是保证它的后面没有奇数就好了。再从后往前，5是奇数，确定要往前放。到目前为止，如果我们能交换2和5问题就完美的解决了。没错，我们就是要从前往后依次找出偶数， 再从后往前找到奇数，再交换。再找下一个。如果采取这种方法的话，我们扫描数组一遍就可以解决问题了。

3. 解释你的算法和实现的方法

从上面的分析看，我们只需要定个两个临时变量就好了。一个从前往后，一个从后往前，终止的条件是他们相遇。 再定义一个临时变量，负责交换就好了。

4. 写代码的时候，记住，一定要解释你现在在干什么

那我们就直接上代码啦。

public static void Switch(int[] array)  
        {  
            if (array != null && array.Length > 1)  
            {  
                int begin = 0;  
                int end = array.Length - 1;  

                while (begin < end)  
                {  
                    if (array[begin] % 2 == 0) // 偶数  
                    {  
                        if (array[end] % 2 == 1) //奇数  
                        {  
                            //交换  
                            int temp = array[end];  

                            array[end] = array[begin];  
                            array[begin] = temp;  

                            begin++;  
                            end--;  
                        }  
                        else  
                        {  
                            end--;  
                        }  
                    }  
                    else  
                    {  
                        begin++;  
                    }  
                }  
            }  
        }  

在上面的代码中有一个地方可以优化，当我们找到前面待交换的偶数，再确定后面是否有奇数时，我们总是会将后面的指针往前移动。所以end -- 可以移出来，将外面的else也删掉。

5. Workthrough

6. 修复缺陷

我们一起来测试一下这个方法

static void Main(string[] args)  
    {  
        int[] array = new int[] { 1, 2, 3, 4, 5 };  

        Switch(array);  

        foreach (var a in array)  
        {  
            Console.WriteLine(a);  
        }  
    } 

大功告成了哈。欢迎大家关注我的公众号，还有我的系列专题课程

• 视频教程
• 数据结构与算法
• 经典算法面试题辅导
• 排序专题讲解
• 链表专题讲解

大家有什么更好的解法，也欢迎讨论哈。