InsertionSort 降序 java

Question

这是按升序执行插入排序的代码。我正在尝试更改代码，以便它可以按降序排列。但每次我改变一些东西时，情况都会变得更糟。有人能给我指出正确的方向吗？

public static void insertionSort(Comparable[] list)
{
  for (int index = 0; index < list.length; index++)
  {
     Comparable key = list[index];
     int position = index;

     //  Shift larger values to the right
     while (position > 0 && key.compareTo(list[position-1]) < 0)
     {
        list[position] = list[position-1];
        position--;
     }

     list[position] = key;
  }
}

Answer 1

我没有发现您的代码有任何大问题。我要做的是用一个附加参数重载这个函数：一个 Comparator (docs here) 用来代替自然 compareTo.

作为灵感，请查看 this（java 中的集合）

static <T> void sort(List<T> list, Comparator<? super T> c) Sorts the specified list according to the order induced by the specified comparator.

要获得降序，您可以使用如下方式调用您的函数：

insertionSort(A,
                new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1) ;
            }}
        );

Answer 2

您当前的 insertionSort() 函数代码对于按升序排序是正确的。这是一个很好的起点。

我不知道你为了制作降序版本尝试了哪些更改。下次请包括该信息，否则我们无法告诉您为什么它不起作用。

要将您的函数更改为降序排序，逐字更改单个字符：

// Sort-ascending version (current)
key.compareTo(list[position-1]) < 0

// Sort-descending version (proposed
key.compareTo(list[position-1]) > 0

我已经测试了此更改并确认它有效。希望这对您有所帮助！

InsertionSort 降序 java

InsertionSort Descending order java

java

sorting

insertion-sort