QuickSort没有完全工作

-2

我从多个来源改编的快速排序算法没有完全工作，我无法弄清楚它有什么问题。我认为在某个地方有一个错误的错误，但是我现在一直在尝试一个小时，结果没有什么不同。QuickSort没有完全工作

public static <T extends Comparable<T>> void serialSort(List<T> list){ 
    if (list == null || list.size() <= 1) { 
     return; 
    } 
    T pivot = list.get(list.size()/2 - 1); 
    int i = 0; 
    int j = list.size() - 1; 
    while (i <= j){ 
     while (list.get(i).compareTo(pivot) == -1){ 
      i++; 
     } 
     while (list.get(j).compareTo(pivot) == 1){ 
      j--; 
     } 
     if (i <= j) { 
      Collections.swap(list, i, j); 
      i++; 
      j--; 
     } 
    } 
    if (0 < j) 
     serialSort(list.subList(0, j)); 
    if (i < list.size()) 
     serialSort(list.subList(i, list.size())); 
}

我应该适应这个多线程版本，但我想先解决这个错误。

示例输入：

[2, 9, 4, 1, 7, 2, 1, 1, 6, 6, 3, 8, 4, 7, 6, 7, 8, 6, 3, 3, 3, 1, 4, 1, 1, 2, 9, 7, 7, 2]

输出：

[1, 1, 1, 1, 1, 2, 2, 1, 2, 3, 3, 3, 2, 4, 4, 4, 3, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 9, 9]

来源

2017-07-06 Tryphon

这是转让或用于生产？如果是第一个，那么通过更大更大的未排序列表直接理解问题（这是学习单元测试的好机会）。如果是后者，忘记这一点并使用Java运行时中已经存在的一个实现。 –

你重写了你的compareTo方法吗？正常比较要拒绝返回0，小于0或大于0.默认情况下，不指定它返回恰好为1或-1。 –

https://www.google.com/search?q=quick+sort+java&oq=quick+sort+java&aqs=chrome..69i57j0l5.2351j0j7&sourceid=chrome&ie=UTF-8#q=quicksort+java –

我

想通了List.subList（INT，INT）是此从Java文档：

Returns a view of the portion of this list between the specified fromIndex, 
inclusive, and toIndex, exclusive.

作为我怀疑这是一个错误。我没有在每次递归调用中包含“左”子列表的最后一个元素。这样做固定它：

if (0 < j) 
     serialSort(list.subList(0, j + 1));

来源

2017-07-06 23:21:10 Tryphon

正如@FFritz提到的，请您compareTo比较< 0和> 0（这是一般的只是好的做法）。
在为递归构建第一个subList时使用j + 1。

此代码：

public static <T extends Comparable<T>> void serialSort(List<T> list){ 
    if (list == null || list.size() <= 1) { 
     return; 
    } 
    T pivot = list.get(list.size()/2 - 1); 
    int i = 0; 
    int j = list.size() - 1; 
    while (i < j){ 
     while (list.get(i).compareTo(pivot) < 0){ 
      i++; 
     } 
     while (list.get(j).compareTo(pivot) > 0 && j > i){ 
      j--; 
     } 
     if (i <= j) { 
      Collections.swap(list, i, j); 
      i++; 
      j--; 
     } 
    } 
    if (0 < j) 
     serialSort(list.subList(0, j + 1)); 
    if (i < list.size()) 
     serialSort(list.subList(i, list.size())); 
}

来源

2017-07-06 23:21:28 Jason

QuickSort没有完全工作

回答

相关问题