使用插入排序对元素进行排序

Question

如果我使用如下所示的插入排序，并且有一个数组包含一些整数元素和一些空元素 - 我将如何使用插入排序对末尾为空元素的数组进行排序？

例如：[1, 2, 6, null, 9, 5, 4, null, 2, 3] 至：[1, 2, 2, 3, 4, 5, 6, 9, null, null]

Answer 1

一个选择是编写一个 compareTo 函数来处理 null:

public static <T extends Comparable<? super T>> int compareTo(T a, T b)
{
    if (a == null && b == null) return 0;
    if (a == null) return 1;
    if (b == null) return -1;
    return a.compareTo(b);
}

然后让插入排序使用：

while (compareTo >= 0 && compareTo(newElement, array[compareTo]) < 0) {

Answer 2

可以用Comparator.nullsLast来完成：

public static <T extends Comparable<? super T>> void insertionSort(T[] array) {
    Comparator<T> comparator = Comparator.nullsLast(Comparator.naturalOrder());
    // ...
    int compareTo = sorted;
    while (compareTo >= 0 && comparator.compare(newElement, array[compareTo]) < 0) {
    // ...
}

我使用 Comparator.naturalOrder 将 Comparable 比较标准转换为 Comparator。

使用插入排序对元素进行排序

Sorting elements using insertion sort

java

arrays

sorting

insertion