MergeSort 算法从大到小 java

Question

所以我想用mergesort算法对一个数组从大到小进行排序。我有这方面的工作代码，但我似乎无法让它从最大到最小排序。我试着玩弄 for 循环，其中包含所有这些 if 语句，但我就是想不通。有人可以帮忙吗

public class MergeSorter
{
    public void merge(int[] a, int l, int h) {
        if (h <= l) return;

        int result = (l + h) / 2;
        merge(a, l, result);
        merge(a, result + 1, h);
        sort_descend(a, l, result, h);
    }
    
    public void sort_descend(int[] a, int l, int result, int h) {
    
        int first_replace[] = new int[result - l + 1];
        int second_replace[] = new int[h - result];
        
        for (int i = 0; i < first_replace.length; i++)
            first_replace[i] = a[l + i];
        for (int i = 0; i < second_replace.length; i++)
            second_replace[i] = a[result+ i + 1];
        
        int first_i = 0;
        int second_i = 0;
            
        for (int i = l; i < h + 1; i++) {
            
            if (first_i < first_replace.length && second_i < second_replace.length) {
                if (first_replace[first_i] < second_replace[second_i]) {
                   a[i] = first_replace[first_i];
                   first_i++;
                } else {
                    a[i] = second_replace[second_i];
                    second_i++;
                }
            } else if (first_i < first_replace.length) {
                a[i] = first_replace[first_i];
                first_i++;
            } else if (second_i < second_replace.length) {
                a[i] = second_replace[second_i];
                second_i++;
            }
        }
    } 
}

import java.util.Arrays; 
public class MergeSortTest
{
    public static void main(String args[]) {
        int[] array = new int[]{ 6, 1, 3, 8, 3, 9, 2 };
        MergeSorter ms = new MergeSorter();
        ms.merge(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }  
}

Answer 1

除了一件事，你的整个逻辑都是正确的。在 sort_descend 函数中，将数组 a 复制到 first_replace 和 second_replace 后，您开始使用 if 条件 if (first_replace[first_i] < second_replace[second_i]) 比较元素.

在这里，您实质上是将两个元素中较小的一个分配到您的数组中 a，这一步决定了您的数组是按升序还是降序排序。

要按降序排序，只需反转此符号即可获得所需的输出，即将 if 条件更改为 if (first_replace[first_i] > second_replace[second_i])。

Answer 2

请参考以下代码对整数数组进行降序排序。它与您的解决方案类似，但仅在第 38 行更改了比较运算符。

import java.util.Arrays;
public class C
{
    public static void main(String args[]) {
        int[] array = new int[]{ 6, 1, 3, 8, 3, 9, 2 };
        MergeSorter ms = new MergeSorter();
        ms.merge(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
}

class MergeSorter {
    public void merge(int[] a, int l, int h) {
        if (h <= l) return;

        int result = (l + h) / 2;
        merge(a, l, result);
        merge(a, result + 1, h);
        sort_descend(a, l, result, h);
    }

    public void sort_descend(int[] a, int l, int result, int h) {

        int first_replace[] = new int[result - l + 1];
        int second_replace[] = new int[h - result];

        for (int i = 0; i < first_replace.length; i++)
            first_replace[i] = a[l + i];
        for (int i = 0; i < second_replace.length; i++)
            second_replace[i] = a[result + i + 1];

        int first_i = 0;
        int second_i = 0;

        for (int i = l; i < h + 1; i++) {

            if (first_i < first_replace.length && second_i < second_replace.length) {
                if (first_replace[first_i] >= second_replace[second_i]) {
                    a[i] = first_replace[first_i];
                    first_i++;
                } else {
                    a[i] = second_replace[second_i];
                    second_i++;
                }
            } else if (first_i < first_replace.length) {
                a[i] = first_replace[first_i];
                first_i++;
            } else if (second_i < second_replace.length) {
                a[i] = second_replace[second_i];
                second_i++;
            }
        }
    }
}

MergeSort 算法从大到小 java

MergeSort Algorithm from largest to smallest in java

java

algorithm

mergesort

loops

for-loop