java - 仅使用一种方法使用 fastSort 对整数 vector 进行排序(无需 Medianof3 或分区方法，如经典实现)

Question

不确定我在这里做错了什么。我遇到空指针异常。我尝试过调整一些东西，我也有一个可以编译的版本，但似乎对 vector 的前半部分进行了排序，然后它将空值分配给一半的索引，因此我认为我的代码有根本性的错误。

正如标题中所述，我尝试仅用一种方法来做到这一点。 Middle 简单地定义为中间元素，(左+右)/2。我尝试通过 for 循环进行分区，而不是单独的分区方法。

我引用过:Stackoverflow with Quicksort Java implementation

主要是 raymi 接受的响应(因此在我的代码中//ei=right)

我不确定我在做什么不同...是他的代码不正确，还是我的代码不正确？

这是我的代码:

 public static void quickSort(Vector v, int left, int right) {
     //ei = right
     //si == left

     if(left == right){
     return;} 
     //base case -- no more recursion!!
     else{
         Comparable pivot = (Comparable) v.elementAt((left+right)/2);
         int i;
         i = left + 1;  

         //partition the array
         for(int j = left +1; j<= right; j++){
             if(pivot.compareTo(v.elementAt(j)) > 0){ 
                 swap(v, left, j);
                 i++;
             }//end if
        }//close for loop
         //place pivot in the right position
         //may be incorrect(?)
         v.replace(left, v.elementAt(i-1));
         v.replace(i-1, v.elementAt((Integer) pivot));

         //recursive call on both sides -- may be wrong(?)
         quickSort(v, left, i-2);
         quickSort(v, i, right);
     }
}//end quicksort

和我的交换替换代码，在其他方法中运行良好:

public void replace(int indexGiven, Object element){
    if(indexGiven<0 || indexGiven>= size)
        return false;

    data[indexGiven] = element;
    return true;
}

当我运行代码时，出现空指针异常。我已经尝试过将 "> 交换为 <"之类的东西，但最多我已经获得了编译代码并将空值分配给一半 vector 的代码。我认为我的代码有一些明显的错误，但我只是看不到它。

Answer 1

该问题之前包含与 Hoare 分区方案类似的代码，现已删除。应该开始了

    for(i = low-1, j = high+1 ; ;)

因为第一个 while 预先递增 i，第二个 while 预先递减 j。枢轴值可以来自数组中的任何值(例如枢轴 = a[(low + high)/2])，但实际使用的枢轴索引将基于 j，递归调用将为

    quicksort(a, low, j);
    quicksort(a, j+1, high);

旁注 - 您可以使用中位数 3 对 a[low]、a[(low + high)/2]、a[high](3 个 if/swap 语句)进行排序，然后使用ivot = a[(低+高)/2]。

由于示例 Hoare 分区代码已从问题中删除，我将在此处添加它:

void QuickSort(int a[], int lo, int hi)
{
    if (lo >= hi)
        return;
    int p = a[(lo + hi) / 2];   // set pivot, could use median of 3 here
    int i = lo-1;
    int j = hi+1;
    while (true)
    {
        while (a[++i] < p) ;    // increase i until a[i] >= pivot
        while (a[--j] > p) ;    // decrease j until a[j] <= pivot
        if (i >= j)             // break if indices meet or cross
            break;
        swap(a[i], a[j]);
    }
    QuickSort(a, lo, j);        // this part includes values <= pivot
    QuickSort(a, j + 1, hi);    // this part includes values  > pivot
}

Hoare type quicksort, p is pivot

          p              quicksort(a, 0, 7)
07 04 05 03 06 00 01 02
02                   07  swap
   01             04     swap
      00       05        swap
    p                    quicksort(a, 0, 3)
02 01 00 03
00    02                 swap
 p                       quicksort(a, 0, 1)
00 01   
       p                 quicksort(a, 2, 3)
      02 03
                p        quicksort(a, 4, 7)
            06 05 04 07
            04    06     swap
             p           quicksort(a, 4, 5)
            04 05
                   p     quicksort(a, 6, 7)
                  06 07