java - 我的 QuickSort 实现存在问题

Question

我正在尝试使用我自己的 QuickSort 实现按扩展名对文件进行排序(如果扩展名相同，则按文件名排序)。

因此，当我对一小部分文件进行排序时，它工作正常，但是当我使用一大组文件时，由于某种原因，某些文件会从结果列表中消失。我找不到原因。 (排序本身按预期工作......问题仅在于丢失的文件)。 有什么想法吗？

public static ArrayList<Extention> quickSort(ArrayList<Extention> list)
{
    if (list.size() <= 1)
        return list; // Already sorted

    ArrayList<Extention> sorted = new ArrayList<>();
    ArrayList<Extention> lesser = new ArrayList<>();
    ArrayList<Extention> greater = new ArrayList<>();
    Extention pivot = list.get(list.size()-1);
    for (int i = 0; i < list.size()-1; i++)
    {
        //int order = list.get(i).compareTo(pivot);
        if (list.get(i).getExtention().compareTo(pivot.getExtention()) < 0)
            lesser.add(list.get(i));
        else if (list.get(i).getExtention().compareTo(pivot.getExtention()) == 0){
            if (list.get(i).getFileName().compareTo(pivot.getFileName()) < 0){
                lesser.add(list.get(i));
            }
        }
        else{
            greater.add(list.get(i));}
    }

    lesser = quickSort(lesser);
    greater = quickSort(greater);

    lesser.add(pivot);
    lesser.addAll(greater);
    sorted = lesser;

    return sorted;
}

Answer 1

您似乎在本节中缺少了 else:

    ...
    else if (list.get(i).getExtention().compareTo(pivot.getExtention()) == 0){
        if (list.get(i).getFileName().compareTo(pivot.getFileName()) < 0){
            lesser.add(list.get(i));
        }
    }
    ...

应该是

    ...
    else if (list.get(i).getExtention().compareTo(pivot.getExtention()) == 0){
        if (list.get(i).getFileName().compareTo(pivot.getFileName()) < 0){
            lesser.add(list.get(i));
        } else {
              greater.add(list.get(i));
        }
    }
    ...

另请注意，由于您选择第一项作为主元，因此您应该从 1 而不是 0 开始循环(以免插入主元两次)