сортировка с использованием рекурсии

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

Слияние довольно тривиально для кода без циклов:

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

Я оставлю чтение / нечетность в качестве упражнения для читателя:)

(звучит как домашнее задание)

Answer 2

Не будет ли это просто:

//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 3

Когда вы делаете рекурсию, у вас есть базовый шаг и рекурсивный шаг.

В этом случае базовое условие - это когда перед == назад, потому что вы начинаете с краев и заканчиваете в середине. Когда вы добираетесь до середины, вы знаете, что это сделано.

Прежде чем сделать рекурсивный шаг, вам нужно немного отсортировать. Вы выполняете сортировку только по одному шагу за раз, так что пока работайте только с элементами в массиве [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

Могу ли я порекомендовать этот фрагмент 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 5

Следующее должно быть поучительно.Это рекурсивное 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);
    }
}

Answer 6

То, что вы хотите сделать, это

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