幾種有關排序的常見面試問題

1、荷蘭國旗問題

題目描述：現有n個紅白藍三種不同顔色的小球，亂序排列在一起，請通過兩兩交換任意兩個球，使得從左至右，依次是一些紅球、一些白球、一些藍球。

分析與解法：

初看此題，我們貌似除了暴力解決并無好的辦法，但聯想到我們所熟知的快速排序算法呢？

我們知道，快速排序依托于一個partition分治過程，在每一趟排序的過程中，選取的主元都會把整個數組排列成一大一小的部分，那我們是否可以借鑒partition過程設定三個指針完成重新排列，使得所有球排列成三個不同顔色的球呢？

解法：

通過前面的分析得知，這個問題類似快排中partition過程，隻是需要用到三個指針：一個前指針begin，一個中指針current，一個後指針end，current指針周遊整個數組序列，當

1.current指針所指元素為0時，與begin指針所指的元素交換，而後current++，begin++ ；

2.current指針所指元素為1時，不做任何交換（即球不動），而後current++ ；

3.current指針所指元素為2時，與end指針所指的元素交換，而後，current指針不動，end– 。

為什麼上述第3點中，current指針所指元素為2時，與end指針所指元素交換之後，current指針不能動呢？因為第三步中current指針所指元素與end指針所指元素交換之前，如果end指針之前指的元素是0，那麼與current指針所指元素交換之後，current指針此刻所指的元素是0，此時，current指針能動麼？不能動，因為如上述第1點所述，如果current指針所指的元素是0，還得與begin指針所指的元素交換。

ok，說這麼多，你可能不甚明了，直接引用下gnuhpc的圖，就一目了然了：

參考代碼如下：

2、求需要排序的最短子數組長度

題目描述：

假設數組為a b c d e f g h i j k l m n，

如果abc是有序的，mn是有序的，至于中間的defghijkl是無序的，我們可以得知，如果是正常升序序列，左邊的一定是小于右邊的任意數值，右邊的一定大于左邊的任意數值。

思路：

1、我們從後往前周遊，如果某個元素大于右邊最小的元素，就标記，一直周遊到最左邊；

2、從前往後周遊，如果某個元素小于左邊的最大的元素，則标記，一直周遊到最右邊。

參考代碼：