數組中的排序分析及奇偶排序 - 算法數據結構面試分享（四）

數組中的排序分析及奇偶排序

我們之前在課本上學習過一般的排序方法，如冒泡，快排，插入，歸并。其中時間復雜度有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);  
        }  
    } 

大功告成了哈。歡迎大家關注我的公眾號，還有我的系列專題課程

• 視頻教程
• 數據結構與算法
• 經典算法面試題輔導
• 排序專題講解
• 鏈表專題講解

大家有什么更好的解法，也歡迎討論哈。