使用遞歸分離偶數和奇數在整數數組中使用遞歸

我正在做一個算法練習，要求重新整理一個整數數組，以便將所有偶數元素放在奇數元素之前。使用遞歸分離偶數和奇數在整數數組中使用遞歸

我想了一會兒，用下面的僞代碼上來：

int[] Rearrange(int [] arr) 
{ 

    if arr.length=1 
    return arr; 

    if arr[0] is even 
    return arr[0] followed by Rearrange(arr.subarray(1,arr.length)) 
    else 
    return Rearrange(arr.subarray(1,arr.length)) followed by arr[0] 

}

我有點擔心我的上述建議的解決方案，因爲我需要在每個遞歸循環，這是做一個複製操作昂貴。請高手指教，謝謝！

來源

2014-09-30 Kevin

您的解決方案永遠不會遞歸。 – 2014-09-30 03:14:05

@BobJarvis它是僞代碼，所以我正在做假設，但它肯定看起來像它遞歸給我。重新安排基金在第二個if語句的兩個分支中調用它自己：首先，如果arr [0]是偶數，並且在其他情況下。這是遞歸tho的一個不好的用法。 – 2014-09-30 11:05:06

@DuncanC - 自發布我的原始評論以來，該問題已被編輯爲顯示對「重新排列」的調用。 – 2014-09-30 11:49:28

遞歸是昂貴的，你的方法會創建大量額外的副本。有時遞歸會產生一個優雅的解決方案，而其他時候絕對是這個工作的錯誤工具。這是一個錯誤的工具爲工作案例。

而是編寫一個保持頭部索引和尾部索引的方法。將頭指針初始化爲數組的開始位置，並將尾部索引初始化爲結尾。

在每次遍歷時，遍歷列表頭部的項目，查找奇數值。當你找到一個，停下來，然後從最後尋找一個平均值，向後看。找到它時，切換兩個值（使用第三個int作爲臨時存儲。）永久重複。當頭部和尾部索引相遇時，就完成了。

事情是這樣的：

int head_index = 0; 
int tail_index = array.count; 
int temp; 
while (true) 
{ 
    //Find the next odd number at the front of the array. 
    while (array[head_index] %2==0) && head_index < tail_index) 
    head_index++; 

    //Find the next even number at the end of the array. 
    while (array[tail_index]%2==1 && head_index < tail_index) 
    tail_index--; 

    //If the pointers meet, we're done 
    if (head_index <= tail_index) 
    break; 

    //Swap the items at the current indexes 
    temp = array[head_index]; 
    array[head_index] = array[tail_index]; 
    array[tail_index] = temp; 
}

（沒有經過充分測試，我累了，但基本的思路應該工作）

它更多或更少的C語法的僞代碼。

它應該在O（n）時間運行，只需要額外的RAM作爲2個索引和臨時保持變量。

來源

2014-09-30 03:23:27

真的很有幫助，很好學習。謝謝！ – Kevin 2014-09-30 04:26:37

即使問題得到解答，我在這裏解決這個問題的遞歸版本，以便讓人們想知道爲什麼遞歸是對這個問題不好的方法。

public static int[] segregate(int[] array, int left) { 

    int leftIndex = left; 

    if(left == array.length) { 
     return array; 
    } 

    for(int i = leftIndex + 1; i < array.length; i++) { 
     if(array[leftIndex] % 2 == 1) { 
      if(array[i] % 2 == 0) { 
       int temp = array[leftIndex]; 
       array[leftIndex] = array[i]; 
       array[i] = temp; 
      } 
     } 
    } 

    return segregate(array, leftIndex + 1); 
}

從代碼可以看出，該方法會自己調用N次。如果考慮到方法中for循環的複雜度爲O（N），則遞歸的總複雜度將爲O（n * 2），這比非遞歸解決方案更糟糕。

來源

2017-12-19 20:40:09

使用遞歸分離偶數和奇數在整數數組中使用遞歸

回答

相關問題