时间戳

首页 > 解决方案 > 我的快速排序实现问题

java - 我的快速排序实现问题

问题描述

我正在尝试使用我自己的 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;
}

标签： javaquicksort

解决方案

看起来您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 而不是零开始循环（为了不插入枢轴两次）

推荐阅读