0

所以我一直在测试不同的排序算法，现在我写了一个快速排序！它有点工作，但排序有点偏离！几乎总是我得到这样的输出：

[0, 1, 2, 3, 8, 6, 5, 4, 7, 9, 20, 16, 22, 21, 14, 17, 18, 10, 15, 19, 13, 11, 23, 12, 26, 24, 25, ...

这是我正在排序的 100 个元素中的前 27 个元素。这就是我填写随机列表的方式：

for(int i =0; i < 100; i ++){
            int nr = rand.nextInt(100);
            if (!numbers.contains(new Integer(nr))){
                numbers.add(nr);
            }else {
                i--;
            }
}

这是快速排序的代码：

public class Quicksort{
@SuppressWarnings("unchecked")
static public <T> ArrayList<T> sortting(ArrayList<T> t){
    //System.out.print("-");
    T piv;
    ArrayList<T> left ,right ,newT;
    left    = new ArrayList<T>();
    right   = new ArrayList<T>();
    newT    = new ArrayList<T>();

    if (!t.isEmpty()){
        piv = t.get(t.size()/2);
        for (int i =0; i < t.size(); i++){
            if (0 < ((Comparable<T>) piv).compareTo(t.get(i))){ //left
                left.add(t.get(i));
            }else{  //right
                right.add(t.get(i));
            }
        }

        if (left.isEmpty() || right.isEmpty()){
            newT.addAll(left);
            newT.addAll(right);
            return newT;
        }else {
            right = sortting(right);
            left = sortting(left);

            newT.addAll(left);
            newT.addAll(right);
        }

        return newT;
    }
    return null;

}

}
4

2 回答 2

2

你的问题是这个块：

    if (left.isEmpty() || right.isEmpty()){
        newT.addAll(left);
        newT.addAll(right);
        return newT;
    }

如果您在某个点选择了恰好是当前子列表中最小的枢轴，则该子列表将自动被视为已排序。您应该只删除该检查并对左右子列表进行排序。

这没关系，因为您将使用一个空列表进入递归调用，在这种情况下您将返回null. 

if (!t.isEmpty()){ ... return newT;}
return null;

我实际上不确定是否可以优雅地ArrayList.addAll()处理null输入。如果您对此感到担心，那么您可以只返回一个空ArrayList而不是null.

于 2013-07-18T00:44:29.137 回答
0

回答你的意见，你指出了一些有助于分配的无能为力的部分！但这不是问题

问题是枢轴没有从数组中删除，这意味着如果枢轴是最小的元素，则正确的数组 == 到 t，这会导致无限循环并使 ram 过载！

例如。

5 ,4 ,8 ,6 ,8 will return 5 ,4 ,8 ,6 ,8

所以为了解决这个问题，需要移除枢轴并重新连接到数组的开头

现在

5 ,4 ,8 ,6 ,8 will return 4 ,5 ,8 ,6 ,8

如果您有兴趣，这里是源代码，并且专业提示：所有方法都确保至少有一个小的变化是在考虑您的迭代

@SuppressWarnings("unchecked")
static public <T> ArrayList<T> sortting(ArrayList<T> t){

    T piv;
    ArrayList<T> left ,right ,newT;
    left    = new ArrayList<T>();
    right   = new ArrayList<T>();
    newT    = new ArrayList<T>();

    if (!t.isEmpty()){
        if (t.size()==1){       //Finish check  -> one elem is sorted
            return t;
        }       
        piv = t.remove(t.size()/2);
        for (int i =0; i < t.size(); i++){          //sorting
            if (0 < ((Comparable<T>) piv).compareTo(t.get(i))){ //left
                left.add(t.get(i));
            }else{  //right
                right.add(t.get(i));
            }
        }   
        right   = sortting(right);  //sub sorting
        left    = sortting(left);

        newT.addAll(left);      //building newT
        newT.add(piv);
        newT.addAll(right);
        return newT;
    }
    return new ArrayList<>();   
}
于 2013-07-18T15:10:53.367 回答