使用递归排序

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); 
    } 
}