数组中的排序分析及奇偶排序 - 算法数据结构面试分享（四）
数组中的排序分析及奇偶排序
我们之前在课本上学习过一般的排序方法，如冒泡，快排，插入，归并。其中时间复杂度有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); } } 大功告成了哈。欢迎大家关注我的公众号，还有我的系列专题课程
- 视频教程
- 数据结构与算法
- 经典算法面试题辅导
- 排序专题讲解
- 链表专题讲解
大家有什么更好的解法，也欢迎讨论哈。
