了解 java 中 ArrayList 的排序方式

你的方法是错误的：你的短语“第一个 1 与 4 进行比较（依此类推）”描述了一种排序算法，但不知道任何排序算法。背后的想法是，任何排序算法都需要比较项目对，因此 为任何排序算法提供了这种特定功能，包括 ArrayList.sort（） 实现的算法（无论它是什么）。未来版本的 Java 可能会实现一种新的、更好的、尚未发明的算法，并且您提供的算法仍然有效且必要。ComparatorComparatorComparatorComparator

比较器的比较功能定义了两个元素的顺序。让我们从比较的角度了解减法是如何工作的： 如果您有：

1. i1 > i2，则 （） 为正数。i1 - i2

2. i1 < i2，则为负数。i1 - i2

3. i1 == i2，则为零。i1 - i2

   比较器函数的结果：compare

   • 负值表示第一个参数小于第二个参数。
   • 正值表示第一个参数大于第二个参数。
   • 零表示参数相等。

   给定列表 [5， 4， 1， 2] 和比较器，让我们一步一步地看：ints = (i1, i2) -> i1 - i2

   1. 比较 5 和 4：

      • 5 - 4 = 1（正数）
      • 这意味着 5 > 4，因此 5 应该在列表中的 4 之后。
      • 列表变为 [4， 5， 1， 2]。

   2. 比较 5 和 1：

      • 5 - 1 = 4（正数）
      • 这意味着 5 > 1，所以 5 应该在 1 之后。
      • 列表变为 [4， 1， 5， 2]。

   3. 比较 5 和 2：

      • 5 - 2 = 3（正数）
      • 这意味着 5 > 2，所以 5 应该在 2 之后。
      • 列表变为 [4， 1， 2， 5]。

   4. 比较 4 和 1：

      • 4 - 1 = 3（正数）
      • 这意味着 4 > 1，所以 4 应该在 1 之后。
      • 列表变为 [1， 4， 2， 5]。

   5. 比较 4 和 2：

      • 4 - 2 = 2（正数）
      • 这意味着 4 > 2，所以 4 应该在 2 之后。
      • 列表变为 [1， 2， 4， 5]。

此时，列表按升序排序，因此比较停止。

上述步骤假设一个简单的气泡排序，以便进行说明。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class comparing {
    public static void main(String[] args) {
        // Initialize ArrayList
        List<Integer> numbers = new ArrayList<>();
        numbers.add(5);
        numbers.add(4);
        numbers.add(1);
        numbers.add(2);
        // Print the original list
        System.out.println("\t\t Original list: " + numbers);
        // Custom comparator
        Comparator<Integer> ints = (i1, i2) -> i1 - i2;
        // Sort using the comparator
        numbers.sort(ints);
        // Print the sorted list
        System.out.println("\t\t Sorted list: " + numbers);
    }

}

结果将是：

在 ArrayList.sort（） 的情况下，底层实现使用 TimSort（MergeSort 和 InsertionSort 的混合体），它不会像示例那样通过反复比较和交换相邻对来排序。

我希望它有所帮助。

我想您想了解排序算法如何在内部使用比较器。那么，让我们看看如何使用 Comparator' 对列表进行排序。Collections.sort()

让我们看一下 JDK，具体看看插入排序如何使用比较器。

这是用于插入排序的 JDK 代码片段，用于对列表进行排序。Collections.sort()size < 7

for (int i=low; i<high; i++){
    for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
        swap(dest, j, j-1);
    }

   //remaining logic
}

我们可以看到，排序算法使用该方法来决定排序顺序。c.compare()

假设这是我的比较器函数：

class MyComparator implements Comparator<Integer> {
   @Override
   public int compare(Integer x, Integer y) {
       return x - y;
   }
}

排序算法将计算每个元素。而且，只有当上面的表达式大于 0 时，它才会交换左右值。即 if OR > .c.compare(dest[j-1], dest[j]) > 0x > ydest[j-1]dest[j]

因此，交换后，基本上是按升序对列表进行排序。smaller element in the right comes to left and greater element goes to right side

如果我们在方法中这样做，则将使用类似的逻辑以相反的顺序（降序）进行排序。y-xcompare()