使用递归排序

发布于 2024-08-30 21:56:21 字数 595 浏览 7 评论 0原文

我有以下函数对无序数组进行排序，使其前面有偶数，后面有奇数。有没有一种方法可以在不使用任何循环的情况下完成它？

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

原文

I have the following function to sort an unordered array to having even numbers in the front and odd numbers in the back. Is there a way to get it done without using any loops?

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

相对绾红妆 2024-09-06 21:56:22

这不就是简单的：吗

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

？

Wouldn't that simply be:

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

回复收藏 0 原文

怪我太投入 2024-09-06 21:56:22

我可以推荐这个 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 和正值的比较器函数并使用它。

May I recommend this Python snippet to inspire high level thinking?

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]

I think one needs to build a comparator function that returns negative, 0, and positive and use that.

回复收藏 0 原文

摘星┃星的人 2024-09-06 21:56:22

你想做的是

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

What you want to do is

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

回复收藏 0 原文

噩梦成真你也成魔 2024-09-06 21:56:22

以下内容应该具有启发性。这是一个递归 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);
    }
}

The following should be instructive. It's a recursive O(N) solution that rearranges the even numbers in front and odd numbers in the back, but doesn't do any ordering beyond that.

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]"

I think the ternary operator makes the recursion flow more naturally, but if you're not that comfortable with how it works, you can just use traditional 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);
    }
}

回复收藏 0 原文

甜中书 2024-09-06 21:56:21

Mergesort 对于没有循环的代码来说相当简单：

void mergesort(int lo, int hi)
{
    if (lo<hi)
    {
        int m=(lo+hi)/2;
        mergesort(lo, m);
        mergesort(m+1, hi);
        merge(lo, m, hi);
    }
}

我将使其排序为偶数/奇数给读者的练习:)

（听起来像家庭作业）

Mergesort is fairly trivial to code without loops:

void mergesort(int lo, int hi)
{
    if (lo<hi)
    {
        int m=(lo+hi)/2;
        mergesort(lo, m);
        mergesort(m+1, hi);
        merge(lo, m, hi);
    }
}

I'll leave making it sort even/odd as an exercise to the reader :)

(Sounds like homework)

回复收藏 0 原文

极致的悲 2024-09-06 21:56:21

当你进行递归时，你有一个基本步骤和一个递归步骤。

在这种情况下，基本条件是当 front == back 时，因为您从边缘开始并在中间结束。当你到达中间时，你就知道它已经完成了。

在执行递归步骤之前，您必须进行一些排序。您一次只进行一步排序，因此现在只处理 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);                                         
}

它未经测试，可能不适用于边缘条件，但这是一个好的开始:)

When you do recursion, you have a base step and a recursive step.

In this case, the base condition is when front == back, because you start from the edges and end up in the middle. When you get to the middle you know it's done.

Before you do the recursive step, you have to do a bit of sorting. You're only doing the sorting one step at a time, so only deal with the elements at array[front] and array[back] for now. After you arrange those into the right place, do a recursive call.

You'll end up with something like this:

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

It's untested and probably doesn't work for edge conditions, but it's a good start :)

回复收藏 0 原文

~没有更多了~