Приложение сортировки слиянием - PullRequest
Новая
       20

Приложение сортировки слиянием

3 голосов
/ 15 июня 2011

Я делаю упражнение, в котором для массива из N значений мне нужно получить два числа, чтобы их вычитание (самое высокое - самое низкое) было самым положительным числом.Я хочу, чтобы v было больше, чем с ... дело в том, что ... скажем, я хочу покупать аукционы по цене C, чтобы я мог продавать их по цене V и получать максимальную прибыль, а каждая ячейка массива - этоцена этого аукциона в день t, поэтому я хочу купить по наименьшей возможной цене, чтобы я мог продавать по максимально возможной цене, поэтому C должен появиться перед V в массиве.Например: 

n = 8
arr = {6,7,3,8,9,2,1,4,20}

Я хочу c = 1 и v = 20, потому что 20 - 1 = 19 (это означает, что вычитание из этих двух чисел является наибольшим)

Другой пример: 

n = 6
arr = {8,12,45,40,18,29}

Я хочу c = 8 и v = 45, потому что их вычитание является наибольшим числом всех остальных вычитаний.(Я хочу уточнить, что с не всегда наименьшее число в массиве).ОБА ЧИСЛА НЕ ДОЛЖНА БЫТЬ СЛЕДУЮЩЕЙ.Если у меня есть n = 1, {1}, то c = 1 и v = 1.

В этом примере демонстрируется, что c и v не всегда являются самыми низкими / самыми высокими значениями.

n = 6
arr = {19,27,5,6,7,8}

В этом случае c = 19 и v = 27

Кроме того, мне нужно решить эту проблему с помощью кода сортировки слиянием много (примеры делят его на два метода: mergesort , который обрабатывает рекурсии, и слияние , которое выполняет смену позиций с помощью массива aux).

Я использую код слияния (слияние, по моему мнению, не нужно, потому чтоне заботится о сортировке), пока у меня есть следующий код, но он явно неправильный, может кто-нибудь сказать мне, что я делаю неправильно? 

public static void mergeSort(int start, int end) {
    if(start < end) {
        int half = (start + end) / 2;
        mergeSort(start, half);
        for(int i = start; start < half; start++, i++){
            if((arr[i+1] - arr[i]) > temp){
                temp = arr[i+1] - arr[i];
                c = i;
                v = i+1;
            }
        }
        mergeSort(half+1, end);
        for(int i = half+1; i < end; half++, i++){
            if((arr[i+1] - arr[i]) > temp){
                temp = arr[i+1] - arr[i];
                c = i;
                v = i+1;
            }
        }
    }
}

Заранее спасибо за любую помощь, которую вы можете предложить!

1 Ответ

2 голосов
/ 15 июня 2011

Я думаю, имя mergeSort в вашем коде наследуется ....

Так как вы уже выполнили рекурсию, нет необходимости перебирать все элементы, потому что после рекурсии, результат уже представлен. Например, один из возможных способов - поменять минимум на первое место и максимум на последнее место, а затем, на «верхнем» уровне рекурсии, вы можете просто получить их напрямую.

Вот еще одно решение, которое использует философию сортировки слиянием, но только возвращает макс. 

public class test {
    static int arr [] = {6,7,3,8,9,2,1,4,20};

    public static void main (String args[]) {
        System.out.println(merge_select_max(0, arr.length - 1));
    }

    public static int merge_select_max (int start, int end) { // both inclusive
        if (start == end) {
            return arr[start];          
        }
        else {
            int half = (start + end) / 2;
            int first = merge_select_max (start, half);
            int second = merge_select_max (half + 1, end);
            return (first > second ? first : second);           
        }       
    }
}
...