使用遞歸排序

Question

我有以下函數來排序一個無序數組，以便在前面有偶數，在後面有奇數。有沒有辦法讓它完成而不使用任何循環？

//front is 0, back =array.length-1; 
arrangeArray (front, back); 

public static void arrangeArray (int front, int back) 
{ 
    if (front != back || front<back) 
    { 
     while (numbers [front]%2 == 0) 
      front++; 


     while (numbers[back]%2!=0) 
      back--; 


     if (front < back) 
     { 
      int oddnum = numbers [front]; 
      numbers[front]= numbers[back]; 
      numbers[back]=oddnum; 

      arrangeArray (front+1, back-1); 
     } 
    } 
} 

Answer 1

你想要做什麼是

arrangeArray(front, back, bool recursed=false) { 
    if (recursed) { 
     arrangeArray(front, back/2, true); 
     return arrangeArray(back/2, back, true); 
    } 
    // Do stuff here. 
} 

Answer 2

Mergesort是相當瑣碎的代碼，而循環：

​​

我會離開使它排序偶/奇作爲一個練習讀者:)

（聽起來像家庭作業）

Answer 3

當你做遞歸時，你有一個基礎步驟和一個遞歸步驟。

在這種情況下，基礎條件是當前==返回時，因爲您從邊緣開始，最終在中間。當你到達中間時，你知道它已經完成。

在你做遞歸步驟之前，你必須做一些排序。你只做一步一步的排序，所以現在只需處理array [front]和array [back]中的元素。將這些人安排在正確的地方後，請進行遞歸調用。

你最終的東西是這樣的：

public static void arrangeArray (int front, int back) 
{ 
    if(front >= back) return; 
    int f = numbers[front]; 
    int b = numbers[back]; 
    if(f%2 == 0) { 
     front++; 
    } else { 
     numbers[back] = f; 
     back--; 
    } 
    if (b%2 == 0) { 
     numbers[front] = b; 
     front++; 
    } else { 
     back--; 
    } 
    arrangeArray(front, back);           
} 

這是未經測試，可能是邊界條件不工作，但它是一個良好的開端:)

Answer 4

那不是簡單地：

//front is 0, back =array.length-1; 
arrangeArray (front, back); 

public static void arrangeArray (int front, int back) 
{ 
    if (front != back || front<back) 
    { 
     if (numbers [front]%2 == 0) 
      arrangeArray (front+1, back); 
     else 
     if (numbers[back]%2!=0) 
      arrangeArray (front, back-1); 
     else 
     if (front < back) 
     { 
      int oddnum = numbers [front]; 
      numbers[front]= numbers[back]; 
      numbers[back]=oddnum; 

      arrangeArray (front+1, back-1); 
     } 
    } 
} 

？

Answer 5

我可以推薦這個Python代碼片段來激發高層次的思考嗎？

compare = lambda x,y: x - y if x%2 == y%2 else y%2 - x%2 
>>> sorted([3,4,2,1,5,6,7,90,23,44], cmp=compare) 
[1, 3, 5, 7, 23, 2, 4, 6, 44, 90] 

我認爲需要建立一個比較函數，返回負數，0和正數，並使用它。

Answer 6

以下內容應該具有啓發性。這是一個遞歸的O(N)解決方案，它可以重新排列前面的偶數和後面的奇數，但不會做任何排序。

static boolean isEven(int n) { 
    return (n & 1) == 0; 
} 
static boolean isOdd(int n) { 
    return !isEven(n); 
} 
static int[] swapped(int[] nums, int i, int j) { 
    int t = nums[i]; 
    nums[i] = nums[j]; 
    nums[j] = t; 
    return nums; 
} 
static int[] arrange(int[] nums, int lo, int hi) { 
    return 
     (lo >= hi) ? nums : 
     (isEven(nums[lo])) ? arrange(nums, lo + 1, hi) : 
     (isOdd(nums[hi])) ? arrange(nums, lo, hi - 1) : 
     arrange(swapped(nums, lo, hi), lo + 1, hi - 1); 
} 
static void evenOddSort(int... nums) { 
    System.out.println(java.util.Arrays.toString(
     arrange(nums, 0, nums.length - 1) 
    )); 
} 
public static void main(String[] args) { 
    evenOddSort(1,3,5,7,2,4,6); 
} // prints "[6, 4, 2, 7, 5, 3, 1]" 

---

我認爲三元操作使得遞歸流更自然，但如果你不與它的工作原理是舒服，你可以用傳統的if-else。

static int[] arrange(int[] nums, int lo, int hi) { 
    if (lo >= hi) { 
     return nums; 
    } else if (isEven(nums[lo])) { 
     return arrange(nums, lo + 1, hi); 
    } else if (isOdd(nums[hi])) { 
     return arrange(nums, lo, hi - 1); 
    } else { 
     return arrange(swapped(nums, lo, hi), lo + 1, hi - 1); 
    } 
}